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
[+]

Écrire une réponse

Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide !
Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci.
Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Options
Sécurité

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

Dans une course, vous doublez le 19ème, en quelle position êtes-vous ?

Retour

Résumé de la discussion

Clydevil
04-11-2015 14:26:37

Hello!
Ça faisait un bail que je n'avais rien posté alors voici une vraie saloperie:
-On a devant nous un polygone.
-Sur chaque sommet de ce polygone il y a un entier relatif.
-La somme de tous les sommets du polygone est strictement positive.
-On a le droit d'effectuer l'action suivante:

Action autorisée:
-On prend un sommet strictement négatif de notre choix.
-On retire le signe - (ainsi si c'est -5 on écrit 5 à la place)
-On ajoute l'entier négatif initial à chaque sommet voisin (ce qui conserve donc la somme globale)

Par exemple:
Si on a  ... 2 -1 -3 4 0 ...  quelque part sur notre polygone, on a le droit de prendre le -3 de le transformer en 3 et de soustraire 3 à ses deux voisins ce qui donne:
... 2 -4 3 1 0 ... 

Il s'agit de démontrer que quoi qu'on fasse on ne pourra plus rien faire au bout d'un moment. (ie quoiqu'on fasse on finira par avoir que des entiers positifs ou nuls partout).

C'est assez dur d'avoir la bonne idée, mais lorsqu'on l'a ce n'est pas très long.
Je vous laisse mariner et je donnerais des indices dans un second temps.

Comme promis un premier indice (vraiment pas un très gros indice):
Spoiler : [Afficher le message] En fait il est assez difficile dans ce problème de trouver une quantité entière qui va strictement décroître à chaque opération (un monovariant). Par contre on peut utiliser le même genre d'argument mais en plus général: Il faut chercher à transformer le problème, le voir différemment de telle manière que sur son homologue transformé l'effet de l'action autorisée mène d'avantage trivialement à un état final.


2ème indice (indice moyen):
Spoiler : [Afficher le message] Sommes partielles

3eme indice (gros indice):
Spoiler : [Afficher le message] Prendre un sommet de référence sur le polygone, et regarder la suite des sommes partielles depuis ce sommet dans le sens de parcourt de votre choix.


Bonne chance!

Solution:
Spoiler : [Afficher le message] On va noter les entiers sur le polygone x0,..,xn et S leur somme.
On va prendre comme référence une arrête et on va construire la séquence
des sommes partielles dans les deux sens:
On considéré qu'on a 0 sur notre arête, puis on parcourt le polygone dans le sens horaire on fait somme de tout ce qu'on rencontre, ça nous donne la moitie droite d'une séquence infinie, pour avoir la moitie gauche on part de notre arrête on va dans le sens inverse du sens horaire et on soustrait tout ce qu'on rencontre.

Ça ressemble a ceci:
http://www.prise2tete.fr/upload/Clydevil-pentagon-solution_1.jpg
Bref on construit la séquence des sommes partielles dans les deux sens, on va la noter b(i)
-Elle est globalement croissante car S est strictement positive.
-Elle est décroissante localement si et seulement si xi est négatif.
-Lorsqu'on effectue une opération sur le polygone, ça revient à permuter deux valeurs consécutives pas dans l'ordre dans notre séquence, pour les trier par ordre croissant.
Il s'agit donc d'un tri par bulle (pour les informaticiens) et il est intuitivement facile de se convaincre qu'il va terminer en temps fini, avec comme résultat d'avoir strictement trié la liste.

Si on veut démontrer rigoureusement qu'il termine:

On peut noter i+ le nombre d'indices j>i tel que b(j) < b(i)
i+ est fini (car la suite est globalement croissante) et ne dépend que de i modulo n.
Soit P la somme des i+ sur une période, lorsqu'on permute b(i+1) alors i+ décroît de exactement 1 et les autre j+ sont inchangés, ainsi donc P décroît de 1 et le tout s’arrête lorsque P = 0 et que la liste est parfaitement triée.

Source: Mathematical Puzzles: A Connisseur’s Collection solution de Bernard Chazelle of Princeton.

Voila voila.

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