Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 15-09-2011 16:46:29

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 805
Lieu: Seahaven island

P2T Parkinng demonstration.

Hello hello,
Je viens de griffonner un truc à ma pause café qui me fait encore me dire que les maths c'est vraiment beau et puissant. Le probleme maintenant bien connu de beaucoup ce trouve ici:
P2T Parking
Les meilleurs ont obtenu 112.
Je me disais qu'on pouvait certainement espérer mieux, alors j'ai cherché et puis je suis arrivé à démontrer en à peine quelques lignes que le maximum était ce 112 (dans le cas précis de la grille donnée dans l'énoncé).
Sauriez vous en faire autant ? :p (il y a du défi) (une vraie démonstration rigoureuse smile)

Je poserais des indices au fur et à mesure sur les différentes étapes pouvant arriver à la démonstration.

Bonne chance aux matheux qui tenteront!

Indice 1 (petit indice):

Spoiler : [Afficher le message] Tentez de voir le problème de manière moins spécifique dans un premier temps pour avoir une majoration, puis la rendre plus fine pour notre cas spécifique, et éventuellement voir des cas particuliers à la main.

Indice 2 (un bon point de départ):

Spoiler : [Afficher le message] Sur une grille hexagonale illimitée, quelle est le plus grand nombre de places qu'un réseau connexe de n cases de route peut desservir?

Démonstration:
Spoiler : [Afficher le message]
Sur un reseau hexagonal illimité:
Lemme 1:
Un réseau connexe de N cases de route dessert au maximum 2N+4 places.
Démonstration du lemme:

On peut considérer qu'un réseau routier peut être construit itérativement
en greffant une case de route sur un réseau existant.
http://www.prise2tete.fr/upload/Clydevil-ParkingGreffon.PNG
Sur la figure ci dessus, on greffe une nouvelle case route vert flashi sur une case quelconque du réseau existant, au bilan de la transformation: on a perdu une place et on en a gagné 3, donc un gain de 2 places.
En considérant que la démarche s'initialise avec une case de route desservant 6 places, le résultat du lemme vient clairement. (C'est une majoration qui en plus peut être très facilement atteinte).

Corolaire 1: On remarquera que pour avoir un réseau optimal on ne doit à chaque greffe jamais toucher plus d'une route du réseau précèdent et jamais toucher plus de 2 places non plus, tout manquement serait une désoptimisation
définitive.

Dans notre figure:
Si on considère nos N cases de routes à l'intérieur on en a nécessairement une qui touche l'entrée:
http://www.prise2tete.fr/upload/Clydevil-ParkingEntry.PNG
Cette case va donc perdre 3 places potentielles (marquées par les points bleus). En conclusion dans notre parking on ne peut desservir avec N routes que 2N+1 places (lemme 1b)

Il y a un autre facteur limitant dans le cas de notre figure c'est que le nombre de places desservies ne peut être supérieur au nombre de cases restantes. Il y a au total 169 cases, donc pour N routes on ne peut desservir au total que 169-N places.

On a donc le tableau suivant:

N                                          55     56     57
max desservi lemme 1b      111   113   115
cases restantes                  114   113   112

En dessous de 55 routes, on voit que le lemme 1b devient limitant.
Au dessus de 57 routes, on voit que le nombre de cases restantes devient limitant.


Comme on a déjà atteint 112, il ne reste donc qu'a prouver qu'on ne peut pas atteindre 113 avec 56 places à l'intérieur. On remarque qu'on a absolument aucune marge d'erreur (la majoration est 113 et on doit faire 113), c'est à dire qu'on doit pouvoir construire itérativement notre réseau interne en faisant en sorte qu'a chaque ajout d'une route on gagne 2 places par rapport au précèdent.

Il vient donc que:
-Toute la périphérie doit être constituée de places. (si on route touchait la périphérie on perdrait au moins une place)
-Sur la figure suivante:
http://www.prise2tete.fr/upload/Clydevil-parking1demo.png
-Si B était une place alors C devrait être une route. (pour accéder à la place marquée étoile).
Hors si C était une case de route alors A et C desserviraient la même place B. (Alors que A et C ne se touchent pas). Conclusion on perdrait au moins une place par rapport à l'optimal (non respect du corolaire 1) et donc B ne peut pas être une place. c'est donc une route. On peut faire le même raisonnement avec la case suivante et ainsi de suite sur toute la seconde périphérie, démontrant que celle ci doit être de la route, et pointant la perte d'optimalité qu'on aurait lorsque cette route formerait une boucle. (non respect du corolaire 1.)

Conclusion: on ne peut pas faire 113 et par conséquent 112 déjà obtenu est le maximum.

CQFD.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 15-09-2011 16:48:31

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

P2T Parking demostration.

Je pense qu'il y a une histoire de 112/113 pour le total de 225, j'essaierai de m'y pencher wink

 #3 - 17-09-2011 20:20:30

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 805
Lieu: Seahaven island

P2T Parking demonstratino.

Ajout d'un plus gros indice.
Démonstration coming soon des que je trouve le temps de faire les quelques images nécessaires.

 #4 - 23-09-2011 10:44:20

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 805
Lieu: Seahaven island

p2r parking demonstration.

Ajout de la démonstration!
Que j'ai pris le temps de rédiger! est ce qu'au moins une personne la lira un jour mystère. big_smile

 #5 - 23-09-2011 11:01:49

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

p2t parking femonstration.

Ne sois pas si pessimiste. J'ai lu la démonstration et je suis sûr que d'autres aussi même s'ils n'y réagissent pas.

Je pense qu'il y a des suppostitions cachées sur la forme "englobante", le mur autour, en particulier dans le calcul du nombre maximum (2N+4) mais puisque ces conditions sont remplies dans ce cas concret la démonstration me semble valide.

Merci d'avoir pris le temps de la rédiger.

 #6 - 23-09-2011 11:11:56

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

2PT Parking demonstration.

Une démonstration brillante ! smile


The proof of the pudding is in the eating.

 #7 - 23-09-2011 11:46:48

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 805
Lieu: Seahaven island

p2t parking demonstratiob.

@rivas:

Je pense qu'il y a des suppostitions cachées sur la forme "englobante", le mur autour, en particulier dans le calcul du nombre maximum (2N+4)

J'ai mis en rouge ou on se trouve pour que ca soit plus clair. Pour 2N+4 il n'y a aucune supposition, le lemme est valable sur un réseau hexagonal illimité. Dans la suite on affine ce lemme pour notre cas précis.

 #8 - 23-09-2011 12:04:25

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

p2t parkung demonstration.

Je suis d'accord, le lemme suppose implicitement le "illimité" (et plus implicitement maintenant) et en effet c'est ensuite affiné dans le cas de cette forme de bordure.

 #9 - 23-09-2011 16:36:22

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

P2T Parking demonsttration.

Tout ça pour dire qu'il n'y aura pas de P2T parking 2 ! sniff !

Merci pour la démonstration !

 #10 - 23-09-2011 16:38:26

TiLapiot
Expert de Prise2Tete
Enigmes résolues : 16
Messages : 851
Lieu: au terrier ;^)

p2t parkinf demonstration.

Clydevil a écrit:

Je viens de griffonner un truc à ma pause café qui me fait encore me dire que les maths c'est vraiment beau et puissant.

Houlaaaa, même si je n'ai pas tout saisi (loin s'en faut), je suis admiratiiif de tes "griffonages" tongue Merci ClyDevil

 #11 - 24-09-2011 12:56:02

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 679

p2t parkung demonstration.

On peut songer à étendre cette discussion en considérant des hexagones de taille quelconque. Soit [latex]n[/latex] entier [latex]\geq 1[/latex] tel qu'il y ait [latex]6n[/latex] cases sur le pourtour du parking (donc [latex]n=7[/latex] pour l'hexagone de cette discussion).
Le nombre de cases est donné par
[TeX]NC(n) = 6*n+6*(n-1)+\cdots+6*1+1[/TeX]
[TeX]NC(n)=3n(n+1)+1[/TeX]
[TeX]NC(n)=3n^2+3n+1[/TeX]
On peut imaginer que le nombre maximum de places de parking est donné par
[TeX]MP(n)=2n^2+2n[/latex] pour [latex]n\geq 2[/TeX]
Reste à le prouver, en étendant la preuve de Clydevil ou en imaginant d'autres preuves...

 #12 - 24-09-2011 18:35:15

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

P2T Parking demonstraation.

L'étape suivant, c'est un parking en forme de ballon de foot smile

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ?

Sujets similaires

Sujet Date Forum
P2T
Demonstration par salehseghiri
11-02-2014 Enigmes Mathématiques
18-12-2010 Enigmes Mathématiques
P2T
Un héritage P2T par Vasimolo
29-08-2009 Enigmes Mathématiques
P2T
05-09-2011 Enigmes Mathématiques
P2T
17-09-2011 Enigmes Mathématiques
P2T
Pas trop P2T ? par SaintPierre
13-01-2011 Enigmes Mathématiques
P2T
Deux cryptarithmes P2T par scrablor
19-04-2010 Enigmes Mathématiques
P2T
P2T Parking par Clydevil
10-09-2011 Enigmes Mathématiques
P2T
Raisonnement Numerique par Chil1977
16-11-2015 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete