ENIGMA 22: Etilarkov au pays des merveilles

Posté par monrow monrow

Bonsoir tout le monde !

Etilarkov vous présente un pays merveilleux où il a passé ses vacances la semaine dernière ... Arnansta !


Dans ce pays, on trouve 3 moyens de transport, pas plus

1) L'avion

2) Le TGV

3) Le bus

Ces trois moyens de transports sont disposés pour réaliser la liaison entre les différentes villes. Un contrôle de ces liaisons nous a donné le rapport suivant :

1) Un seul moyen de transport assure le contact entre deux villes.
2) Il n'y a pas une seule ville qui utilise les 3 moyens de transport.
3) Trois villes ne sont jamais reliées entre elles par le même moyen de transport.



A/ Une réponse justifiée serait obligatoire pour avoir son
B/ Après avoir posté votre réponse, cette dernière va être affichée. Ceci est du a une amélioration sur l'île.

Bon courage

Posté par gunnm gunnm

et bien disons qu'il y en a 3.

en premier lieu 3 fonctionne avec les conditions
chaque ville est reliée aux deux autres par 2 moyens de transports différents

disons 1-2 : Avion    2-3 : Train    et 3-1 : Bus
--> 1) est vérifié un seul moyen entre 2 villes
--> 2) est vérifié chaque ville n'utilise que 2 moyens de transports
--> 3) est vérifié on a pas 3 villes reliées par le mêmme moyen de transport.

ajoutons une quatrième ville,
pour vérifier 1) il ne doit y avoir qu'un seul moyen de transport entre 4 et chacune des 3 précédentes.
choisissons le moyen pour aller de 4 à 1:
2) chaque ville n'utillise que 2 moyens de transports donc ce sera soit l'avion soit le bus car 1 n'utilise pas le train.
choisissons l'avion; un probleme se pose car alors nous avons 3 villes reliées par le même moyen de transport: 4, 1 et 2.
On aurait le même probleme en choisissant le bus,
on ne peut vérifier le 3)

donc pas de 4.

mais ça m'a l'air un peu simple... j'ai raté un truc?



ma réponse: il y a 3 villes a Arnansta

Posté par jamo jamo

Bonjour,

je me permets de participer ...

J'ai l'impression qu'il manque quelquechose dans l'énoncé, non ?

Parce que si on dispose les villes sur les sommets d'un polygone, le nombre de villes ne me semble pas limité !

Il n'aurait pas fallu rajouter que chaque ville doit être reliée à chaque autre ville ?

Posté par Nofutur2 Nofutur2

Bien sûr dans ce problème, il faut tenir compte des symétries.
J'essaie des définir le nombre de solutions type selon le nombre de points.

Pour 3 points, il y a deux types de solutions
AB=1, AC=1, BC=2
AB=1, AC=2, BC=3

Pour 4 points,
AB=1, AC=1, BC=2, DA=2, DB=2, DC=1 (3 fois 1, 3 fois 2)
Cette solution est impossible car les trois moyens de transport doivent être utilisés.
AB=1, AC=1, BC=2, DA=3, DB=1, DC=1(4 fois 1, 1 fois 2, 1 fois 3)
Il y a donc un seul type de solution à 4 villes.

A partir de cette solution si j'essaie d'insérer un 5ème point E,
EA=1 ne permet pas de trouver EB
EA=2 est impossible
EA=3 permet ED=1, mais impossibilité trouver EB
EA=3 ne permet pas ED=2 et ED=3 .

Le maximum de villes est donc de 4.

Posté par rogerd rogerd

Bonjour Monrow et merci pour ce retour sur l'île .

Deux propriétés préliminaires:
1) La liaison entre deux villes est nécessairement directe. Si on allait de V1 à V2 en passant par V3,alors V1,V2,V3 seraient reliées par le même moyen de transport.
2) D'une ville donnée ne peuvent partir que 2 lignes au plus utilisant un moyen de transport donné. En effet, si l'on suppose que V1 est reliée à V2,V3,V4 par avion, aucune des liaison V2V3,V3V4,V2V4 ne peut se faire par avion (condition 3). Par exemple V2V3 se fait en bus, donc V3V4 aussi (condition 2 au départ de V3) et de même V4V2 (condition 2 à partir de V4). Mais alors V2V3V4 sont deux à deux reliées par bus, contradictoire avec la condition 3.

Comme le nombre de moyens de transport à partir d'une ville est limité à 2, le nombre de lignes partant d'une ville est donc limité à 4.

Il y a donc au maximum 5 villes.

Montrons maintenant que:

Il est possible d'avoir 5 villes.

Par exemple, sans utiliser le TGV:

Par avion: V1V2, V1V3, V2V4, V3V5, V4V5
Par bus: V1V4, V1V5, V2V5, V3V4, V2V3

Posté par monrow monrow

jamo>> Je pense que c'est clair d'après l'énoncé que toutes les villes sont reliées entre elles ! Et ça a été posé de la même façon dans d'autres endroits.

Posté par lo5707 lo5707

Bonjour,

Le maximum est 4 villes.

Par exemple:
[img1]

_{Je l'avais déjà donné en JFF:}

Posté par lo5707 lo5707

l'image n'est pas passée:

Posté par plumemeteore plumemeteore

bonjour
d'abord, une ville ne peut pas être reliée à trois autres par le même moyen de transport
supposons que A soit reliée à B, C et D par T
B ne pourrait être relié par T ni à C ni à D (triangle ABC ou ABD?); donc elle leur est reliée par le même moyen de transport U
mais alors C et D ne peuvent pas être reliées p
ar T (triangle ACD ?), ni par U (triangle BCD ?) ni par un troisième moyen V (trois moyens pour C et D ?)
cela établit qu'une ville ne peut pas être reliée à cinq autres et qu'il n'y a pas six villes

supposons qu'il y ait cinq villes; chacune est reliée à deux autres par un moyen de transport et encore à deux autres par un autre moyen de transport
soit A reliée à B et à C par T et à D et à E par U
T peut relier B indifféremment à D ou à E, mettons à D
B est reliée à C et à E par U ou par le troisième moyen V
si B est reliée à C et à E par U, D et E ne peuvent être reliées par V (trois moyens pour D et C ?); elles sont donc reliées par T
C et D seront alors reliées par U
cette solution ne respecte pas l'énoncé car il n'y a que deux moyens de transport
si B est reliée à C et à E par V, E doit être reliée par V à D ou à C; à D cela donnerait trois moyens de transports différents à D; à C, cela formerait un triangle BCE interdit

avec quatre villes A B C D
A est reliée à B et à C par T et à D par U
si la relation DC est V, la relation CB est V et la relation BD est U
si la relation DC est U, la relation CB est U et la relation BD ne pourrait être V; il n'y aurait pas trois moyens de transport
si la relation DC est T, BC devra se charger du transport V et BD sera T

solution : quatre villes
AB : T
AC : T
AD : U
variante 1
DC : V
CB : V
BD : U
variante 2
DC : T
CB : V
BD : U

Posté par link224 link224

Salut monrow!

Le nombre maximal de villes que compte Arnasta est 4.
On aura par exemple : Bus entre les villes A et B, B et C, C et D, D et A; puis avion entre A et C et TGV entre B et D.

Du fait qu'une ligne de transport relie obligatoirement 2 villes, il est impossible de trouver une configuration qui marche pour 5 villes. Par exemple :
TGV entre A et D, A et C, C et D
Avion entre E et C, E et D, B et D, B et C
Bus entre A et E, E et B, A et B
Les propriétés 1 et 2 sont vérifiées, mais pas la 3 (villes A, B et E reliées par le bus).

Donc le nombre maximal de villes est 4! (En espérant que la justification convienne).

@+ et merci pour l'énigme.

Posté par Eric1 Eric1

j'ai bien hésité...


je me demandais au début : y a t-il nécessairement un moyen de transport entre deux villes.
En fait, si tel était le cas, on ne met pas un seul transport entre les villes (ou une chaine alternée de deux transports différents), et on a un nombre de villes infinie... Donc apparemment, ce n'ets pas ça.

Il faut donc comprendre la phrase comme

On peut dans ce cas ne mettre que 3 villes (A,B,C), avec AB: avion, BC: bus, et AC: TGV

En effet, si l'on essaie de mettre une quatrième ville,  on ne vérifie plus soit la 2ème soit la 3ème contrainte.

Posté par infophile infophile

Bonjour



Démonstration

L'énoncé ne precise pas si les 3 transports doivent impérativement être utilisés, je vais donc supposer que c'est le cas.

Appelons , , et les dîtes villes. Montrons qu'il existe une disposition qui assure le contrôle des liaisons de celles-ci.

Un seul moyen de transport assure le contact entre deux villes.
Il n'y a pas une seule ville qui utilise les 3 moyens de transport.
Trois villes ne sont jamais reliées entre elles par le même moyen de transport.

Nous représenterons les 3 moyens de transports par 3 couleurs différentes : rouge, bleu et jaune que l'on n'attribuera pas spécifiquement aux moyens de transports puisqu'ils jouent le même rôle.

Formons et en rouge, alors en vertu de ne peut-être rouge. On décide de lui donner la couleur bleu. Relions maintenant à , d'après ne peut pas être jaune. De même pour . Ainsi par symétrie on peut supposer bleu et rouge, mais alors le dernier raccord devant être jaune on a un problème au nœud où se raccorde les trois couleurs . Donc et sont tous deux rouges (impossible pour bleu car la liaison serait bleu ). Et là la diagonale jaune convient.

Formons bleu et rouge. ne peut donc pas être jaune, on l'impose rouge. Donc ne peut pas être rouge. S'il était bleu, sachant qu'il faut utiliser un raccord jaune, on aurait ou jaune, impossible d'après   au nœud et . Donc est jaune. ne peut pas être bleu pour vérifier en , ni jaune car ensuite si était jaune la liaison   serait jaune   et si bleu ou rouge on aurait un problème de type aux extrémités de . Donc est rouge et par suite également pour vérifier .

Dans les deux configurations on a la même façon de relier les villes, on prend 4 fois le même transport et une fois de chaque les deux autres.



Montrons alors qu'il est impossible de relier 5 villes avec de telles contraintes.

Reprenons les configurations à 4 points. Et plaçons une cinquième ville représentée par le point au dessus du plan contenant le quadrilatère (pour visualiser).

et ne peuvent pas être bleus d'après ni tous deux jaunes sinon jaune . Donc un au moins des segments est rouge, mettons . ne peut pas être jaune d'après ni rouge d'après donc bleu par élimination. De même n'est ni jaune ni rouge pour les mêmes raisons, donc serait bleu. Mais alors serait bleu ce qui contredit .

ni ne peuvent être jaune d'après , ni tout deux bleus d'après . Supposons qu'ils soient tout deux rouges, alors puisque et ne peuvent être bleus d'après , ils sont soit tous les deux jaunes - auquel cas serait jaune absurde - soit un des deux au moins est rouge et toujours d'après ou est rouge, absurde. Donc par symétrie on peut supposer rouge et bleu. On ne peut alors pas avoir de segment jaune issu de . Ainsi n'est pas jaune, ni bleu d'après ce qui précède, ni même rouge car le serait ! D'où la contradiction.



Dans les deux cas il est impossible de relier la cinquième ville au réseau. CQFD.

Remarque : en utilisant seulement deux types de transport il est possible de relier 5 villes entre elles selon le schéma suivant :



Bien sûr l'ajout d'un sixième point est impossible, on pourrait prendre le symétrique du tétraèdre par rapport au plan contenant le quadrilatère ABCD mais on aurait un soucis de type (3) sur la grande diagonale [ED].

Merci pour l'énigme

Posté par plumemeteore plumemeteore

rebonjour
dans mon examen de quatre villes, le premier cas ne donne pas une solution : tout moyen de transport pour la relation BD fait contrevenir aux règles
finalement seul le troisième cas est bon; cependant en copiant la récapitulation, j'ai écrit BD = U au lieu de T comme dans la démonstration
AB, BC, CD, DA : un moyen de transport
AC : un deuxième moyen de transport
BD : le troisième moyen de transport
on obtient un quadrilatère dont les côtés sont pareils et dont les deux diagonales apportent chacune une nouveauté

Posté par manpower manpower

Bonjour,

aaah... la théorie des graphes...

je vais noter A=avion, B=bus et T=TGV.

La condition 1 interdit des liaisons multiples et ne nous intéressera plus par la suite.
Le problème est facile pour 3 villes (mais délicat pour 2 villes!).

Pour 4 villes, chacune des villes est reliée aux 3 autres, donc il y a au moins un moyen de transport que l'on retrouve 2 fois au départ de chaque ville (condition 2).
En supposant que les villes sont disposées en carré (ce qui ne pose aucun problème), disons que le coin supérieur gauche (1) possède des liaisons du type A, A, B, alors la liaison 2-3 et 3-4 ne peuvent être que du type A ou B (condition 2).
Le cas "Deux B" est à exclure sinon 2-3-4 contredirait la condition 3, "un A et un B" conduit à l'absence de T impossible pour 3, donc les liaisons 2-3 et 3-4 sont également assurées par "Deux A". Reste T pour la liaison 1-3 et aucune contradiction.


Les moyens de transport étant tous mathématiquement équivalents, le graphe est unique (à permutation des différents moyens de transports près).

On s'attaque alors au cas de 5 villes:
l'ajout d'une ville (5), impose 4 nouvelles liaisons 1-5,2-5,3-5,4-5.
La démonstration précédente permet de partir de "l'unique" cas pour n=4 et de tester les différentes configurations.
La condition 2, permet d'exclure des possibilités:
1-5: A ou T (B exclus)
2-5: A ou B
3-5: A ou T
4-5: A ou B
Ensuite, c'est assez long (16 cas à tester) mais en utilisant la condition 2, on s'assure qu'aucune ne convient.
Deux A ne peuvent convenir sinon la condition 2 serait mise en défaut (un triangle prenant 5 et deux sommets du carré). Deux B non plus, avec le triangle 2-4-5 et enfin deux T non plus avec le triangle 1-3-5. Donc, nous devrions compléter 4 liaisons avec 3 moyens de transport différents, ce qui est impossible.

Conclusion: Il y a au plus 4 villes.

Enfin, pour conclure une petite faille dans l'énoncé (ou alors c'est un piège?):


Avec deux moyens de transports et les mêmes conditions, on peut parfaitement proposer un système à 5 villes (par exemple, mais pour tout polygone avec un nombre impair de côtés, c'est possible).


Merci pour cette énigme.

Posté par bizbiz bizbiz

A ARNANSTA, il y a QUATRE villes .

Par exemple :

Posté par piepalm piepalm

Affectons une couleur à chaque moyen de transport: on est donc ramené au problème suivant: nombre maximum de points reliés par des segments colorés (3 couleurs possibles), tels qu'il n'y ait pas de triangle monochrome, et pas de point tricolore.
Pour trois points, on a deux configurations possibles: un triangle tricolore, ou bien bicolore avec deux cotés d'une couleur et le troisième d'une autre.
Pour étudier les configurations possibles avec 4 points, il faut partir d'une configuration possible à trois points et ajouter le quatrième: on n'obtient aucune configuration valide à partir d'un triangle tricolore : si ABC est le triangle et D le 4çme point, AD BD et CD ne peuvent être de la même couleur sans qu'il y ait un triangle monochrome, ni de trois couleurs différentes sans que D soit un point tricolore: il y en a donc deux de la même couleur, par exemple AD et BD, et cette couleur n'est pas celle de AB; c'est par exemple celle de AC: mais alors B serait tricolore).
Par contre, on obtient trois configurations possibles à partir d'un  triangle bicolore, topologiquement équivalentes aux dispositions suivantes:
- un carré tricolore avec 4 cotés de même couleur et les deux diagonales chacune d'une autre couleur
- un carré bicolore avec 4 cotés de la même couleur et les diagonales de la seconde
- un carré bicolore avec 3 cotés de la même couleur et le quatrième et les diagonales de la seconde.
De la même façon, pour rechercher les configurations possibles à 5 points on cherche à ajouter un point aux configurations possibles à 4 points.
Si l'on part d'une configuration où les 4 cotés sont de la même couleur, on ne peut obtenir de configuration valide: en effet les 4 premiers points sont déjà bicolores, et les segments les reliant au 5ème point ne peuvent être que de l'une de ces couleurs, et puisque les deux segments reliant ce point aux extrémités d'une diagonale ne peuvent être tous les deux de la couleur de la diagonale, il y en a un par diagonale, de la couleur des cotés; ces deux segments aboutissent aux extrémités d'un  coté, d'où impossibilité.
La seule configuration possible (obtenue en partant de la troisième configuration du carré) est alors équivalente à un pentagone convexe bicolore dont les cotés sont d'une couleur, et les diagonales d'un autre.
Si l'on cherche à ajouter un 6ème point on aboutit alors à une impossibilité: en effet les 5 points sont déjà bicolores, et les segments qui vont les relier au sixième ne peuvent être que de l'une des deux couleurs déjà employées. Soit ABCDE le pentagone et F le point ajouté; si CF est de la couleur des cotés, BF et DF doivent être de la couleur des diagonales, mais alors BDF est monochrome; de même si CF est de la couleur des diagonales, AF et BF doivent être de la couleur des cotés, mais alors ABF est monochrome.
Le nombre maximal de villes est donc 5

Posté par Chewingum Chewingum

Salut !

Selon moi, la réponse est une infinité de villes
Schéma explicatif :

Posté par kiko21 kiko21

Bonjour,

Le nombre maximal des villes qui constituent Arnansta est
Il est impossible d'ajouter une quatrième ville, car dans ce cas, chaque ville possède 3 liaisons et on ne peut alors respecter simultanément la condition 2 (2 moyens de transport maxi) et la condition 3 (3 moyens de transport différents dans un triplet de ville).

Merci et A+, KiKo21.

Posté par 1emeu 1emeu

Bonjour,

Si j'ai bien compris l'énoncé, on a ici affaire à un problème de coloriage d'arêtes dans un graphe complet.

On notera n le nombre de villes maximum recherché.
Le théorème de Ramsey affirme que n est bien fini (n serait fini même sans la contrainte "chaque ville utilise au max deux moyens de transport")


montrons tout d'abord que n>=5 :
On peut colorier les arêtes du graphe complet K5 aveec deux couleurs de la façon suivante : si on représente K5 comme une étoile inscrite dans un pentagone, on colorie les arêtes du pentagone avec la couleur 1 et les arêtes de l'étoile avec la couleur 2.
Ce coloriage vérifie les contraintes de l'énoncé, donc on a bien n>=5

Montrons à présent que n<6.
Pour cela, on va prouver qu'il n'existe pas de coloriage des arêtes de K6 avec 3 couleurs qui vérifie les contraintes de l'énoncé :

- il n'existe pas de coloriage avec 2 couleurs exactement des arêtes de K6 tel qu'il n'y ait pas de cycle d'ordre 3 (c'est un cas particulier bien connu du théorème de Ramsey)

- Supposons qu'il existe un tel coloriage avec exactement 3 couleurs, alors on peut montrer qu'il existe un sommet de K6 tel que le graphe induit par la suppression de ce sommet donne un coloriage des arêtes de K5 vérifiant les contraintes de l'énoncé avec exactement 3 couleurs. On montre ensuite qu'il n'existe pas de coloriage avec exactement 3 couleurs des arêtes de K5 vérifiant les contraintes de l'énoncé. Pour cela, on peut regarder cas par cas les différentes distributions possibles du nombre d'arêtes des différentes couleurs. En effet K5 possède 10 arêtes, et 10=8+1+1=7+2+1=6+2+2=6+3+1=5+3+2=5+4+1, ce qui fait 6 cas au total à étudier.

Par conséquent le nombre de villes maximal de Arnansta est 5 !!


Je n'ai pas mis les détails techniques de la preuve car il est indiqué qu'il faut une justification et non une démonstration (et que c'est déjà long ), mais je peux les donner sur demande.

Il y avait très certainement une démonstration plus simple, mais je ne l'ai pas vue...

Merci pour l'énigme ,

1emeu

Posté par geronimo 652 geronimo 652

Bonjour,
La réponse que j'ai trouvé me paraît trés faible mais enfin essayons tout de même:
D'après les indications, rien n'explicite le fait que ces villes soient alignées. Or trois villes non alignées impliquent trois liaisons... contre deux si elles étaient alignées! Je ne sais pas si c'est ça la clef de l'énigme mais sans ça (elles seraient toutes alignées) il y aurait une infinité de villes constituants Arnansta... Donc d'après moi, 4 villes maximum constituent Arnansta. Démonstration avec un schéma (certainement très archaïque)

0-------^Bus-------0
              
   ^{Avion       TGV                    Avion}          
                 0               Bus               0

0= ville et il y a une liaison entre chaque 0 dont le moyen de transport est indiqué
Ici cela fonctionne on a 4 villes. Ajoutons-en une!


0            ^Bus          0

       ^{Avion            TGV     avion}


                  0                    Bus                  0
         ^???
0

et là, c'est la catastrophe! Avec 5 villes, on est bloqué puisque l'on a une croix qui se forme avec les diagonales du parallélogramme et deux de ces côtés! Or : Trois villes ne sont jamais reliées entre elles par le même moyen de transport. Comme les trois moyens de transport sont pris, on ne peut plus rien faire!

Donc 4 villes constituent Arnansta... De plus, même si les villes sont alignées, cela fonctionne tout de même. Si l'on a trois villes, rien ne nous empêche de liés la 1ère et la dernière!
voilà et désolé pour la longueur du message, c'est mon p'tit défaut de faire des longues démonstration! Merci pour ce jeu et à +

Posté par totti1000 totti1000

On notera en rouge le reseau des trains, en vert celui des avions et en bleu celui des bus...
Si on suppose que LES TROIS moyens de transport sont utilisés.
Pour trois villes on peut avoir le cas n°1.
Pour quatre villes il n'y a qu'une seule possibilité (on peut cependant intervertir les couleurs...), c'est celle où un moyen de transport est utilisé pour 4 liaisons,
et les deux autres pour une seule liaison... Cas n°2.
Enfin pour cinq villes on rajoute 4 liaisons au cas n°2...
Dans ce cas BE et DE ne peuvent pas etre vertes, supposons BE rouge, alors AE est obligatoirement verte, et donc CE obligatoirement rouge et enfin
DE oblgatoirement bleu. Ceci qui contredit l'hypothèse 2). Il en va de meme si on suppose BE bleu... Dans tous les cas il est impossible de le faire pour 5 villes.
Cependant si 'on oblige pas de se servir des trois moyens de transport on peut avoir le cas n°4...
Et ensuite on ne peut pas rajouter une ville F, car ceci dans tous les cas contredit soit l'hypothèse 2) soit la 3)...

CONCLUSION:
L'enigme ne dit pas clairement si on doit se servir des trois moyens de transport meme si il est dit: "Dans ce pays, on trouve 3 moyens de transport" ...
Si on doit les utiliser tous les trois, le nombre maximal de villes de Arnansta est 4.
Si l'on impose pas de se servir des trois moyens alors le nombre maximal est 5...

Posté par dhalte dhalte

Bonsoir.

Appelez-moi bourrin si vous voulez, mais je n'ai pas trouvé d'argument convainquant qui éviterait la recherche exhaustive.

Alors j'ai trouvé une seule configuration possible avec cinq villes et aucune avec six villes.

Raisonnement (si on peut dire) : partir des configurations à n villes (en démarrant à n = 3) et ajouter à chacune une ville puis tester toutes les possibilités de rajouter un arc entre cette nouvelle ville et une ancienne (parfois judicieusement choisie pour ne pas prolonger le supplice) qui respecte les contraintes données.

Je fournis ci dessous la preuve en 10 dessins et en couleurs.

Horreur, le site n'accepte que 3 fichiers, de 60 Ko maximum chacun...

Vous n'aurez donc que les 3 suivants :


Les seules configurations à trois villes


A partir de la première, on dérive les configurations à quatre villes. Je ne montre que la première dérivation.


Dans un raccourci saisissant indépendant de ma volonté, la solution à cinq ville. Par permutation des villes, on arrive à une jolie étoile de David.

Et puis les configurations à six villes depuis la solution à cinq villes, que je ne peux pas vous montrer hélas, qui toutes aboutissent à une impossibilité.

C'est peut-être laborieux, grossier. Mais à chacun selon ses possibilités.

Posté par Poldenys Poldenys

Enigma 22
Je représente le réseau des villes de Arnansta par le triplet (n,p,q)
n laisons par bus , p par train , q par avion (les 3 moyens de T. jouant des rôles symétriques ,n,p,q seront en ordre décroissant )
Pour 3 villes 2 types sont possibles (1,1,1) et (2,1,0) . (3,0,0) étant
interdit par la clause 3 (3 villes non reliées par un même moyen )
Pour 4 villes 3 types sont possibles (3,3,0) , (4,1,1) et (4,2,0) .
n=5 (ou supérieur) est rendu impossible par la clause 3
Les types (3,2,1) et (2,2,2) sont rendus impossibles par la clause 2 (une
    même ville ne peut pas recevoir les 3 types de transport)
Pour 5 villes il faut 15 liaisons au total et 4 villes choisies au hasard
parmi les 5 doivent satisfaire à l'un des 3 types ci-dessus .
    Seul le type (3,3,0) permet une extension au type (5,5,0) selon la
configuration du pentagone complet : 5 liaisons par 1er moyen suivant les
côtés du pentagone convexe et 5 par 2è moyen suivant les côtés du pentagone
étoilé .(2 moyens de transport seulement !)
    Dans les types (4,1,1) et (4,2,0) c'est la clause 2 qui rend impossible
toute extension .
    Enfin pour plus de 5 villes il faut trouver une extension du seul type
possible au rang 5 ,(5,5,0) ce qui est impossible , en effet la clause 2
rend impossible l'introduction du 3è moyen de T.et la clause 3 rend
impossible l'adjonction de plus de 2 liaisons prises dans les 2moyens
existants.   Donc CINQ villes à Arnansta et DEUX moyens de Transport .

Posté par veleda veleda

bonjour monrow

je note A,B,T les trois moyens de transports et n le nombre de villes de Arnansta
*n=2 pas de problèmes V₁etV₂peuvent être reliées par A,B ou T
*n=3 pas de problème non plus
* |(1)(2)(3)
(1)|-*A*B
(2)|A*-*B
(3)|A*B*-
par exemple
*n>3
une ville quelconque utilise au plus deux moyens de transport donc  par exemple les liaisons de V₁vers V₂, V₃ et V₄ sont du type A,A,A ou A,A,B
supposons qu'il existe une liaison A,A,A
(1)<-A->(2)
(1)<-A->(3)
(1)<-A->(4)
la liaison (2)<->(3) ne peut se faire par A donc elle se fait par B ou T ,supposons qu'elle se fasse par B alors la liaison(3)<->(4) doit se faire par A ou B sinon il y aurait les 3 moyens de transport en(3) mais A est à exclure sinon (1),(2),(3) sont reliées par A donc c'est B
la liaison(2)<->(4) se fait donc nécessairement par A ou B mais ces deux moyens de transport sont à rejeter :
en effet si l'on choisit A alors (1),(2),(4) sont reliées par A  impossible
et si l'on choisit B alors (2),(3),(4) sont reliées par B
  une ville  donnée ne peut pas être reliée à plus de deux autres villes par le même moyen de transportcomme par une ville il passe au plus deux moyens de transport une ville est reliée au plus à 4 autres villes donc n5
il reste à montrer que n peut effectivement être égal à 4 et 5

d'aprés ce qui précéde  les liaisons d'une ville avec 4 autres ne peuvent être que de la forme A,A,B,B

*|(1)(2)(3)(4)(5)
(1)|-*A*A*B*B
(2)|A*-*B*B*A
(3)|A*B*-*A*B
(4)|B*B*A*-*A
(5)|B*A*B*A*-
par exemple
donc le maximum de villes est 5

merci pour cette énigma


  

Posté par ThierryMasula ThierryMasula

Bonsoir monrow,

On peut facilement relier trois villes avec les contraintes de l'énoncé.
Ces trois villes sont impérativement reliées par les trois moyens de transport pour respecter la condition 3)
Lorsqu'on place une quatrième ville, les choses se corsent... En la reliant à l'une des trois villes déjà connectée, il faut choisir l'un des deux moyens de transport déjà utilisé par cette ville (règle 2) et on ne pourra donc pas établir de liaison avec les deux autres villes sans violer la règle 3.

Il y a donc trois villes au maximum à Arnansta.

Posté par karatetiger karatetiger

salut alors je dirais 4 je sais pas si mon explication va etre valable.

1T2
1T3
2A3

1T2
1T4
2A4

2A3
2A4
3B4

1T2
1T5
2A5

1T3
1T4
3B4

1T3
1T5
3B5

1T4
1T5
4 ?? 5  on peut pas mettre T problème dans la boucle 145, on ne peut pas mettre A problème dans la boucle 245 et on ne peut mettre B problème dans la boucle 345

Voila merci pour l'énigme

Posté par monrow monrow

ENIGME CLOTUREE

Et voilà une petite énigme sur la théorie des graphes !

Beaucoup sont ceux qui sont tombés dans le piège ! Tous les moyens doivent être utilisés et toutes les villes sont reliées entres elles sinon à quoi sert de citer les 3moyens de transport?

33% de réussite c'est pas très fameux, mais bon, vous avez bien eu un grand nombre d'énigmes ce mois là

Merci pour votre participation

Posté par veleda veleda

bonsoir monrow
je ne conteste pas du tout mon poisson mais le texte ne disait pas qu'il fallait impérativement utiliser les 3 moyens de transport et dans ce cas il était plus simple de s'arrêter à 4 que de montrer qu'avec deux moyens de transport on pouvait relier 5 villes

Posté par kioups kioups

Perso, je n'ai pas compris les propositions 1 et 3... Donc, dans le doute....

Posté par rogerd rogerd

Bonsoir Monrow

J'ai beau lire et relire l'énoncé, je ne vois pas où l'on dit qu'il faut que les trois moyens de transport soient utilisés!

Posté par monrow monrow

rogerd>> c'est vrai que ce n'est pas signalé sur l'énoncé, mais je pense que déjà citer les 3 moyens de transport c'est qu'on les utilise tous sinon à quoi sert de les citer tous les trois? j'aurais du mentionner que deux !

Posté par monrow monrow

Désolé veleda je viens de voir: même réponse que rogerd

Posté par rogerd rogerd

Il y avait un piège dans l'énoncé:

Dans un pays qui dispose de trois  moyens de transport , il y a des villes où on n'utilise que deux de ces moyens de transport.

C'est le type de piège qu'on trouve fréquemment dans les énigmes de l'île des maths: ajoût d'une hypothèse qui ne sert pas.

Curieusement, tu pénalises ceux qui ne sont pas tombé dans le piège...

Posté par monrow monrow

rogerd>> La source de cette énigme a le même énoncé et avec la même réponse qui est 4 villes, y avait pas de données superflues

Posté par rogerd rogerd

Oui ou non: est-il possible de relier 5 villes en respectant l'énoncé?

Posté par rogerd rogerd

Monrow: lis bien l'énoncé:

Dans un pays, on trouve 3 moyens de transport..

On ne dit pas que toutes les villes utilisent les trois moyens de transport!

Posté par rogerd rogerd

Mille excuses, Monrow!

Je vois mon erreur: les villes concernées constituent l'ensemble des villes de l'île. Si un moyen de transport n'était pas utilisé entre ces villes, il ne le serait donc pas du tout sur l'île. Or l'énoncé dit clairement qu'il y a trois moyens de transport.

Merci pour ta patience!

Posté par karatetiger karatetiger

pourquoi un poisson?

Posté par veleda veleda

bonjour à tous,
>>morow
une remarque amusante :dans le village où je suis en vacances il y a une liaison par train avec la petite ville la plus proche en semaine et le dimanche c'est un autobus donc on utilise les deux moyens de transport mais pas en même temps
ce n'est pas Arnansta il n'y a pas de liaison aérienne
avec le texte tel qu'il fallait le comprendre il n'y a donc que 3 ou 4 villes
bon week-end à tous

Posté par Eric1 Eric1

Quelqu'un peut m'expliquer le point 3?

Posté par Eric1 Eric1

parce que selon, 3 villes ABC sont reliées si il y a au moins deux liaisons entre celles-ci

Posté par karatetiger karatetiger

si tu prends 3 villes A, B, C; chaque ville est relié à chacune des deux autre tu peux comparé cela à un graphe complet. Le point 3 veux dire que si tu va de A vers B puis de B vers C puis de C vers A alors tu utilises au moins deux moyens de transport

Posté par monrow monrow

karatetiger>> Ta démonstration n'est pas claire à mon avis, j'ai pas compris tes notations et ton raisonnement n'est pas présent

Veleda>> J'espère que tu passes de bonnes vacances

Eric1>> Ca veut dire que si tu as une ville A reliée à B C et D alors on peut pas avoir le même moyen qui relie A à B,à C et à D

Posté par karatetiger karatetiger

Voila ce que veux dire le point 3

Posté par karatetiger karatetiger

Lol pas clair mais c'est très clair j'avoue que en relisant à part dans ma tête il n'y a rien de clair,tampis

Posté par Eric1 Eric1

OK. Donc j'ai mal interprété le truc...

Posté par geronimo 652 geronimo 652

Bonjour morow,
je ne comprends pas mon poisson...démonstration pas assez rigoureuse?
Ceci dit je ne consteste pas... si j'ai un poisson c'est qu'il y a une erreur!

Posté par geronimo 652 geronimo 652

excuse moi j'ai un petit peu "transformer" ton pseudo...désolé ce n'était pas volontaire...

Posté par geronimo 652 geronimo 652

enfin si j'ai une erreur de démonstration, je ne vois pas où car je trouve la bonne réponse...
dans l'attente d'une réponse...
geronimo 652

Posté par monrow monrow

Corrigé !