Défi 8

[MikO]

On dispose de 45 pieces de monnaie tt a fait banales,
On en fait 0On retire de chaque tas la piece du sommet et on reforme un nouveau tas.
Prouvez qu'il existe k dans IN tq qu'apres k itérations on ai :
-un tas de une piece
-un tas de deux
.
.
.
-un tas de neuf

Bonne chance

[BQss]

On dispose de 45 pieces de monnaie tt a fait banales,
On en fait 0<n<46 tas comme il nous semble bon.
On retire de chaque tas la piece du sommet et on reforme un nouveau tas.
Prouvez qu'il existe k dans IN tq qu'apres k itérations on ai :
-un tas de une piece
-un tas de deux
.
.
.
-un tas de neuf

Bonne chance

1+2+3+4+5+6+7+8+9=45 lol...

[MikO]

ca n'interesse personne ? pourtant c'est tres interessant comme probleme :)

[fahr451]

très très en effet

[alben]

Bonjour,

Considérons la transformation
Il suffit de montrer que (1,2,...9) est son seul point fixe à une permutation près du fait que les transformés successifs sont en nombre fini
1 c'est un point fixe : trivial
2 il est unique : si n € à la suite finie, n-1 aussi. Donc il s'agit de nombres successifs dont le plus petit élément est un. (sinon contradiction)

PS non ce n'est pas correct, cela n'élimine pas la possibilité de cycles. désolé

[yos]

C'est l'Awélé (ce jeu africain), mais à l'envers.

[sandrine_guillerme]

Salut,



je crois que je l'ai trouvé, je vais essayé de rédiger..

je garantie pas que ça soit une bonne méthode ..

[sandrine_guillerme]

Voilà ..


Préliminaire : la configuration qu'on souhaite réaliser est une forme stable, c'est à dire qu'après une nouvelle itération, elle reste identique.

Donc, si la configuration est stable, ça signifie que le nombre de tas avant et après une manipulation est le même => il y a au moins un tas de 1, et même exactement 1 (sinon le nombre de tas diminue).

Comme un tas va disparaitre, stable => (nombre de tas = nombre de pièces dans le plus gros tas = nbTas), et le tas le plus gros est unique (car un seul tas de 1 pièce).
On a donc exactement un tas minimal de 1 pièce , et exactement un tas maximal de nbTas pièces.

nbTas ne vaut ni 1 ni 2.
Si nbTas>3, on a au moins un tas de 2 pièces, de 3 pièces, .... de nbTas-1 pièces.
Comme il y a nbTas tas, tous ces tas sont uniques (sinon il y aurait trop de tas par rapport à nbTas).
Donc dans une configuration stable, il y a exactement un tas à 1, à 2, à 3, ..., à nbTas.
Comme la somme fait 45, la configuration est forcément 1,2,3,...,9

Il reste maintenant que l'autre moitié,

à vous !

[sandrine_guillerme]

Personne pour confirmer alors ? :cry:

[yos]

Jopli problème en tout cas.
Sandrine, tu as reformulé ce qu'a dit Alben. Mais c'est bien tourné.
Comme le dit Alben il reste à prouver qu'il n'y a pas de cycle d'ordre supérieur (ou qu'il y a un point fixe).

[Imod]

Bonjour à tous , une autre idée :id:

On les hauteurs des différentes colonnes et on note le plus grand indice tel que l'on puisse réorganiser les colonnes de façon à ce que : avec pour tout , . Si c'est fini sinon deux cas de figure :

1°) S'il reste au moins une colonne après .

On peut supposer que a au moins i+1 éléments sinon à l'étape suivante , on créerait à partir des éléments prélevés au sommets des piles une colonne qui aurait cette particularité . Alors à l'étape suivante on obtient des colonnes avec un i plus grand qu'à l'étape précédente .

2°) S'il n'y a que i colonnes .

est au moins égal à i+1 et à l'étape suivante on crée au moins une colonne après qui n'est pas vide et on se ramène à 1°) .

On aboutit donc à .

Imod

correctif : Il y a une erreur dans mon raisonnement , je regarde s'il y a moyen de la corriger .

Non c'est sans issue :--:

[aviateurpilot]

Bonjour,

Considérons la transformation
Il suffit de montrer que (1,2,...9) est son seul point fixe à une permutation près du fait que les transformés successifs sont en nombre fini
1 c'est un point fixe : trivial
2 il est unique : si n € à la suite finie, n-1 aussi. Donc il s'agit de nombres successifs dont le plus petit élément est un. (sinon contradiction)

PS non ce n'est pas correct, cela n'élimine pas la possibilité de cycles. désolé

un autre idée
s'il y a un autre point fixe tel que
alors (sinon apres la 1er ransformation on aura tas)et il exite surement tel que (sinon puisque et => )
si
alors qui n'est pas un point fixe
si
alors il exite tel que et
apres la 1er transformation on aura surement et (absurde)

[MikO]

;) ca avance a petit pas on dirait

[Imod]

Malheureusement , pas encore de solution , mais simplement une information pour ceux que celà intéresse . Il s'agit du problème du mois de l'université de Regina dont la solution tombera dans quelques jours , il va donc falloir nous dépêcher si nous ne voulons pas être grillés...

Imod

[sandrine_guillerme]

Salut Imod, merci pour l'info ..

Tu peux me dire la date quand stp ? Parceque là je perso je suis en plein periode de préparation des partielles et j'ai pas du tout le temps pour refléchir a ce beau problème ..

donc si tu pourrais me dire quand est ce que la solution tombe et sinon

PRIERE A TOUT CEUX QUI TROUVERONT LA SOLUTION, CACHEZ LA .

Merci de votre compréhension et pour ta réponse Imod .

[mathelot]

1+2+3+..+9=45
je ne sais si c'est utile.

[manelle]

Salut Imod, merci pour l'info ..

Tu peux me dire la date quand stp ? Parceque là je perso je suis en plein periode de préparation des partielles et j'ai pas du tout le temps pour refléchir a ce beau problème ..

donc si tu pourrais me dire quand est ce que la solution tombe et sinon

PRIERE A TOUT CEUX QUI TROUVERONT LA SOLUTION, CACHEZ LA .

Merci de votre compréhension et pour ta réponse Imod .

Il y a encore le temps : il suffit d'aller sur le site de l'université Regina et de taper "problem of the month" : on a le problème en couleur , et les précédents avec les solutions : les Français font bonne figure , 7 au précédent palmarès sur 22 affichés ! le problème venait de Gauss dans un ouvrage d'arithmétique .
Merci en tout cas de nous faire connaître ce site .
Il faut peut-être mieux exprimer les choses mais ALLEZ SANDRINE !
Ce que cherchent les autres avec le groupe symétrique est peut-être trop compliqué .

[MikO]

j'aurai pu en effet donner le reference, en tt cas malgres son aspect facile c'est bel et bien un exercice tres difficile :)

EDIT : lool mathelot

[mathelot]

je regarde le formalisme suivant:
on définit un vecteur à 45 coordonnées entières :
= nombre de tas à l'étape n de cardinal i ()
alors:

où A est une matrice carrée 45x45 nilpotente et un vecteur colonne avec un "1" sur une coordonnées et les autres coordonnées à zéro.
je vais regarder si il y a une relation de récurrence sur les

[sandrine_guillerme]

On va voir, on va voir,

Merci pour tes encouragement manelle ! (C'est vraiment dommage que j'ai deux semaines d'examen a partir du 8janvier) et je ne suis pas très ajour !!!!!!!!!
:mur: