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 - 11-10-2009 18:14:01

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Un escalier de pièce

Un problème assez difficile smile

on prend dix pièces de monnaie que l'on dispose en un ou plusieurs tas . On prend les pièces au dessus de chaque tas pour faire une nouvelle pile que l'on dispose à côté des autres puis  on recommence à volonté . Quelle que soit la position de départ aboutit-on systématiquement à un escalier 1 ; 2 ; 3 ; 4 ? On peut bien sûr se poser la même question avec 15 ; 21 ; 28 ; 36 ; 45 ; ... pièces .

http://img237.imageshack.us/img237/8420/pilesdepices.jpg

Bon courage cool

Vasimolo

  • |
  • Répondre

#0 Pub

 #2 - 11-10-2009 21:08:49

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 964

Un escalier de piècess

Il n'y a qu'un nombre fini de répartitions des 10 pièces en tas ordonnés, disons de la gauche vers la droite. Commençons par les dénombrer :
- pour faire - de manière unique - une telle répartition, je place mes 10 pièces en ligne et je marque - ou pas - une séparation sur chacun des 9 intervalles ;
- je réponds donc 9 fois à la question « séparation ou pas ? ».

Cela fait donc 2^9 cas, 512 pour être plus concret.

Si on répète suffisamment de fois le procédé, on est obligé de retomber sur une configuration déjà rencontrée. Il faut que l'on prouve que c'est la distribution 1:2:3:4. Cette configuration est stable : une fois atteinte, on n'en sort plus.

La question revient à justifier qu'on ne peut pas tourner en rond et éviter cette progression arithmétique.

Ce qui distingue la configuration 1:2:3:4 des autres, c'est qu'elle est la seule pour laquelle les écarts sont de +1 à chaque fois.

... voilà où j'en suis. Je ne vais tout de même pas développer les liens entre les 512 cas roll

[EDIT]
J'ai essayé de classifier les 512, mais les dénombrements se compliquent !

Première idée : il y a de nombreuses situations sans antécédent, toutes celles dont le dernier nombre est inférieur au nombre des autres tas. Par exemple 1:3:4:2 et 1:1:1:4:3 ne peuvent pas être déduit d'une situation antérieure.
En revanche, les autres le sont. Par exemple, 1:2:4:3 vient de 2:3:5 et 1:1:1:2:5 vient de 1:2:2:2:3 ou de 2:2:1:2:3 entre autres...

Deuxième idée : Une configuration où le nombre de droite vaut le nombre d'autres tas a exactement 1 antécédent et celui-ci compte un tas de moins.
Quand il est supérieur, cela donne plus de choix. Par exemple 1:2:3:4 succède à lui-même mais aussi à 2:1:3:4, à 2:3:1:4 et à 2:3:4:1.


Celui qui fuit les casse-tête ne vaut pas un clou.

 #3 - 11-10-2009 22:25:35

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 11×569

Un escalier dee pièces

Bon, ma méthode ne prouve rien mais j'ai testé "betement" tous les cas :
à partir des 42 partitions du chiffre 10 :

Code:

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

J'ai généré pour chacune toutes les permutations possibles. (512 en tout)

Et j'ai lancé une fonction de calcul (en PHP, je n'avais que ça sous la main) :

Code:

function escalier($tasdepieces) {
 $pos_actuelle = $tasdepieces;
 $pos_precedente = array();
 while ($pos_actuelle != $pos_precedente) {
  $pos_precedente = $pos_actuelle;
  $nb_tas = count($pos_actuelle);
  for ($i = 0; $i < $nb_tas; $i++) {
   $pos_actuelle[$i]--; // on enleve une pièce
   if ($pos_actuelle[$i] == 0) unset($pos_actuelle[$i]); // on enleve un tas
  }
  $pos_actuelle[] = $nb_tas; // rajoute le tas
  $pos_actuelle = array_values($pos_actuelle); // evite les problème de clef
 }
 return $pos_actuelle;
}

Aucune position de départ ne donne autre chose que 1 2 3 4.

J'en ai profité pour calculer le nombre d'étapes, en posant systématiquement la nouvelle pile à droite des premières.

Les cas les plus défavorables sont :
3 3 2 1 1, 3 2 2 2 1 et 3 2 2 1 1 1 avec 16 mouvements.

 #4 - 13-10-2009 17:53:27

Enelya!
Professionnel de Prise2Tete
Enigmes résolues : 13
Messages : 117

Un escalie rde pièces

Oui, cela aboutis obligatoirement à cette finalité, et cette position n'est plus modifiable.
Si la taille de la plus grande colonne est égale au nombre de colonne, et si toute les colonnes à valeur entière de la taille maximum à la taille 1 sont représenté, il est impossible de sortir de cette situation.

Pour calculé s'il existe une position final comme ceci, le calcul est le suivant :

Soit x le nombre de jeton de la plus grande colone.
Soit z le nombre total de jeton.

Si x = au nombre de piles.
Et Si z = x² - (x*(x-1))/2.
Nous serrons donc dans une position type :
x ; x-1 ; x-2 ; x-3 ; [...] ; x-(x-1)

Dans le cas final présent, nous avons x=4
z = 4² - (4*(4-1))/2
z = 16 - (4*3) / 2
z = 16 - 6
z = 10.
Il y a bien dix jetons, donc nous sommes dans une position final type :
4 3 2 1.
Une fois arrivés dans cette position, celle-ci ne peux plus être modifié.

Exemple avec x = 17 et z = 153.
z =? 17² - (17*(17-1))/2
z =? 289 - 136
z = 153
Une position type x ; x-1 ; x-2 ; x-3 ; [...] ; x-(x-1) est donc inévitable.

 #5 - 13-10-2009 19:45:34

Bamby2
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 152

Un escalierr de pièces

c'est l'unique position invariante, reste a voire pourquoi toutes situations y arrivent big_smile

j'edite des que j'ai des idées big_smile

EDIT1:
a ben, je viens de tomber sur un contre exemple big_smile
655322
6544211
754331
664322
6553211
754421
664331
655322

et en l'étudiant un peu c'est logique, lorsque 2 valeurs sont égales, on se retrouve avec un "trou" ailleurs dans l'escalier, et donc a un moment on va avoir 1 étape sans avoir de 1, et donc on va se retrouver avec 2 chiffres crées identiques, et donc on perpétue l'erreur initial.

par contre avec une sommes de 10, il est impossible de crée une liste avec 2 valeurs égales et un trou.. je pense donc qu'a 10 toutes situation arrive a l'equilibre

EDIT2:
ca semble pas suffisant, j'ai pu trop de temps, je regarderai ca plus tard !

 #6 - 13-10-2009 22:36:06

gabrielduflot
Expert de Prise2Tete
Enigmes résolues : 34
Messages : 609

Un escalier d epièces

je vais le faire dans le cas général
Il y aura [latex]{n(n+1)}\over2[/latex] pieces qu'il faut arriver à placer sur n colonnes qui aura 1;2;3;....;n

On part avec k colonnes avec 0<k<=[latex]{n(n+1)}\over2[/latex]
on note [latex]n_k[/latex] le nombre de pièces qu'il y a à la colonne k
on range les colonnes dans l'ordre décroissant donc [latex]n_1[/latex] est le nombre le plus grand

On va faire dans un premier temps [latex]n_1[/latex] étapes pour arriver à [latex]k_1[/latex] colonnes où 0<[latex]k_1[/latex]<n

Si il existe dans les [latex]k_1[/latex] colonnes au moins deux colonnes [latex]k_i et k_{i+j}[/latex]où il y a le meme nombre de pieces.
On va faire [latex]k_i[/latex]étapes jusqu'à ce que toutes les colonnes aient un nombre différents de pièces. Dans ce cas il y aura [latex]k_2[/latex] colonnes avec toutes avec des pièces différentes.
Ensuite on refait le même système en faisant [latex]n-k_2+1[/latex] étapes et pour arriver au résultat que l'on veut.

Maintenant il faut montrer que si l'on part d'une combinaison on n'y arrivera jamais à la même combinaison c'est à dire que cela soit cyclique.

 #7 - 14-10-2009 12:13:39

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

un escaloer de pièces

La réponse est "oui" pour 10 pièces.

Je pense l'avoir vérifié sur excel en balayant toutes les combinaisons.
Par contre, je n'ai pas de démo complète... mais des bribes d'idées :

1. Si il existe une position invariante par l'opération, celle-ci ne peut être que 4 3 2 1.
En effet : la position invariante contient une unique pile de 1 (pour conserver le nombre de pile). Toutes les autres piles vont être diminuées de 1, donc la pile la plus haute doit être engendrée par la nouvelle pile créée et toutes les valeurs entre 1 et cette hauteur doivent être présentes.
Donc, les piles invariantes sont du type 1 2 .... n.

rem : si on démarre avec un nombre de pièces différent de P(1)=1 P(2)=3 P(3)=6 P(4)=10 P(5)=15 etc, il n'y a pas de position invariante, mais des périodes de tailles n+1 pour un nombre de pièces initiales compris entre P(n) et P(n+1).

2. J'ai ensuite essayé de trouver une mesure de l'écart par rapport à la position invariante et de montrer sa décroissance stricte...
Je n'ai rien trouvé : si on prend, par exemple, la somme des écarts (en valeur absolue) de la position actuelle ordonnée par rapport à la position invariante, on observe que ça décroit mais pas de façon stricte, donc ça ne prouve rien.

Donc je sèche...

Si on part de 3 3 2 1 1, il faut 12 opérations pour arriver à 4 3 2 1, alors que visuellement, c'est proche de 4 3 2 1 (plus proche que 6 4 qui ne demande que 2 opérations).
Tous les chemins passent par 5 3 2.

J'attends avec impatience les indices ou la solution pour m'extasier sur le beau modèle mathématique qu'il convient de coller sur ce problème.

 #8 - 14-10-2009 22:53:23

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

UUn escalier de pièces

Beaucoup de choses intéressantes, et en effet le nombre de pièces "10" n'est pas choisi au hasard ( comme dans le problème de l'électricien ) .  Il est toujours difficile de donner des pistes de recherches sans passer pour un malin qui crâne parce qu'il a la solution ou au contraire de trop en dire et ne plus rien laisser à chercher .     

http://img73.imageshack.us/img73/3313/pilesdepices2.jpg

Les pièces sont représentées en jaune et en bleu . On choisit de prendre les pièces au dessous de chaque pile ( en jaune ) et de les remplacer par leurs symétriques ( en rouge ) par rapport à la bissectrice (D) . On fait ensuite subir à l'ensemble des pièces ( rouges et bleues ) une translation de vecteur u , on obtient alors la nouvelle disposition des pièces . Je vous encourage à suivre en détail le mouvement de n'importe quelle pièce à l'aide de ce schéma .

Vasimolo

 #9 - 16-10-2009 10:38:21

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

Un esscalier de pièces

Merci pour l’indice qui éclaire tout !

On suppose que l’on démarre avec les piles (ou colonnes) ordonnées de la plus grande en X=0 vers la plus petite et on note la hauteur de chaque pièce par son ordonnée Y (Y=0 pour la pièce du bas).

http://www.prise2tete.fr/upload/dylasse-piecespos1.jpg
exemple : Position 1 :

En prenant les pièces en bas de la pile, il est clair qu'une opération de distribution conserve les pièces sur une même ligne de niveau. J’appelle ligne de niveau n une ligne pour laquelle X + Y = n.

En effet, une distribution revient à faire : si Yi=0, Yf=Xi et Xf=Yi et sinon, Yf=Yi-1 et Xf=Xi+1.

Distribution : passage de pos1 à pos2

http://www.prise2tete.fr/upload/dylasse-piecespos2.jpg
Position 2 :

Donc, si on prend comme mesure du désordre E d’une position la somme des niveaux de chaque pièce, ce désordre E est invariant par distribution.


Si la colonne créée (ou n’importe quelle autre colonne d'ailleurs) possède moins de pièces que celle sur sa droite, il convient de trier les colonnes. Ce tri revient à déplacer sur la gauche les pièces n’ayant pas de voisins à gauche.

Tri : passage de pos2 à pos3.

http://www.prise2tete.fr/upload/dylasse-piecespos3.jpg
Position 3 :

Le tri diminue le désordre (puisqu’au moins une pièces passe à Xf=Xi-1).


Démontrons maintenant que l’on obtient toujours la position 4 3 2 1, qui correspond au désordre minimal E=20 :

Si l’on n’est pas sur la position 4 3 2 1, il existe donc une colonne pour laquelle la pièce supérieure n’est pas sur le niveau 3, et il existe aussi une colonne pour laquelle il y a une pièce sur le niveau 4.

Par distributions successives, le trou du niveau 3 et la pièce du niveau 4 se déplacent vers la droite sur leur ligne de niveau respective.

Le trou se déplaçant sur le niveau 3 va prendre successivement 4 positions, la pièce se déplaçant sur le niveau 4 va prendre successivement 5 positions. Donc, 4 et 5 étant premiers entre eux, au bout de 20 distributions maxi, on aura le trou niveau 3 sur une colonne et la pièce niveau 4 sur la colonne juste à droite, on pourra donc faire un tri et diminuer le désordre E.

Cette opération réduit de 1 au moins le désordre et peut être répétée tant que l'on ne se trouve pas sur la position 4 3 2 1, donc on atteindra E=20 (donc la position 4 3 2 1).

Cqfd.


Rem : la démonstration s’applique pour n’importe quel nombre de pièces initiales. Si le nombre de pièces permet d’avoir une position où tous les niveaux sont pleins (1 3 6 10 15 21 etc), cette position invariante est la position finale. Sinon, on obtient une suite périodique de positions (de désordre le plus faible possible), les positions de la périodes correspondant au déplacement des pièces sur le niveau incomplet (par distribution mais sans tri) : d’où la période égale au nombre de positions du niveau incomplet.

Encore un beau problème de Vasimolo ! Bravo !

 #10 - 16-10-2009 12:24:40

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Un scalier de pièces

C'est tout à fait ça dylasse smile

On peut aussi laisser la gravité faire son oeuvre , on ne réorganise pas les piles et le passage à gauche va réduire les niveaux de certaines pièces sous l'action de leurs poids .

Encore bravo car l'indice était minimal smile

Vasimolo

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Mots clés des moteurs de recherche

Mot clé (occurences)
Calcul escalier sur mesure (4) — Enigme mathematique+tas de pieces (3) — Les systemes perpetuellement invariants et similaires (3) — Systemes distribution des pieces (2) — Reponce de fitting piece (2) — Escalier (2) — Probleme math escalier (2) — Reponse de fitting piece (2) — Recherche mathematiques escalier la grenouille (2) — On peut monter un escalier une ou deux marches a la fois (2) — Escalier position 4 claire 08 (1) — Enigme sur les escaliers (1) — Interrupteur va et vient (1) — Enigmes denombrement (1) — Probleme marches escalier par 1 et par 2 (1) — Enigmes mathematiques escalier (1) — Escalier 1/2 niveau (1) — Grenouille escalier (1) — Distribution pieces escalier (1) — Denombrement grenouille (1) — Enigmes sur escalier (1) — Fitting pieces reponses (1) — Utiliser 5 chiffres (1) — Enigme tas pieces pile (1) — Interrupteur schema 3 (1) — Maths denombrement pieces monnaie (1) — Fitting pieces level 11 (1) — Problemes mathematiques 15 pieces (1) — Que veut dire des pieces de monnaie sur un escalier? (1) — Fitting pieces reponse (1) — Trouver les possibilites de monter les marches d escalier math (1) — Suite arithmetique grenouile escakier (1) — Tas de pieces casse tete (1) — Avec dix pieces faire 4 tas (1) — Pile pieces droite et pile pieces en desordre (1) — Enigme escalier (1) — Mathematique escalier (1) — Soluce fitting pieces (1) — Probleme en maths d escalier (1) — Schema 3 va et vient (1) — Une grenouille est au pied d un escalier de 13 marches (1) — Devinnete des tas de pieces (1) — Denombrement grenouille escalier 18 marches (1) — Solution fitting pieces level 11 (1) — Suite 10 15 21 78 (1) — On prend 10 tas de 10 pieces (1) — Calcul sur les marches math (1) — (1) — Enigme sur escalier (1) — Schema va et vient 3 interrupteurs (1) — Pour monter un escalier on peut a chaque pas choisir de monter une marche ou de monter deux marches (1) — Php fonction escalier (1) — Fitting pieces reponse (1) — Quel est la devinette des trois tas de pieces (1) —

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