![](/img/vague-bas-gauche.png) |
#1 - 14-01-2011 17:09:06
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
Des hauts et es 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.
#2 - 15-01-2011 00:00:59
- sterac
- Amateur de Prise2Tete
- Enigmes résolues : 25
- Messages : 9
Des hauts et dess bas...
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 es 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,937E+3
des hayts et des bas...
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
eDs 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 : 49
- Messages : 44
Des hats et des 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
des hauts et des nas...
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 hayts et 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
Dess 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 ? )
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 hauts et ded 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 : 203
Des hauts et dess 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 : 446
Des hauts et ddes 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é ). 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
ded hauts et des 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 de 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](img/smilies/smile.png)
#15 - 17-01-2011 11:46:09
- Milou_le_viking
- Professionnel de Prise2Tete
- Enigmes résolues : 30
- Messages : 446
des hauts et des bad...
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 : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Des hauts 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
es hauts et des bas...
Oui Milou, c'est mieux en effet... tu vois quand tu veux ![wink](img/smilies/wink.png)
#18 - 17-01-2011 13:36:59
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
des hauts et des baq...
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 : 446
des jauts 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](img/smilies/big_smile.png)
#20 - 17-01-2011 15:40:39
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Des hauts 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 hauts et des abs...
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 auts et 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 hauts te 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.
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |