exercice difficile :jeu de sauts

[invited8d9e610]

Bonjour a tous il y a de cela un moi
Mon ami a participé aux sélections d'olympiades
Et il est tombé sur un exercice plutôt pas mal
Moi j'ai essayé de le faire mais le truc c'est que je bloque au milieu
Voilà l'exercice :
Alexendre a écrit les nombres 1,2,3,4,5.......n rangé sur un rond
Et la il a commencé avec 1 en l'effaçant. Il a sauté le 2 et il a effacé le 3 et la il a sauté le 4
Et effacé le 5 .... Comme ça jusqu'à ce qu'il ne reste qu'un seul nombre sur le rond
Par exemple si n=20 il effacera dans le premier tour les nombres 1,3,5,7,9,11,13,15,17,19
Et il aura laissé les nombres 2,4,6,8,10,12,14,16,18,20
Et dans le deuxième tour il effacera les nombres 2,6,10,14,18 et laissera les nombres 4,8,12,16,20
Et dans le 3eme tour il effacera les nombres 4,12,,20 et laissera les nombres 8,16
Et comme il a effacé le dernier nombre 20 alors il commencerait pas 8en l'effaçant et il restera 16
Comme le dernier nombres
Si n=2016, quel serait alors le dernier nombre sur le rond


Bon pour moi j'ai remarqué que dans le premier tour il effacerait tous les nombres impair
Et dans le deuxième tour il effacerat tous les nombres sauf les multiples de 4 dont 2016
En fait partie
Le 3eme tour il effacera tous les nombres sauf les multiples de 8
Meme chose pour le 4 eme tour il restera les multiples de 16
Et puis pour le 5 tour il restera les multiples de 32 et 2016 en fait partie
Et puis il effacera les multiples de 32 et laissera 64 et
La je bloque parceque 2016 sera effacé enfin je ne sais plus
Parceque 2016 n'est pas multiples de 64 bref la je bloque
Svp aidez moi
Meeci d'avance
-----

[zenxbear]

donc il reste 64 , 128 , ... 1984

et tu effaces 128 , 128+128 ...
il reste 64 , 192 , ... 1984 (pas de 128)

tu effaces 64, 64+ 256, ...
il reste 192, 192+256, ...., 1984

tu effaces 192, 192+512, ...
il reste 192+256=448, 448+512, 448+1024, 1984

tu effaces 448, 448+1024
il reste 448+512, 1984

il reste 1984

[zenxbear]

Ton calcul pour n=20 est faux, parce que je trouve 8. Tu t'es trompé à la dernière ligne. comme tu as supprimé le 20, au tour suivant, tu gardes le premier terme, (8) et supprime 16. Si j'ai bien compris le probleme.

J'ai écris une petite routine pour voir ce que ca donnait pour plein de valeur de n.

Surprise, les valeurs pour des n différents sont quasi cycliques. En gros, si k est tel que , alors le nombre qui reste à la fin est . Et si n=2^k, il restera 2^k à la fin.

par exemple pour 2016, et bien 2x(2016-1024)= 1984!
à vérifier d'ou ca vient, et comment justifier élégamment le résultat.

[zenxbear]

Finalement c'est assez trivial. F(2n)=2f(n), et f(2n+1)=2+f(2n) car a l etape 2, on eat comments avec f(2n) Mais decale d'un nombre pair sur le cercle, d'ou plus 2

[A voir en vidéo sur Futura]