Enigmo 104 : Ceci n'est pas un jeu de gratte-ciel

Posté par jamo jamo

Bonjour,

je suppose que vous connaissez tous le "jeu du gratte-ciel" qu'on trouve dans pas mal de magazines.
Alors le jeu que je vous propose n'est pas un jeu de gratte-ciel !

Voilà une énigme sympa comme on les aime : tout le monde peut y jouer, plusieurs approches sont utilisables (à la main, par informatique, ...) mais à laquelle on n'est pas certain d'avoir la solution optimale !

On dispose d'un terrain carré de 5x5 parcelles. Sur chaque parcelle, on construit un immeubles de 1, 2, 3, 4 ou 5 étages. Mais il faut respecter les contraintes suivantes :

- un immeuble à 1 étage peut être placé n'importe où ;
- un immeuble à 2 étages doit être voisin avec au moins un immeuble à 1 étage ;
- un immeuble à 3 étages doit être voisin avec au moins un immeuble à 1 étage et un immeuble à 2 étages ;
- un immeuble à 4 étages doit être voisin avec au moins un immeuble à 1 étage, un immeuble à 2 étages et un immeuble à 3 étages ;
- un immeuble à 5 étages doit être voisin avec un immeuble à 1 étage, un immeuble à 2 étages, un immeuble à 3 étages et un immeuble à 4 étages.

Petite précision : être voisin signifie avoir un côté commun, les immeubles en diagonale ne comptent pas.

Ensuite, on compte le nombre total d'étages : sur l'exemple proposé ci-dessous, on compte donc 46 étages en tout (si je ne me suis pas trompé en faisant l'addition).

Question : trouver la configuration afin d'avoir un score maximal. Vous me donnerez le nombre total d'étages, puis la disposition des immeubles.

Bonne recherche !

Posté par link224 link224

Salut jamo.

Je propose comme score maximal 58 étages. La disposition serait la suivante :
1 3 2 1 2
2 5 4 1 1
3 1 3 4 2
1 1 2 5 3
2 4 3 1 1

@+ et merci pour l'énigme.

Posté par MatheuxMatou MatheuxMatou

Bonjour Jamo,

Je n'ai pas temps d'approfondir ni de faire un programme... et donc aucun moyen de savoir si j'ai bien la maximale...

je vais tenter un score de 59 :

2-3-1-2-3
1-5-2-3-1
2-4-1-4-2
1-3-2-5-1
3-2-1-3-2

MM

Posté par shboul shboul

Salut...
Bon j'ai pas trop poussé le truc mais visiblement, j'en trouve 60.
la disposition est la suivante
31123
23451
31231
13451
32123

Merci encore pour la détente...

Posté par kjus kjus

Voici ma réponse :

3 2 1 2 1
1 5 4 3 4
4 3 2 1 2
2 1 5 4 3
3 1 3 2 1

(total de 63).

Ce problème se résout exactement par la programmation dynamique.

Posté par Nofutur2 Nofutur2

Je me lance..
Je trouve une solution à 62 étages au total, (avec un axe de symétrie).
Ci-joint ma disposition..

Posté par LeDino LeDino


Je pense que le maximum est à 62 étages.

Le maximum d'immeubles de 5 étages est de 2.
Et dans ce cas, le maximum d'immeubles de 4 étages est de 4.
Et dans ce cas, le maximum d'immeubles de 3 étages est de 5.
Et dans ce cas, le maximum d'immeubles de 2 étages est de 7.

Merci pour l'énigme.

Une disposition possible :

Posté par pacou pacou

Bonjour, jamo

De façon purement intuitive et non rigoureuse , je dirais 60 étages au total.



Merci pour l'énigmo.

Posté par castoriginal castoriginal

Bonsoir,

je vous propose une solution qui donne un total de 60 étages.

On aura du mal à dépasser ce total !

voici ma solution graphiquement

Bien à vous

Posté par spybot77 spybot77

Si j'ai bien compris cette enigmo:
Sans être sur que se soit la meilleure config j'obtiens 59:

  1 1 4 2 1
  2 4 3 2 1
  3 5 1 5 3
  1 2 3 4 2
  1 2 4 1 1

Posté par Rickthokmas Rickthokmas

Après plusieurs essai manuellement, j'arrive à un maximum de 65 étages.

Voici la disposition

3 1 2 1 3
2 5 3 5 2
1 4 1 4 1
2 5 3 5 2
3 1 2 1 3

Posté par 13or 13or

Bonjour jamo,

Nombre maximum : 63

Exemple de disposition :
1 2 1 2 3
4 3 4 5 1
2 1 2 3 4
3 4 5 1 2
1 2 3 1 3

Bon courage pour la correction...

Posté par manpower manpower

Bonjour,

avec de sérieux doutes _{(car je n'ai pas réussi à placer plus que deux "5")}, je propose un score maximum de 63.

Voici une des configurations que j'ai trouvé _{(alors que la question annonce "la"...)}:



Merci pour l'Enigmo (et le ?).

Posté par lolo248 lolo248

J'ai trouvé plus de 5 solutions où le nombre total d'étages est de 62.

Voici l'une des diverses solutions que j'ai trouvé en texte ET en image :
23132
15251
24142
43134
12321

Posté par fade2black fade2black

J'ai rempli deux grilles sans aucune méthode, et je ne vois pas comment voir si ma solution est optimale. Le total de ma première grille était 54, et la deuxième 59.

Voilà ma deuxième :

3 2 3 1 2
1 1 4 2 3
3 2 5 3 1
2 4 1 4 2
1 3 2 1 3

Posté par fade2black fade2black

Ah j'ai perdu, j'ai trouvé une autre grile qui fait 60 :

3 2 1 2 3
1 5 4 3 1
4 3 2 4 1
2 1 1 5 2
3 1 2 3 1

Tant pis...

Posté par hypatie hypatie

J'arrive à un total de 60 avec la configuration suivante :

3  1  1  2  3
2  5  3  4  1
1  4  2  1  2
1  3  4  5  3
3  2  1  2  1

Posté par allca allca

*challenge en cours*

Posté par maher_91 maher_91

bonjour,

je trouve un nombre maximal de 62 étages.

Posté par veleda veleda

bonsoir Jamo
si cette énigme compte pour le mois d'avril je suis vraiment en retard
je propose 61 étages avec la disposition suivante

2 4 1 3 2
1 3 2 4 1
2 5 1 5 2
1 4 2 3 1
2 3 1 4 2

merci pour ce jeu

Posté par yoyodada yoyodada

Bonjour Jamo,

je n'ai pas trouvé mieux que 60 pour ce coup-ci, en espérant que ça marche


2  1  3  2  3
1  1  4  1  1
3  5  2  5  3
2  4  1  4  2
1  3  2  3  1         , total = 60.

Merci pour l'énigme

Posté par Bradveto Bradveto

Bonjour

nombre total d'étages 62

3 1 3 2 1
2 1 4 1 2
3 4 2 4 3
1 5 3 5 1
3 2 1 2 3

Posté par carpediem carpediem

salut jamo _{et sans rancune aucune}

13213
25412
31323
32541
13232



pour un total de 61 étages....

1	3	2	1	3
2	5	4	1	2
3	1	3	2	3
3	2	5	4	1
1	3	1	3	2

Posté par gugu39 gugu39

Sans conviction j'annonce 60 avec

12321
35153
24142
23132
13231

Posté par albatros albatros

Total 57

1	1	1	3	2
2	5	3	2	1
3	4	1	4	3
1	2	3	5	2
2	3	1	1	1

Bonne journée

Posté par amina78 amina78

Bonsoir

Je trouve 62 etages en tOut!!

3       2       1     2   1
1       5      3     4   3
3       4       2     1   2
2       1       4     5   3
3       1       3     2   1

Posté par torio torio

Pour un total de 61

A+
Torio

Posté par jeni231 jeni231

bonjour,
score 63, j'ai pas pu faire mieux...
merci

Posté par thib2139 thib2139

Bonjour, je trouve 61 étages dans la configuration suivante :
1 2 1 3 2
3 4 2 4 1
2 1 2 5 3
3 5 4 1 2
1 2 3 1 3

Posté par dpi dpi

merci réponse 101 (bof)
voici ma réponse : 62 étages
grille:
2 3 1 4 2
1 5 2 3 1
3 4 1 4 2
2 2 1 5 3
1 4 3 2 1

Posté par Francois86 Francois86

Je propose :

1  4  2  3  1
2  3  1  4  2
2  4  2  3  1
1  1  4  5  2
3  2  3  1  3

pour un total de 60

Posté par PCAX PCAX


Nombre total d'étages = 58, répartis comme suit:

3 1 3 2 1
2 1 4 1 2
4 3 2 1 3
1 4 5 3 1
3 2 1 2 3

Posté par castoriginal castoriginal

Bonsoir,

je me rends compte, en vérifiant que la solution que j'ai donné précédemment n'est pas
correcte.
J'aurais du vous présenter celle qui suit; tant pis, j'aurai un poisson

Posté par totti1000 totti1000

Bonjour Jamo,
Je n'ai pas trouvé mieux qu'un total de 63...

Posté par kryzen kryzen

le maximum selon moi est 59

2	1	2	1	2
4	1	3	1	4
3	4	2	4	3
2	5	3	5	2
1	1	1	1	1
12	12	11	12	12	59

Posté par Rudi Rudi

Bonjour

---------Reponse proposee----------

Sans garantie, je trouve une somme maximale de 61 etages avec une des dispositions en image attachee

---------Methode employee---------

Placer les 5 dans le carre central 3x3 : il ne peut y en avoir que deux au plus
Les solutions maximales trouvees le sont avec deux 5, puis trois ou quatre 4, puis quatre ou six 3...
Pour certaines, les solutions possedent un axe de symetrie

Ayant cherche cette enigme a la main, je n ai aucune certitude que 61 soit la valeur maximale : une recherche exhaustive avec programme informatique permettrait de facon certaine de trouver la ou les dispositions maximales

Rudy

Posté par dhalte dhalte

Mon meilleur score : 63

Posté par Lilli Lilli

Hmm je sais pas si c'est optimal mais je trouve: 63 étages
Disposition en image

Bonne soirée
Merci

Posté par Youpi Youpi

Je répond "just for fun" puisque je n'ai pas participé ce mois ci..

Difficile de savoir si ma solution est optimum (à moins de faire un programme mais bon ...): je n'arrive pas à faire mieux que 61.

merci pour le casse tête.

Posté par rezoons rezoons

Bonjour ,
je trouve un maximum de 61 avec:
12313
35412
21253
14241
23132

Posté par gloubi gloubi

Bonjour,

Je me lance avant la clôture ...

Total: 63 étages.

Disposés comme ceci:

Merci pour cette très intéressante énigme.
On en redemande !  

Posté par matovitch matovitch

Bonjour !
Après avoir testé plusieurs centaines de millions de grilles (pas toutes correctes) parmi les plus intéressante grâce à un programme en C++.
Je trouve un maximum de 58...en bonus voici ces 25 gratte-ciels en 3D :

Posté par castoriginal castoriginal

Bonsoir,

je progresse encore avec une solution à 61 étages; la voici en image :

A bientôt

Posté par cesium134 cesium134

Bonjour,

je vous propose 57 disposés comme suit:

1	2	3	1	1
1	5	4	2	2
2	3	1	3	4
1	5	4	2	1
1	2	3	1	2

Bonne journée
Jpp

Posté par jamo jamo

Clôture de l'énigme

Bon, il est temps d'arrêter le massacre avec cette énigme visiblement très difficile !

Le maximum est de 63, je vous laisse consulter les bonnes réponses, je crois qu'il en existe plusieurs différentes (hors symétries bien entendu).

Je crois que nous devons tous saluer et nous incliner devant kjus, qui s'est inscrit sur le forum dans le seul but de répondre à cette énigme, en donnant la bonne réponse, et en semblant certain d'avoir la solution optimale grâce à la "programmation dynamique".

Ce serait sympa de sa part de venir nous en dire un peu plus, car je crois bien que parmi ceux qui ont trouvé la bonne réponse, personne ne semble certain d'avoir la solution optimale !

Un grand bravo aussi à matovitch qui, même s'il n'a pas trouvé la bonne solution, a fourni une image de synthèse pour représenter sa solution (vous pouvez vérifier, ses building ont bien les bonnes hauteurs par rapport à sa solution !)

Et pour le mois d'avril, c'est donc 13or le grand vainqueur, avec un sans-faute, un temps moyen pas mauvais (comme quoi rien ne sert de courir parfois), et je crois bien que c'est sa 1ère victoire !!

Posté par MatheuxMatou MatheuxMatou

Un grand bravo à 13or...

et je fête mon premier poisson !

_{mais j'avais prédit que ma réponse était un peu "risquette" !}

amitiés à toutes et tous

MM

Posté par 13or 13or


Quand on a la chance, en consultant le site, de tomber peu de temps après la diffusion des énigmes, ça aide bien pour le classement!
En avril, j'ai eu cette chance. En mai, moins...
... mais l'important c'est de s'amuser, on fait ce qui nous plaît!
Merci jamo pour ces bon moments, et un coucou à tou(te)s les participant(e)s!

Posté par lièvre59 lièvre59

Bravo 13or

Louisa

Posté par maher_91 maher_91

Mes félicitations 13or

Posté par kjus kjus

Bonjour,

Désolé de répondre un peu tard, mais voici pour ceux que ça intéressent un algorithme permettant de trouver la meilleure solution (ici de total 63) de manière sûre.

Un algorithme naïf, qui fonctionne, mais dont l'espace de recherche est beaucoup trop gros, serait d'énumérer tous les placements possibles des immeubles, et de ne garder que le (ou les) placements optimaux. Une manière de tester récursivement, ligne par ligne, toutes les possibilités de placements d'immeubles. Il faudrait bien sûr mémoriser assez d'information des lignes précédentes pour satisfaire les contraintes liées aux batiments de la ligne i-1 lorsque l'on teste tous les placements de batiments de la ligne i.

Une remarque pour ces contraintes : pour remplir la ligne i en satisfaisant les contraintes liées aux batiments de la ligne i-1, il suffit de connaitre la ligne i-1 et la ligne i-2. Mieux, on peut remarquer que chaque batiment de la ligne i-1 est soit "satisfait" (il y a déjà assez de batiments autour de lui avec la bonne taille), soit impose un numéro précis de batimenent sur sa colonne en ligne i. Il suffit donc de stocker la ligne i, et les contraintes liées aux batiments non satisfaits de la ligne i.

Ensuite, pour pouvoir calculer ça vite, on s'aperçoit qu'étant donné un état de ligne i, et un ensemble de contraintes, on peut optimiser le score des lignes suivantes (supérieures à i) indépendemment. (C'est l'idée de la programmation dynamique, cf http://en.wikipedia.org/wiki/Dynamic_programming).
Le nombre d'états possibles est d'environ 5 * 5^5 * 5^5 (nombre de lignes * états ligne i * contraintes), et le nombre d'états de lignes suivantes à tester est en moyenne contant (pour simplifier). L'algorithme va donc effectuer en gros 50 million de tests (il y a en gros cent opérations par test, il tourne en moins d'une seconde en pratique).

Vous pouvez voir le code ici (pour gcc):
http://pastebin.com/f9aa2145

Enfin, merci pour l'enigme qui était très sympatique