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...

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.

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.

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

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

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.

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

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.

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

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

gasole a écrit:

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

En anglais dans le texte alors !