Inscription / Connexion Nouveau Sujet
Niveau 3 *
Partager :

Challenge n°206 : "jeu"***

Posté par
puisea Posteur d'énigmes
10-02-07 à 20:15

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 !

Posté par
caylus
re : Challenge n°206 : "jeu"*** 10-02-07 à 21:20

perduBonsoir,


4$ \fbox{35400}
f(n+2=f(n+1)+f(n)+n+1 avec f(0)=0;f(1)=1

Posté par
jamo Moderateur
re : Challenge n°206 : "jeu"*** 10-02-07 à 22:31

gagné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.

Posté par
Eric1
re : Challenge n°206 : "jeu"*** 10-02-07 à 23:03

perduOn 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

Posté par
manpower
re : Challenge n°206 : "jeu"*** 10-02-07 à 23:57

gagné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é):
a_{2n}=2a_{2n-1} et a_{2n+1}=2a_{2n}+1 (où a_0=0 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.

Challenge n°206 :  jeu

Ainsi, pour une tablette à 20 cases, il faudra pas moins de 3$ \red \rm 699050 coups !

Merci, puisea, pour cette belle énigme.

Posté par
smil
re : Challenge n°206 : "jeu"*** 11-02-07 à 00:14

gagnéje propose 699 050 coups

Posté par
vincprof
re : Challenge n°206 : "jeu"*** 11-02-07 à 00:15

gagnéje propose 699050

Zut smil m'a grillé!!

Posté par
Nofutur2
re : Challenge n°206 : "jeu"*** 11-02-07 à 06:18

gagné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.

Posté par
geo3
re : Challenge n°206 : "jeu"*** 11-02-07 à 09:47

perduBonjour
Le nombre de coups pour remplir une tablette, initialement vide, de 20 cases (n=20) est de        5$\red35400
car la relation de récurrence est f(n+2) = f(n+1) + f(n) + n + 1
A+

Posté par
zabusa
re : Challenge n°206 : "jeu"*** 11-02-07 à 10:16

perduje pense qu'il faut 90 coups pour n=20

Posté par nobody (invité)re : Challenge n°206 : "jeu"*** 11-02-07 à 10:24

Bonjour,

je pense que la question est plutôt : quel est le nombre minimum de coups ....

La solution est
\frac{2^{n+2}-(-1)^n-3}{6}, 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) ?

Posté par
plumemeteore
re : Challenge n°206 : "jeu"*** 11-02-07 à 11:48

gagné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) !

Posté par
evariste
re : Challenge n°206 : "jeu"*** 11-02-07 à 18:54

perdu 1 398 101 coups

si n pair       un=2un-1 +1
si  n impair    un=2un-1

Posté par
Youpi
re : Challenge n°206 : "jeu"*** 11-02-07 à 20:10

gagnéBonsoir

je trouve que pour remplir une tablette initialement vide de 20 cases il faut jouer 4$ \red\rm\fbox{699050} coups

voici un tableau excel qui présente le nombre de coups à jouer en fonction du nombre de cases à remplir:  

Challenge n°206 :  jeu

Posté par Teebo (invité)re : Challenge n°206 : "jeu"*** 12-02-07 à 14:48

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

Posté par
kiko21
re : Challenge n°206 : "jeu"*** 12-02-07 à 14:59

gagnéBonjour,

Il faut 5$ \red \fbox{\textrm 699050 coups} pour parvenir à remplir une tablette, initialement vide, de 20 cases (n=20).

Merci Puiséa, et à bientôt, KiKo21.

Posté par
lo5707
re : Challenge n°206 : "jeu"*** 13-02-07 à 10:19

perduBonjour,

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

Posté par
piepalm
re : Challenge n°206 : "jeu"*** 13-02-07 à 12:07

gagné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

Posté par
simon92
re : Challenge n°206 : "jeu"*** 13-02-07 à 14:06

perdubonjour,
ca me parait trop simple, mais j'en trouve qu'un avec un rapport de 2/3, voila, merci pour l'énigme!
simon

Posté par
gloubi
re : Challenge n°206 : "jeu"*** 14-02-07 à 14:22

gagnéBonjour,

Pour n=20, il faut jouer 699 050 coups.

Merci pour l'énigme,
gloubi
-

Posté par gyu (invité)Challenge n°206 : "jeu" 15-02-07 à 20:28

gagné699050

Posté par sarah007 (invité)re : Challenge n°206 : "jeu"*** 17-02-07 à 18:45

perduil faut 6 coups

Posté par
Nyavlys
re : Challenge n°206 : "jeu"*** 18-02-07 à 17:00

gagné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 !

Posté par
gix09
re : Challenge n°206 : "jeu"*** 19-02-07 à 11:10

perdu113

Posté par geff (invité)jeu 21-02-07 à 16:16

perduPour remplir une tablette de 20 cases vides, il faut:
36 coups

Posté par jouddy (invité)re : Challenge n°206 : "jeu"*** 23-02-07 à 08:09

gagnéPour n pair, on a besoin de 2^n-1 + 2^n-3 + ... + 1 coups.
Pour n=20, cela fait 699050 coups.

Posté par
puisea Posteur d'énigmes
re : Challenge n°206 : "jeu"*** 24-02-07 à 10:57

Bonjour

Merci à tous de votre participation !

Posté par
plumemeteore
re : Challenge n°206 : "jeu"*** 24-02-07 à 21:42

gagnébonsoir à Eric1 qui a trouvé un résultat vingt fois trop petit
citation de Boileau
"Vingt fois sur le métier, remettez votre ouvrage."

Posté par
minkus Posteur d'énigmes
re : Challenge n°206 : "jeu"*** 25-02-07 à 12:22

Salut

Dis Simon92 j'ai l'impression que tu t'es trompe d'enigme non ?

Posté par
simon92
re : Challenge n°206 : "jeu"*** 20-03-07 à 14:16

perdu
je suis vraiment trop bête!

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 69:38:28.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !