Inscription / Connexion Nouveau Sujet
Niveau 3 *
Partager :

Enigmo 218 : Transports maritimes à l'archipel des maths

Posté par
jamo Moderateur
04-09-10 à 13:18

Bonjour tout le monde,

Tom_Pascal, président de l'archipel des maths, souhaite établir un système de transports par bateaux entre les îles.
Chaque île concernée par ce réseau de transports doit vérifier certaines conditions.

Tout d'abord, chaque île ne doit être en liaison qu'avec trois autres îles au maximum.
De plus, en partant de n'importe quelle île, il doit être possible de se rendre sur n'importe quelle autre île en ne faisant qu'un seul changement au maximum.

Par exemple, le réseau des 6 îles vertes ci-dessous convient : aucune île n'est reliée à plus de 3 autres, et chaque île est atteignable des 5 autres avec un changement au maximum.
Mais l'exemple des 6 îles rouges ne convient pas : la ville 6 est reliée à 4 villes, et il n'est pas possible d'aller de l'île 1 à l'île 2 avec un seul changement.

Question : Quel est le nombre maximal d'île dans ce réseau de transports, et comment sont-elles reliées entre elles ?

Pour la réponse, je veux tout d'abord le nombre maximal d'îles.
Ensuite, l'idéal serait de répondre en image pour décrire le réseau.
Mais sinon, en numérotant les îles et en me donnant, pour chacune d'entre elles, les numéros des îles auxquelles elles sont rattachées, je devrais m'en sortir (car en fait, la disposition des îles n'a pas grande importance).

Je mets 3 étoiles pour la difficulté, car je crois que la recherche du maximum n'est pas facile ... mais je me trompe peut-être !

Bonne recherche !

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
Nofutur2
re : Enigmo 218 : Transports maritimes à l'archipel des maths 04-09-10 à 13:54

perduJe pense que la limite maximale est de 7 îles.

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
godefroy_lehardi Posteur d'énigmes
re : Enigmo 218 : Transports maritimes à l'archipel des maths 04-09-10 à 14:21

perduBonjour Jamo,

Je tente un maximum à 8.

1 est relié à 2 5 8
2 est relié à 1 3 6
3 est relié à 2 4 8
5 est relié à 1 4 6
6 est relié à 2 5 7
7 est relié à 4 6 8
8 est relié à 1 3 7

Désolé mais je n'ai pas pu faire d'image.

Merci beaucoup.

Posté par
LeDino
Bonjour 04-09-10 à 14:45

perduBonjour,

Je pense que le réseau comptera au plus 8 îles.
Voici ci-dessous en image une disposition possible.
Merci pour l'énigme ...

Bonjour

Posté par
Rodolphe
re : Enigmo 218 : Transports maritimes à l'archipel des maths 04-09-10 à 15:11

perduEnigmo 218 : Transports maritimes à l\'archipel des maths

Nofutur2 et godefroy_lehardy m'ont mis la pression !

Ma proposition est donc celle-ci avec 8 îles et 12 chemins.

Posté par
Chaosleague
re : Enigmo 218 : Transports maritimes à l'archipel des maths 04-09-10 à 16:09

perduBonjour,

Un total de 8 iles
1 attaché à 2,3,4
2 attaché à 1,6
3 attaché à 1,5,8
4 attaché à 1,5,7
5 attaché à 3,4,6
6 attaché à 5,4,7
7 attaché à 8,6,4
8 attaché à 7,3

Voila !

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
rezoons
re : Enigmo 218 : Transports maritimes à l'archipel des maths 04-09-10 à 17:37

perduBonjour ,

j'ai réussi a trouver une solution avec 8 îles et a démontrer que c'était impossible avec 9 îles et plus. Mais autant je suis sur pour les 8 îles autant j'ai peur d'avoir ommis un ou deux cas dans ma démonstartion. Mais je me lance avec 8 îles:

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
totti1000
re : Enigmo 218 : Transports maritimes à l'archipel des maths 04-09-10 à 18:10

gagnéSalut Jamo,
Je propose un maximum de 10.

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
plumemeteore
re : Enigmo 218 : Transports maritimes à l'archipel des maths 05-09-10 à 00:31

gagnéBonjour Jamo.
Le maximum est de dix îles.
Par numéros :
1 -> 9 3 2
2 -> 10 4 1
3 -> 1 5 6
4 -> 2 6 7
5 -> 3 7 10
6 -> 4 8 3
7 -> 5 9 4
8 -> 6 10 9
9 -> 7 1 8
10 -> 8 2 5
Les numéros sont groupés en pairs et impairs. Dans chaque groupe, chaque numéro est relié à ses deux voisins (9 et 1 sont voisins; 10 et 2 son voisin. En outre, chaque numéro impair est relié à son double modulo 10 (5 étant relié à 10).
Quinze liaisons directes : 1-3 3-5 5-7 7-9 9-1 2-4 4-6 6-8 8-10 10-2 1-2 3-6 5-10 7-4 9-8
Visuellement : on trace deux pentagones; on numérote les sommets du premier de A à E en passant d'un sommet à l'autre; on numérote les sommets du deuxième de A' à E' en sautant chaque fois un sommet.

Calcul du maximum.
Nombre pair : 2n
nombre de paires : 2n*(2n-1)/2 = 2n²-n
maximum de chemins simples : 2n*3/2 = 3n
minimum de paires non reliées : 2n²-n-3n = 2n²-4n
longueur minimale en chemins simples de la somme des trajets entre paires non reliées : 4n²-8n
un chemin simple peut participer au maximum à quatre parcours doubles.
3n*4 4n²-8n
4n²-20n 0
4n² 20n
n 5
soit dix îles.
Nombre impair : 2n+1
nombre de paires : (2n+1)*2n/2 = 2n²+n
maximum de chemins simples : (2n+1)*3/2 - 1/2 = 3n+1
minimum de paires non reliées : 2n²+n-3n-1 = 2n²-2n-1
longueur minimale en chemins simples de la somme des trajets entre paires non reliées : 4n²-4n-2
un chemin simple peut participer au maximum à quatre parcours doubles.
(3n+1)*4 4n²-4n-2
4n²-16n-6 0
n 5 mais n peut être 4
soit neuf îles.

La solution avec dix îles ne peut donc pas être améliorée.

Posté par
plumemeteore
re : Enigmo 218 : Transports maritimes à l'archipel des maths 05-09-10 à 00:32

gagnéDans la représentation visuelle, on relie bien entendu les paires de sommets ayant les mêmes lettres.

Posté par
Noflah
re : Enigmo 218 : Transports maritimes à l'archipel des maths 05-09-10 à 01:45

perduBonjour Jamo !

Je propose 10 îles,

Voici une magnifique représentation sous paint :

Enigmo 218 : Transports maritimes à l\'archipel des maths


Merci pour l'énigme !

Posté par
Eric1
re : Enigmo 218 : Transports maritimes à l'archipel des maths 05-09-10 à 10:43

perdu8 îles

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
dpi
re : Enigmo 218 : Transports maritimes à l'archipel des maths 05-09-10 à 12:01

perduBonjour,
La solution est 6 (voir les îles vertes)
En effet si on rajoute un île elle  ne peut être reliée qu'à 5 ou 6
et ne pourra pas être reliée aux autres 1/2/3/4 car déjà 3 liaisons
et cette  7 ème ne pourra  relier 1 en un seul changement

Posté par
castoriginal
Enigmo 218 : Transports maritimes à l'archipel des maths 05-09-10 à 13:40

perduBonjour,

comme chaque île doit pouvoir être reliée à chacune des autres; on peut envisager une figure avec symétrie. Le polygone convient parfaitement.
On s'aperçoit vite que la relation demandée bloque au-delà de 8 îles.La réponse est donc 8 îles maximum

La figure ci-dessous montre les relations entre les îles

Enigmo 218 : Transports maritimes à l\'archipel des maths

Bien à vous

Posté par
cohlar
re : Enigmo 218 : Transports maritimes à l'archipel des maths 06-09-10 à 00:47

gagnéBonjour,

je pense que c'est 10 îles au maximum, avec la solution ci-dessous.

Merci pour l'énigme

Larry

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
13or
re : Enigmo 218 : Transports maritimes à l'archipel des maths 06-09-10 à 01:19

perduBonjour jamo,
Nombre maximal : 6
Disposition : cf. énoncé, îles vertes

Posté par
geo3
re : Enigmo 218 : Transports maritimes à l'archipel des maths 06-09-10 à 21:04

perduBonsoir
Sans conviction je dirai 8
Il doit être beau le
A+

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
veleda
re : Enigmo 218 : Transports maritimes à l'archipel des maths 06-09-10 à 22:21

gagnébonsoir jamo
une île x peut être en relation directe avec au plus  trois îles y,z,t qui peuvent au plus être chacune en relation directe avec  deux autres îles
à partir d'une île x quelconque on peut donc atteindre au maximum 9 îles :
3 directement et 6 avec un changement
xy
xyy'
xyy"
xz
xzz'
xzz"
xt
xtt'
xtt"
ce qui donne un maximum de 10 îles pouvant être reliées conformément au texte(si j'ai bien compris ce texte)
je numérote les iles de 1 à 10 et j'obtiens les liaisons suivantes

1 2
1 3
1 4
1 2 5
1 2 6
1 3 7
1 3 8
1 4 9
1 4 10

2 1
2 1 3
2 1 4
2 5
2 6
2 6 7
2 5 8
2 6 9
2 5 10

3 1
3 1 2
3 1 4
3 8 5
3 7 6
3 7
3 8
3 8 9
3 7 10

4 1
4 1 2
4 1 3
4 10 5
4 9 6
4 10 7
4 9 8
4 9
4 10

5 2 1
5 2
5 8 3
5 10 4
5 2 6
5 10 7
5 8
5 8 9
5 10

6 2 1
6 2
6 7 3
6 9 4
6 2 5
6 7
6 9 8
6 9
6 7 10

7 3 1
7 6 2
7 3
7 10 4
7 10 5
7 6
7 3 8
7 6 9
7 10

8 3 1
8 5 2
8 3
8 9 4
8 5
8 9 6
8 3 7
8 9
8 5 10


9 4 1
9 6 2
9 8 3
9 4
9 8 5
9 6
9 6 7
9 8
9 4 10

10 4 1
10 5 2
10 7 3
10 4
10 5
10 7 6
10 7
10 5 8
10 4 9


j'espère  que bien que ce ne soit pas l'idéal espéré   c'est compréhensible
bon courage pour les corrections et merci pour cet énigmo

Posté par
franz
re : Enigmo 218 : Transports maritimes à l'archipel des maths 07-09-10 à 08:22

perduBonjour,

j'ai trouvé un maximum de 8 îles :
Merci pour l'énigme

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
kiems
re : Enigmo 218 : Transports maritimes à l'archipel des maths 07-09-10 à 14:57

perduje dirai que si parmit les six îles aucune n'est relié a plus de trois îles et que on peut rejoindre a partir des iles toutes les cinq autres villes,je dirai-je que six est le nombre maximal d'île.



on a que  île 1 est relier a île 2,île 3,ile 6
          île 2 est relier a île 1,île 3,île 6
          île 6 est relier a île 1,île 2,île 4
          île 4 est relier a île 5,île 3 et île 6

Posté par
caylus
re : Enigmo 218 : Transports maritimes à l'archipel des maths 07-09-10 à 15:22

perduBonjour Jamo,

Le nombre maximal d'îles dans ce réseau de transports est de 8.
Voici la 1 ère solution trouvée (parmi 5880)
--| 1 2 3 4 5 6 7 8
-------------------
1|                
2|                
3|                  
4| 1              
5| 1 1            
6| 1 1 1          
7|   1 1 1          
8|     1 1 1      
-------------------
En image:
Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
ahmed80dz
re : Enigmo 218 : Transports maritimes à l'archipel des maths 08-09-10 à 18:58

gagnépartant d'une île A en peut aller directement a 3 îles aux maximum en passant par une de ces îles en peut aller a 2 autres îles aux maximum ce qui nous donne 6 îles pour les 3 îles maximum donc de l'île A en peut atteindre que 9 îles max donc le nombre d'îles ne peut dépasser 10


Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
gloubi
re : Enigmo 218 : Transports maritimes à l'archipel des maths 10-09-10 à 16:10

gagnéBonjour,

Ma solution: 10 îles reliées comme ceci:
Enigmo 218 : Transports maritimes à l\'archipel des maths  

Posté par
Mello
re : Enigmo 218 : Transports maritimes à l'archipel des maths 11-09-10 à 00:25

perduJe pense que le maximum d'îles est 6. Sur le dessin je représente les îles en points rouges et les liaisons entre elles avec des lignes bleues.

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
Mello
re : Enigmo 218 : Transports maritimes à l'archipel des maths 13-09-10 à 22:03

perduJe rectifie j'ai trouvé mieux une solution avec 8 îles au maximum mais ce n'est peut-être toujours pas la meilleur solution.

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
alexandre5
re : Enigmo 218 : Transports maritimes à l'archipel des maths 14-09-10 à 18:45

perduJe dirai 7 iles
1:rattaché à 2,4
2: 1,3,5
3: 2,6,7
4: 1,6,7
5: 2,6,7
6: 3,4,5
7: 3,4,5

Posté par
1emeu
re : Enigmo 218 : Transports maritimes à l'archipel des maths 17-09-10 à 18:33

perduBonjour,

voici ma proposition en images: le maximum est 8 iles.

Merci pour cette très jolie énigme.
1emeu

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
mathisgood
Des iles 18-09-10 à 20:31

perdu
Bonjour il me semble qu l'on ne peut relier que 8 iles au maximum

Les 1 du tableau représentent quelles iles sont reliées entre elles de manière directe ( remarque il n'y a jamais plus de 3 fois le chiffre 1 dans une ligne comme dans une colonne)

ile 1ile 2ile 3ile 4ile 5ile 6ile 7ile 8
ile 101001001
ile 210100100
ile 301010010
ile 400101001
ile 510010100
ile 601001010
ile 700100101
ile 810010010

Posté par
jamo Moderateur
re : Enigmo 218 : Transports maritimes à l'archipel des maths 22-09-10 à 21:18

Clôture de l'énigme

Ouille ouille ouille !!!

Je n'en n'étais pas certain, mais cette énigme était vraiment difficile !!

Le maximum est donc de 10 îles, et je livre une belle solution symétrique ci-dessous (celle de gloubi est pas mal non plus).

Pour ceux qui m'ont répondu 10 îles, la vérification n'a pas été toujours facile à faire, j'espère ne pas m'être trop trompé. En particulier, Noflah, j'ai trouvé un truc qui n'allait pas dans ta solution, merci de la contrôler point par point.

Avec tous ces plantages sur cette énigme, cela laisse de l'espoir à ceux qui n'y ont pas participé de remporter le mois ...

Enigmo 218 : Transports maritimes à l\'archipel des maths

Posté par
LeDino
Merci 23-09-10 à 20:00

perdu
Un grand merci à jamo pour cette superbe énigme.
Un grand bravo à totti1000 pour avoir été le premier à trouver une solution.

Et un coup de chapeau particulier à gloubi pour la superbe élégance de sa solution. J'aurais vraiment adoré trouver un truc pareil. C'est simple, c'est beau, c'est vérifiable en un clin d'oeil. C'est plus que des maths... c'est de l'art !!!

Posté par
totti1000
re : Enigmo 218 : Transports maritimes à l'archipel des maths 23-09-10 à 22:32

gagnéBonjour LeDino et merci

J'avais trouvé par calcul que le maximum était 10, mais j'ai mis énormément de temps à trouver la configuration...

Posté par
gloubi
re : Enigmo 218 : Transports maritimes à l'archipel des maths 24-09-10 à 11:23

gagnéBonjour LeDino,

Merci pour ton coup de chapeau (Aîe ! ).

Citation :
c'est de l'art

C'est vrai ...  
Mais j'aurais préféré trouver tout seul.

Posté par
veleda
re : Enigmo 218 : Transports maritimes à l'archipel des maths 24-09-10 à 18:20

gagnébonjour à tous,
je suis étonnée par le petit nombre de bonnes réponses,ce ***m'a paru presque immédiat alors que j'ai passé du temps pour trouver les deux précédents **
merci à Jamo d'avoir accepté ma solution avec simplement la liste des liaisons

Posté par
Noflah
re : Enigmo 218 : Transports maritimes à l'archipel des maths 24-09-10 à 19:19

perduBonjour Jamo,

Effectivement il me semble aussi que ma solution ne fonctionne pas ! Mais je crois avoir compris comment arranger ça. trop tard !

Posté par
plumemeteore
re : Enigmo 218 : Transports maritimes à l'archipel des maths 24-09-10 à 22:36

gagnéBonsoir.
J'avais décrit le futur croquis de Gloubi.

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 72:43:14.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !