DEFI 50 : L'archipel.:*::*::*:

Posté par minkus minkus

Bonjour à tous.

Pour ce 50e défi, et pour changer un peu, je vous propose un petit exercice de topologie.

Un archipel comporte un certain nombre d'îles reliées entre elles par 143 ponts.

Sachant que :

-Aucune île n'est directement reliée à une voisine par deux ponts différents.
-Les ponts ne se croisent pas.
-Il est possible de passer de n'importe quelle île à toutes les autres, en empruntant un ou plusieurs ponts.

Quel est le nombre minimal d'îles dans cet archipel ?


Et en question subsidiaire cette fois-ci, quelle est donc cette petite île reliée par un seul pont ?



Bonne réflexion.

minkus

Posté par nobody (invité)

En m'inspirant fortement de , je trouve qu'il y a au moins 50 îles (ce qui correspondrait assez bien au défi n° 50).
Je suis tombé dessus un peu par hasard, à cause de ca j'ai loupé la difficulté de l'énigme

Sinon, pour l'image, il doit sûrement s'agir du Mont Saint Michel ( )

Posté par Nofutur2 Nofutur2

Le but est de minimiser le nombre d'îles à partir d'un nombre de ponts donné, ou de maximiser le nombre de ponts à partir d'un nombre d'îles donné.
Le structure en triangle est celle qui utilisera le maximum de ponts ne se croisant pas.
En ajoutant une île à l'intérieur d'un triangle (ou à l'extérieur de la surface des triangles déjà formés),j'ajoute 3 ponts. Je peux donc démontrer par récurrence que P=(I-2)*3
Pour P=143, les 141 premiers nécessitent I=141/3 + 2 = 47 +2 = 49 ponts. Les deux derniers ponts nécessitent une dernière île.
Le nombre minimal d'îles dans cet archipel est donc de 50.

Posté par Nofutur2 Nofutur2

J'oubliais la question subsidiaire!!!
C'est bien sûr notre fameux "Mont Saint Michel".

Posté par geo3 geo3

Bonjour
Pour n îles le nombre maximum de ponts = le nombre de ponts reliant une île à toutes les autres sauf les 2 voisines ( = n-3) + n = 2n -3  =>
143 = 2n - 3  => n = 70
Le nombre minimal  d'îles =
Il s'agit du MONT St Michel
A+

Posté par Torpedo (invité)

Salut !

L'archipel comporte au minimum 50 îles.

Un graphe vérifiant les 3 propriétés énoncées a comme invariant topologique : F - A + S = 1. ("F" le nombre de faces, délimitées par "A" ponts (arêtes du graphe) et "S" le nombre d'îles (sommets du graphe)). Avec un petit peu d'imagination, si on plonge ce graphe dans un espace 3D, en lui ajoutant une face on obtient un polyèdre qui a la topologie d'une sphere (F' - A + S = 2, je note avec un prime les nombres de faces dans la représentation 3D). La face ajoutée est celle délimitée par tous les ponts qui marquent les contours extérieurs de l'archipel. L'avantage de cette représentation est qu'elle permet d'avoir chaque arête commune à deux faces et donc d'écrire :

2.A = 3.F'₃ + 4.F'₄ + 5.F'₅ + ... , avec F'₃ le nombre de faces triangulaires, F'₄ les faces à 4 côtés, etc.

On a F+S=144 donc pour minimiser S, il faut maximiser F. Et ainsi chercher à avoir un maximum de faces triangulaires. Cela est possible en prenant F'₃ = 94 et F'₄ = 1. Rappellons qu'il y a une face en plus dans la vision 3D du probleme, et donc au final F=94, S=50 et A=143 vérifie l'invariant topologique et minimise le nombre de sommets du graphe. CQFD.

Quant à la photo il s'agit du Mont St Michel. Tiens d'ailleurs je suis en train de penser à une autre image qui aurait bien illustré ce probleme... Je la posterai peut-être en JFF

A++ et merci pour cette révision de topologie !

Posté par bret (invité)

bonjour,

voici ma réponse : le nombre minimal d'iles est 50

Dans un graphe planaire "minimal", F-A+S=2 (où F est le nombre de zones délimitées par des ponts, A le nombre de ponts et S le nombre d'îles)

De plus, si le graphe est minimal, chaque zone est délimitée par trois ponts, et chaque ponts touche deux zones, donc

Par conséquent, S-A+F=S-A/3=2

Donc S=2+A/3

comme ici A n'est pas divisible par trois, il faut prendre le plus petit S entier qui est plus grand que 2+A/3

donc S=50

Ci dessous un exemple pour le même problème avec 20 ponts et donc S=2+A/3 donc 9 villes

Posté par chaudrack chaudrack

Bonjour et merci pour cette énigme bien sympa.

Pour commencer, j'ai considéré l'énigme de la façon suivante:

Combien de ponts peut-on faire au maximum (en respectant les conditions énoncées) pour un archipel de x îles?

Pour 2 îles, 1 seul pont. (c'est un cas particulier)
Pour 3 îles, 3 ponts
pour 4 îles, 6 ponts
Pour 5 îles, 9 ponts

On remarque alors qu'a chaque ajout d'une île, on ajoute 3 ponts..

Dans la même logique, on trouve que pour 49 îles, on peut mettre au maximum 141 ponts..

Il manque alors 1 île pour ajouter les deux ponts manquants..

Ma réponse est donc:

Le nombre minimal d'îles dans cet archipel est 50.

@ plus, Chaudrack

Posté par gloubi gloubi

Bonjour,

Les conditions imposées correspondent à la définition d'un "graphe planaire".
Dans un tel graphe le nombre total de sommets est supéreur ou égal à deux plus le tiers du nombre d'arêtes.

Ici, le nombre minimal d'îles est 50.

A+,
gloubi

Posté par evariste evariste

Je propose 48 îles au minimum.
Si on construit la figure en ajoutant les îles une par une et si à chaque fois on trace tous les ponts possibles (sans doublon et sans croisement) on constate que pour chaque île ajoutée on ne peut construire que trois ponts supplémentaires. Donc 143/3=47,667 soit 48 îles.

Posté par piepalm piepalm

Rappelons la formule d'Euler pour un graphe planaire connexe:
s+f=a+2 si s est le nombre de sommets, f de faces et a d'arêtes.
Comme chaque face a au moins 3 arêtes et chaque arête participe à 2 faces, 3f<=2a donc s>=a/3+2
Ici a=143 donc s>=50

Posté par Fractal Fractal

Bonjour,
Il y a autant d'îles dans cet archipel que de défis posés par minkus (donc toi ) depuis qu'il est posteur d'énigmes (soit 50 îles).

Question subsidiaire :
Il s'agit du Mont-St-Michel.

Fractal

Posté par lotfi lotfi

Bonjour
C'est fou comme réponse mais bon l'éssentiel c'est de participé
le nombre minimal d'ile est 36 îles.


Lotfi

Posté par slaurent128 (invité)

Bonjour,

Je dirai 50.

Pour trouver le nombre minimal d iles connaissant le nombre de ponts, je pense qu il faut determiner pour un nombre i d iles le nombre maximum de ponts pouvant reliés ces iles.

aprés quelques tentatives infructueuses avec un dessin quelconque, j ai dessiné les iles toutes alignées et la, j ai vu une certaine propriété. Pour i iles, la 1e ile peut etre relier à (i-1) iles, en tracant les ponts "au-dessus" des iles. Puis la 2e ile peut etre relier à (i-2) iles, en tracant les ponts "en-dessous" des iles.
Les autres iles, elles, ne peuvent relier ensuite qu'à la prochaine ile (elles sont "coincés" entre les ponts des 2 premieres iles).
Donc, pour i iles, on peut construire au maximum :     (i-1)+(i-2)+(i-3) = 3i-6.
En résolvant 3i-6=143, on trouve i=49,66...
Avec 49 iles, on a au maximum 141 ponts;
Il y a donc au minimum 50 iles.

Merci pour l'énigme.

Posté par slaurent128 (invité)

NB: dans ma demonstration, j ai supposé, en toute logique, que les ponts sont "a plat" et qu il n y en a pas qui "partent dans l espace" pour passer au dessus d un autre.

Posté par moomin moomin

Bonsoir Minkus

Je propose 57 iles
La photo représente le Mont-Saint-Michel

Merci
Moomin

Posté par plumemeteore plumemeteore

cinquante îles (nombre égal au numéro du défi !)

premier exemple
seize triangles emboîtés l'un dans l'autre sans se toucher; soient EFG un de ces triangles et IJK le triangle immédiatement intérieur; on peut toujours trouver un chemin en corolle tel que EIFJGKE qui ne se croise pas; le triangle tout intérieur contient en plus deux îles, l'une reliée à ses trois sommets, l'autre pouvant être reliée à la première et à deux des sommets.
Donc : 16*3 (triangles) = 48; 15*6 (corolles) = 90; 6 pour les îles intérieures; total 144 > 143

deuxième exemple
un polygone fermé de 49 côtés dont les sommets sont reliés en rayons à une île intérieure : 50 îles; on relie en outre un des sommets à tous les sommets qui ne sont pas ses voisins : 49+49+46 = 144 > 143

troisième exemple
un polygone de 48 côtés dont les sommets sont reliés à une île intérieure; on dessine une corolle extérieure de 2 en 2 sommets; par-dessus des corolles en faisant des sauts de 4, 8, 16 îles et en prenant toujours le même départ
48 côtés + 48 rayons + 24+12+6+3 sauts de corolles = 141; on ajoute une île n'importe où et elle peut toujours être reliée exactement à trois autres; 141+3 = 144 > 143

Pour le nom de l'île, je propose : Mont-Saint-Honoré, parce qu'elle a la forme du gâteau.

Posté par Pr3dator (invité)

je propose 50 îles, ici disposées en cercle, dont 1 au centre, avec 144 ponts possibles. 49 rayons + 49 cordes + 25 sauts de 2 îles + 12 sauts de 4 + 6 sauts de 8 + 3 sauts de 16 + 1 saut de 32...
merci pour l'énigme !

Posté par borneo borneo

Bonjour,
j'ai enfin de nouveau internet à volonté, j'ai donc fait une petite recherche sur les formules géométriques (et je remercie celui qui me l'a conseillé)

Je trouve un nombre minimal d'îles de 50 en considérant qu'on est dans un plan, et non sur une sphère (pas de pont qui fait le tour de la terre).

La photo est le Mont Saint Michel.

Je poste mon raisonnement à la suite.

Posté par borneo borneo

J'ai testé beaucoup de combinaisons différentes pour avoir des polygones avec le moins possible de sommets (les îles) et le plus de côtés (les ponts.
Grâce à google, j'ai trouvé la formule d'Euler qui dit que dans le plan,

nb îles - nb ponts + nb de faces = 1

J'ai aussi trouvé des cours sur la triangulation du plan. Ce qui est bien avec les énigmes, c'est qu'on apprend plein de choses. J'ai retrouvé une configuration que j'avais obtenue intuitivement, à savoir un triangle dans lequel on ajoute un point intérieur, ce qui permet d'ajouter 3 arêtes.

J'ai donc un tableau où on part de 3 îles et 3 ponts
puis
4 îles 6 ponts
5 et 9
6 et 12
7 et 15
8 et 18
9 et 21
10 et 24
11 et 27
12 et 30
13 et 33

on ajoute à chaque fois une île et 3 ponts. On arrive à 49 îles et 141 ponts. On ajoute une île et deux ponts, et on a nos 143 ponts.

Je mets une image, mais je n'ai pas pu mettre les 50 îles.
Je croise les doigts pour ne pas avoir de car j'ai rempli des pages de constructions... sans internet pour les recherches, ça va beaucoup moins bien, quand on n'est pas Euler

Posté par sof (invité)

74 iles

Posté par tealc tealc

ma réponse est 17 iles...

et question subsidiaire : je dirai... le mont st michel!

merci pour l'énigme

Posté par Titane12 Titane12

50 îles
Le Mont Saint-Michel

Posté par minkus minkus

Bonjour,

Il s'agissait bien du Mont Saint-Michel _{(qui devrait vraiment appartenir à la Bretagne)}. Plumemeteore il va falloir venir faire un tour par chez nous

Concernant le défi lui meme, on peut voir que les topologues ont été à la fete en pensant a utiliser la formule de leur illustre prédécesseur à tous, le grand Euler. Bravo à tous ceux qui ont trouvé 50 sans la formule !

Un grand bravo aussi pour tous les jolis graphes avec une mention spéciale pour celui de Bornéo.

minkus

Posté par borneo borneo

Merci Minkus.
J'ai noirci beaucoup de papier avant de tomber un peu par chance sur la technique qui consiste à ajouter une île dans un triangle existant (ce qui crée 3 ponts) et pas à l'extérieur (ce qui n'en crée que 2). Ensuite, en ajoutant une île et 3 ponts autant de fois que nécessaire, on trouvait vite la réponse.

Posté par plumemeteore plumemeteore

Bonjour.
J'ai voulu faire preuve d'humour en répondant 'Mont-Saint-Honoré'.
D'ailleurs la forme de gâteau de ce site n'est pas étrangère à sa popularité

Posté par minkus minkus

Plumemeteore, a dire vrai je m'en doutais un peu et puis apres je me suis dit : "Ca te semble evident parce que tu es breton mais c'est pas pareil pour tout le monde."

Posté par plumemeteore plumemeteore

bonjour à tous
je ne suis pas Breton, mais Belge, de la province de Liège.
Le Mont-Saint-Michel me semble être normand, car le Couesnon se jette juste à gauche de son isthme. Peut-être en était-il autrement à d'autres époques.