Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 14-01-2011 17:09:06

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Des hauts et des bas..

Une tribu vit en forêt vierge. Chaque foyer vit dans une cahutte,  loin des autres cahuttes.
De tout temps, chaque fois qu'un foyer a été créé, chacun des autres l'a relié directement à chez lui soit par un souterrain, soit par un "surterrain" (chemin dans les arbres), car il est dangereux de se déplacer au sol.
Ces sur- ou souterrains ne se croisent jamais entre eux (ils peuvent passer l'un au dessus de l'autre).

Dans les souterrains, il faut se déplacer en cuissardes à cause des infiltrations d'eau, et dans les arbres il faut se déplacer en basket.

Le sorcier de la tribu, de temps en temps, fait la tournée de toutes les familles, dans l'ordre que lui ont dicté les oracles. Il est vieillissant et voudrait pouvoir faire chaque tournée en minimisant le nombre de fois où il doit changer de chaussures évitant ainsi de se baisser, quitte à repasser plusieurs fois par la même cahutte si nécessaire. Quel conseil lui donneriez-vous pour s'organiser ?

Le conseil est celui-ci : Spoiler : [Afficher le message] il est possible (en repassant par des foyers déjà visités) de tout faire soit en l'air, soit en souterrain) . Mais ça reste à prouver...

PS : Si c'est pas clair, n'hésitez pas à demander, j'éditerai.

PS2 : oui, le sorcier a des baskets ET des cuissardes, il y a une ZAC pas très loin.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 15-01-2011 00:00:59

sterac
Amateur de Prise2Tete
Enigmes résolues : 25
Messages : 9

Des hauts et des ba.s..

admetons une foret vierge conquise par l'homme (donc plus vierge), ben moi je lui conseille, vu qu'il a deja des cuissardes et des baskets, de prendre un sac a dos.

a son bon gré de changer quand il le souhaite...

 #3 - 15-01-2011 09:57:05

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

des hauts et fes bas...

C'est ça, déjà qu'il veut pas se baisser à cause de son dos, et il faudrait EN PLUS qu'il se coltine un sac à dos... Sterac : tout faux.

 #4 - 15-01-2011 10:46:11

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,474E+3

des hauts et des vas...

De toute façon, chaque maison est reliée à toutes les autres par un des deux types de chemins. Donc, si j'en prend une, je peux voir toutes les autres avec 2 paires de chaussures non ?

Maintenant, il faut savoir si une paire de chaussures suffirait :

1) par l'absurde ?


Si un foyer est relié à tous les autres par un seul type de chemin : une paire suffit

La question devient deux paires sont-elles indispensables?  peut-on créer deux groupes indépendants 1 et 2  si on n'a qu'une paire de chaussures ?

On a choisi une chaussure : Il y a alors entre le groupe 1 et  le groupe 2 uniquement des chemins d'un seul type (celui de l'autre chaussure) . Or, chaque maison de l'un étant reliée à une maison de l'autre , toutes les maisons du premier  sont reliées par un chemin de ce type à toutes celles de l'autre.  Idem à l'inverse. Donc, il suffit de prendre l'autre chaussure

Il n'est donc pas possible de créer deux groupes indépendants : une paire de chaussures suffit, reste à trouver la bonne.

Autre raisonnement

2) par itération
, je pars d'un groupe de foyers connecté tous entre eux par un seul type de chemin. (genre 2 foyers, on devrait pouvoir le prouver)

Je rajoute un foyer : Soit il s'intègre au groupe en y étant relié au moins une fois par ce type de chemin : le problème est donc le même au foyer suivant.

Soit il ne s'y intègre pas en n'étant connecté au groupe de base par aucun chemin de ce type, mais dans ce cas, le nouveau foyer est relié à tous les autres par le deuxième type de chemin, et le problème initial est de nouveau le même.

Donc , à chaque nouveau foyer, tous les foyers communiqueront entre eux avec un seul type de chemin : une paire de chaussure suffit.

PS : quel que soit l'ordre choisi par les oracles chaque jour, ce sera la même paire de chaussures, jusqu'à la construction d'un nouveau foyer. même pas besoin de réfléchir le matin.

 #5 - 15-01-2011 13:09:53

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Ds hauts et des bas...

Le nombre de foyers est quelconque.

L'idée est de minimiser le nombre de fois où il doit changer de chaussures.

 #6 - 15-01-2011 16:15:45

CLAIRE68
Habitué de Prise2Tete
Enigmes résolues : 48
Messages : 32

des hauts et dzs bas...

salut
Personnellement je ne vois pas trop le pb, puisque la hutte du sorcier est reliée à tous les autres foyers, il peut revenir à chaque fois chez lui et faire d'abaord tout ce qui est "sous", ensuite tout ce qui est "sur" ce qui ne lui fait changer de chaussures qu'une seule fois. (s'il n'a pas un ordre  d'ancienneté à respecter dans les visites)
D'autre part, il ferait relier tout le monde par face book , il se casserait moins le dos et le reste.

 #7 - 15-01-2011 19:16:24

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

De hauts et des bas...

Bien Claire, mais on peut faire mieux... il est là le problème.
Pour facebook, il a demandé le cable, c'est en travaux :-)

 #8 - 15-01-2011 19:22:40

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Des hauts e des bas...

et bravo à Gwen pour ses deux preuves ! :-)

 #9 - 16-01-2011 13:42:06

Tromaril
Habitué de Prise2Tete
Enigmes résolues : 20
Messages : 45

deq hauts et des bas...

Bonjour,

On a un graphe complet avec des arêtes de deux types : H (Haut) pour les sur-terrains et B (Bas) pour les sous-terrains.

Si le graphe partiel restreint aux arrêtes H est connexe alors le sorcier peut rejoindre toutes les habitations en basket.
Sinon, ça veut dire que ce graphe partiel a k composantes connexes et que son complémentaire (le graphe partiel des arêtes B) est un graphe "k-parties" complet qui est donc connexe. Le sorcier peut alors rejoindre toutes les habitations en cuissardes  (au fait, sorcier ou sorcière ? tongue)

Edit : En fait le graphe partiel des arêtes B n'est pas forcément un graphe "k-parties" complet mais il en contient un.

 #10 - 16-01-2011 21:41:38

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

des hautd et des bas...

Tromaril, tu veux dire "k-partite" je suppose... Bien joué :-)

 #11 - 17-01-2011 10:17:12

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 198

Des huts et des bas...

Alors je me mets dans la peau du vieillard.
Je regarde:
- l'ensemble A de toutes les cahuttes que je peux visiter en ne passant que par les arbres (notamment la mienne),
- l'ensemble B (complémentaire de A) des cahuttes pour lesquelles je suis obligé de mettre mes cuissardes.

Si B est vide, alors c'est cool: je pars en Basket.

Si B est non vide, alors qu'est-ce qui se passe?
Soit a une cahutte de A et b une cahutte de B. Forcément ces deux cahuttes sont reliées par un souterrain car sinon je pourrais aller en b en basket en passant par a.
Alors j'enfile mes cuissardes et pour aller à une cahutte de B, je passe direct par le souterrain qui relie ma maison à b et pour aller à une cahutte de A, je passe par une cahutte de B (qui est non vide).

 #12 - 17-01-2011 10:20:02

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 434

Des hats et des bas...

Salut,


Il peut exister une cahutte relier uniquement par des souterrains. Il peut aussi exister une cahutte relier que par des sur-terrains. Mais ces deux types de cahuttes ne peuvent pas coexister puis qu'elles doivent être connectées.
Il en va de même pour des groupes de cahuttes connectées entre elles d'une façon et avec les autres exclusivement de l'autre façon. Un groupe de type opposé ne peut pas coexister puisque toutes les maisons doivent être interconnectées, de sorte qu'un des deux mode de transport est 100% compatible (j'ai chercher d'autres termes mais pas trouvé big_smile). Il donne accès à toutes les cahuttes sans discontinuer.
Donc en connaissant le réseau de cahuttes, il est possible de passer dans toute les cahuttes sans se changer.

 #13 - 17-01-2011 10:47:53

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Des hauts et dees bas...

Pas mal Irmo, juste un détail : quand tu dis "l'ensemble B (complémentaire de A) des cahuttes pour lesquelles je suis obligé de mettre mes cuissardes", il faut s'assurer (même si c'est assez évident) que tu es obligé de mettre tes cuissardes certes, mais mieux : tu n'as pas besoin de baskets (sinon on aurait un chemin composite). Et c'est le cas, puisque ta case est forcément reliée à chaque b de B par un souterrain (sinon, b serait dans A).

 #14 - 17-01-2011 10:56:51

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Des hauts et des bas..

et Milou_le_viking, toutes les idées y sont, mais ton argument n'est pas très clair. Désolé, c'est mon travers, j'enseigne la logique smile

 #15 - 17-01-2011 11:46:09

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 434

des hauts et fes bas...

Je vais tenter de faire mieux.

S'il existe un ou plusieurs îlots de cahuttes connectées entre elles par des souterrains et connectées au reste de la tribu par des sur-terrains (que j'appelle îlots de type "souterrain"), alors il n'existe aucun îlot ne disposant pas de connexion de type sur-terrain de sorte que les îlots ce type n'existe pas. Il est dès lors possible de parcourir l'ensemble de la tribu sans se changer en empruntant les sur-terrains.
En effet, s'il s'avérait impossible de parcourir toute la tribu en empruntant les sur-terrains, cela constituerait un îlot de type opposé à celui qui existe par hypothèse, ce qui est impossible comme je l'ai expliqué plus haut.

Dans le cas où il n'y aurait aucun îlot d'aucun type, les deux modes de transport permettent de parcourir la tribu sans se changer.

Mieux ?

 #16 - 17-01-2011 12:22:29

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2991
Lieu: Fanning Island-?-Lac Tele,Mali

des haurs et des bas...

Admettons que les habitants relient les cahuttes de maniere a forcer le sorcier a se baisser. Ils vont donc isoler 2 groupes ou a l'interieur de chaque groupe toutes les connections sont dans les arbres. Mais comme tout le monde est relié a tout le monde le reste des connexions (entre les 2 groupes) se fait par souterrain, et donc par souterrain tout le monde est relié a tout le monde. Le sorcier prendra donc les souterrains. L'inverse est vrai aussi.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #17 - 17-01-2011 13:27:03

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

dzs hauts et des bas...

Oui Milou, c'est mieux en effet... tu vois quand tu veux wink

 #18 - 17-01-2011 13:36:59

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

des hauts zt des bas...

Bien que pas très formel, l'argument de drhm me paraît juste.

 #19 - 17-01-2011 13:53:34

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 434

Des hautts et des bas...

Note que la démonstration par l'absurde ne fait que démontrer que ma première explication était suffisante. big_smile

 #20 - 17-01-2011 15:40:39

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1988
Lieu: Paris

Des hautss et des bas...

Montrons donc par récurrence sur n le nombre de cahute:
P(n) : il existe un chemin qui relie toutes les cahutes qui passe soit en l'air uniquement, soit sous terre uniquement

n=2 : c'est évident.

supposons P(n) : montrons P(n+1)
Le rajout d'une (n+1)-ème cahute va ajouter des chemins entre cette nouvelle cahute et les n existantes.
Là 3 possibilités :
1 : tous ces chemins sont sous terre : on aura donc trouvé un moyen de relier les n+1 cahutes par un chemin sous terrain
2 : tous ces chemins sont en l'air : on aura donc trouvé un moyen de relier les n+1 cahutes par un chemin en l'air
3 : il existe au moins un chemin sous terre et au moins un chemin en l'air : alors d'après P(n), si le chemin de P(n) était en l'air, on peut relier la (n+1)-ème cahute avec ce chemin par au moins un chemin en l'air, et idem si le chemin de P(n) est sous-terrain.
Dans les 3 cas, il existera un chemin qui relie les n+1 cahutes, et qui sera soit exclusivement en l'air, soit exclusivement sous terre. Ce qui prouve P(n+1)

Par récurrence, on a donc :
Le sorcier n'a pas besoin de changer de souliers !

Il peut même chaque fois qu'un foyer se crée, savoir quels chaussures prendre pour son prochain tour :
- si tous les nouveaux chemins sont sous-terrains : cuissardes
- si tous les nouveaux chemins sont en l'air : baskets
- sinon : il prend les mêmes chaussures qu'à la dernier création de foyer

 #21 - 18-01-2011 01:26:39

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Des hautts et des bas...

Merci merci pour vos réponses, et bravo. Vous méritez des mentions pour vos démonstrations :

- Gwen pour sa preuve multiple

- Tromaril pour sa preuve érudite

- Irmo pour sa preuve empathique

- Milou pour sa preuve confuse

- drhm pour sa preuve minimale

- looping pour sa preuve carrée

La mienne consistera à constater que les deux graphes (celui des souterrains et celui des surterrains) sont complémentaires et à utiliser le fait qu'entre un graphe et son complémentaire, l'un au moins est connexe.

 #22 - 18-01-2011 18:44:30

Tromaril
Habitué de Prise2Tete
Enigmes résolues : 20
Messages : 45

Des hauts ett des bas...

gasole a écrit:

Tromaril, tu veux dire "k-partite" je suppose... Bien joué :-)

En anglais dans le texte alors !

 #23 - 18-01-2011 20:49:51

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Des hhauts et des bas...

Non, non, c'est français.
BIPARTI, IE, BIPARTITE, adj.
A. Qui est partagé, divisé en deux parties.

Pour "bi" les deux existent, mais pour "k-" je n'avais jamais entendu que partite.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
P2T
26-01-2010 Enigmes Mathématiques
P2T
Balade sur un cube par McFlambi
29-06-2010 Enigmes Mathématiques
P2T
26+33+28+6+5=14 par grenoblois
30-05-2010 Enigmes Mathématiques
30-06-2013 Enigmes Mathématiques
P2T
Titius-Bode par cantalene
07-06-2008 Enigmes Mathématiques
P2T
05-09-2016 Enigmes Mathématiques
P2T
20-01-2012 Enigmes Mathématiques
P2T
Enigme de la marche par nana973
22-01-2014 Enigmes Mathématiques
P2T
07-01-2008 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete