Bonjour à tous !
Le jeu consiste à essayer de placer n pions dans les n cases d'une tablette supposée vide au départ.
A chaque coup, le joueur peut :
- soit jouer sur la première case,
- soit jouer sur la case qui suit la première case occupée.
Jouer signifie poser ou enlever un pion dans le cas où l'on joue, suivant que celle-ci est vide ou non.
Exemple pour n = 3 :
Je pose un pion dans la case 1
Je pose un pion dans la case 2
J'enlève le pion de la case 1
Je pose un pion dans la case 3
Je pose un pion dans la case 1
>> 5 coups
Exemple pour n = 4 :
Je pose un pion dans la case 1
Je pose un pion dans la case 2
J'enlève le pion de la case 1
Je pose un pion dans la case 3
Je pose un pion dans la case 1
J'enlève le pion de la case 2
J'enlève le pion de la case 1
Je pose un pion dans la case 4
Je pose un pion dans la case 1
Je pose un pion dans la case 2
>> 10 coups
Question : combien faut-il de coups pour parvenir à remplir une tablette, initialement vide, de 20 cases (n=20) ?
Bonne chance à tous !
Bonsoir,
soit Un le nombre de coups pour remplir (ou vider) une tablette de n cases.
On a : U2=2 U3=5 U4=10
Pour remplir une tablette de n cases, il faut :
1) Remplir les n-1 premières cases
2) Vider les n-2 premières cases
3) Remplir la case n
4) Remplir les n-2 premières cases
On a donc la relation de récurrence suivante :
Un = U(n-1) + 2*U(n-2) + 1
avec U2=2 et U3=5
Donc :
U4=5+2*2+1=10
U5=10+2*5+1=21
U6=21+2*10+1=42
U7=42+2*21+1=85
U8=170 U9=341 U10=682 U11=1365 U12=2730 U13=5461 U14=10922 U15=21845
U16=43690 U17=87381 U18=174762 U19=349525 U20=699050
Il faut donc 699050 coups pour remplir la tablette.
On appelle Un le nombre de coups pour remplir n cases.
Pour passer au rang suivant, il faut:
- remplir les n cases ->U(n)
-Enlever la deuxieme, troisieme,...,n-1 ième ->n-2
-Enlever la première->1
-Mettre la n+1 ième->1
-Remplir les n-1 cases->U(n-1)
Donc: U1=1
U2=2
U(n+1)=U(n)+n+U(n-1)
Donc U3=2+2+1=5
U4=5+3+2=10
U5=10+4+5=19
...
U10=276
...
U15=3177
...
U20=35400
ma réponse35400
Il faut donc être tres patient
Bonsoir,
Sauf erreur, la suite qui donne le résultat pour une tablette de dimension n est donnée par la double formule de récurrence suivante (fonction de la parité):
et (où et a_1=1).
En fait, le rôle symétrique des zéros et des uns (cases vides ou pleines) permet d'affirmer qu'il faut autant de coup pour vider n cases que pour en remplir n.
Ainsi on peut utiliser les deux rangs précédents.
Par exemple pour n=4, il faut :
-5 coups pour remplir les trois premières cases;
-2 coups pour vider les deux premières cases;
-1 coup pour remplir la case 4;
-2 coups pour remplir les deux premières cases;
soit au total 10 coups.
Avec le même raisonnement le tableau ci-dessous montre les détails par étapes.
Ainsi, pour une tablette à 20 cases, il faudra pas moins de coups !
Merci, puisea, pour cette belle énigme.
Chaque jeu peut se décomposer en plusieurs "phases".
Pour n cases, soit un le nombre de coups nécessaires :
Phase 1 : on remplit (n-1) cases soit u n-1 coups.
Phase 2 : on enlève (n-2) cases. On remarque que pour enlever les pions dans des cases consécutives, on applique la même méthode que pour les remplir, mais à l'envers, donc soit u n-2 coups.
Phase 1 : on ajoute le nième pion soit 1 coup.
Phase 1 : on remplit (n-2) cases soit u n-2 coups.
On obtient donc :
un = u n-1+u n-2 +1 +u n-2
un= u n-1+ 2* u n-2 +1.
On a facilement u1=1 et u2=2.
On vérifie que u3=2+2*1+1=5 et que u4=5+2*2+1=10 (valeurs fournies par l'énoncé).
On obtient u 20 = 699050
Il faut 699050 coups pour remplir une tablette de 20 cases.
Bonjour
Le nombre de coups pour remplir une tablette, initialement vide, de 20 cases (n=20) est de
car la relation de récurrence est f(n+2) = f(n+1) + f(n) + n + 1
A+
Bonjour,
je pense que la question est plutôt : quel est le nombre minimum de coups ....
La solution est
, soit
699050 lorsque n=20.
PS : Comment faites-vous pour répondre aussi un samedi soir ? Vous restez même le samedi soir devant votre ordinateur pour surveiller la sortie d'un défi (ou d'un challenge) ?
bonjour
je crois que c'est six cent nonante-neuf mille cinquante (699050) coups
il faut obtenir un pion solitaire en 19; je suppose qu'il faut passer par toutes les configurations : soit 2[/sup]19 coups - 1 (puisque la position vide de départ ne demande pas de coup), puis ajouter le pion en 20 et recommencer le jeu avec les dix-huit premières cases
cette fois, il faudra 2[sup]17 coups plus le jeu avec les seize premières cases
et ainsi de suite
en tout, il faudra 2[/sup]19 +2[sup]17+...8+2 coups = 2(4[/sup]9+4[sup]8+...4[/sup]1+1)coups = 2(4[sup]10-1)/3 = 699050
on remarque que la nième case a un cycle de 2[/sup]n pleins et 2[sup]n vides
le numéro du défi (206) est le palindrome du numéro de l'énigme (602) !
Bonsoir
je trouve que pour remplir une tablette initialement vide de 20 cases il faut jouer coups
voici un tableau excel qui présente le nombre de coups à jouer en fonction du nombre de cases à remplir:
Bonjour!
Bon, c'est moi poetique comme ça, mais on retrouve l'algorithme de Gray utilisé pour éviter les erreurs de transmissions...
Donc pour n=20 nous avons un nombre de coup de 699050 . J'aurais pu dire aussi que je l'avais fait à la main mais j'ai peur que ça ne soit pas très crédible
Sinon c'est le 20ème terme de la suite défini par a(2n)=2a(2n-1) et a(2n+1)=2a(2n)+1
Bonjour,
Il faut pour parvenir à remplir une tablette, initialement vide, de 20 cases (n=20).
Merci Puiséa, et à bientôt, KiKo21.
Bonjour,
j'ai peur de mal comprendre le principe, mais je me lance.
D'après ce que je comprends l'étape N=5 donnerais ceci:
Je pose un pion dans la case 1
Je pose un pion dans la case 2
J'enlève le pion de la case 1
Je pose un pion dans la case 3
Je pose un pion dans la case 1
J'enlève le pion de la case 2
J'enlève le pion de la case 1
Je pose un pion dans la case 4
Je pose un pion dans la case 1
Je pose un pion dans la case 2
J'enlève le pion de la case 3
J'enlève le pion de la case 2
J'enlève le pion de la case 1
Je pose un pion dans la case 5
Je pose un pion dans la case 1
Je pose un pion dans la case 2
Je pose un pion dans la case 3
ce qui fait 17 coups.
On a donc:
N=3 -> 5 coups
N=4 -> 10 coups (+5)
N=5 -> 17 coups (+7)
N=6 -> 26 coups (+9)
Etc...
Pour N=20 cela fait donc 401 coups
merci pour cette énigme
Si U(n) désigne le nombre de coups pour remplir un tablette de n cases, on a la relation de récurrence U(n)=U(n-1)+2U(n-2)+1 ou encore U(2p)=2U(2p-1) et U(2p+1)=2U(2p)+1, ce qui donne U(20)=699050
bonjour,
ca me parait trop simple, mais j'en trouve qu'un avec un rapport de 2/3, voila, merci pour l'énigme!
simon
Le nombre minimal de coups à jouer se calcule par une suite
u(n+1) = u(n) * 2 + (n mod 2)
u(20) = 699 050 coups !
Pour n pair, on a besoin de 2^n-1 + 2^n-3 + ... + 1 coups.
Pour n=20, cela fait 699050 coups.
bonsoir à Eric1 qui a trouvé un résultat vingt fois trop petit
citation de Boileau
"Vingt fois sur le métier, remettez votre ouvrage."
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :