Enigme Absolument différent @ Prise2Tete

nodgim · #1

Bonjour à tous.
Soit une suite S0 ordonnée de n entiers positifs. Un algorithme crée une suite S1 de cette façon: le kième nombre de S1 est obtenu par la valeur absolue de la différence entre le kième et le (k+1)ième nombre de S0, le dernier étant obtenu par la valeur absolue de la différence entre le 1er et le dernier nombre de S0.
Après avoir obtenu S1, on recommence pour calculer S2, puis S3...

Trouver une suite initiale S0 qui finira par une suite de n zéros et qui sera passée par un maximum d'itérations. Si en plus vous trouvez S0 telle que la somme des n entiers est minimale, vous serez un champion.

Bon amusement.

elpafio · #2

Bonjour,

Pour N=4, je propose:
S0 = ( 1, 3, 7, 14 ) qui nous amène à la suite S10 = ( 0, 0, 0, 0 ).
10 itérations.
Somme des N entiers: 25.
S0 = ( 0, 2, 6, 13 ) nous amène aussi à la suite S10 = ( 0, 0, 0, 0 ).
Somme des N entiers: 21.

Pour N=2, je propose S0 = ( 0, 1 ) qui nous amène à la suite S2 = ( 0, 0 ).
2 itérations.
Somme des N entiers: 1.

Pour N autre que 2 ou 4, S0 = ( 1, 1, 1, 1, [...], 1 ) nous amène à la suite nulle en une itération.
Somme des N entiers: N.

Suites à suivre...

nodgim · #3

Je n'avais pas vu ta 1ère solution, qui n'est pas mal du tout. Comment l'as tu obtenue ?
Sinon, il y a mieux et pour moins cher, mais en plus long....

irmo322 · #4

Je pense qu'il est possible d'avoir autant d'itérations qu'on le souhaite.

Je prends un entier i et je définis la suite S0:
1 1 1 1 1 ... 1 0 0 0 0 0 0 ... 0 avec [latex]2^i[/latex] fois le nombre 1 et le même nombre de zéro.
Je conjecture qu'il faut exactement [latex]2^i[/latex] itérations afin d'arriver à la suite nulle.

Avec ça, il n'existe pas de champion

PS: J'ai bien essayé de simuler ce problème sur mon ordi mais rien que pour i=30 ça sature la mémoire vive...!

nodgim · #5

Irmo, tu es sur la bonne voie, mais on peut faire mieux.

dhrm77 · #6

irmo322 a écrit:
Je pense qu'il est possible d'avoir autant d'itérations qu'on le souhaite.

Je prends un entier i et je définis la suite S0:
1 1 1 1 1 ... 1 0 0 0 0 0 0 ... 0 avec [latex]2^i[/latex] fois le nombre 1 et le même nombre de zéro.
Je conjecture qu'il faut exactement [latex]2^i[/latex] itérations afin d'arriver à la suite nulle.

Avec ça, il n'existe pas de champion

PS: J'ai bien essayé de simuler ce problème sur mon ordi mais rien que pour i=30 ça sature la mémoire vive...!

je viens de simuler pour i=4, et je trouve ([latex]2^i[/latex])+1 itérations

PS: je n'arrive pas a inserer un '+' dans une formule Latex, y -a-t-il un probleme?

irmo322 · #7

@dhrm: En effet, c'est plutôt [latex]2^i plus 1[/latex] itérations que [latex]2^i[/latex].

nodgim · #8

Oui c'est 2^i + 1, mais on peut faire mieux, et pour moins cher...

dhrm77 · #9

pour tout n on peut faire 2^n-1 fois le zero suivi d'un 1.
Et ca donne pour 2^n chiffres, 2^n iterations.

Par exemple:
00000001 nous fait 8 iterations.

PS: on trouve la suite de irmo322 a mi-chemin.

nodgim · #10

Bravo Dhrm.
En fait le 1 peut être placé où on veut.
Algorithme avec un seul 1:
....00010000...... sans frontières
........11000.......
.......101........
......1111......
.....10001.......
etc..

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 05-05-2012 11:54:53

Absolumeent différent

#0 Pub

#2 - 05-05-2012 15:17:57

absoliment différent

#3 - 05-05-2012 17:00:58

absilument différent

#4 - 08-05-2012 00:18:30

absolyment différent

#5 - 08-05-2012 09:30:24

Absoluemnt différent

#6 - 08-05-2012 12:34:13

Abbsolument différent

irmo322 a écrit:

#7 - 08-05-2012 14:22:50

Absoluemnt différent

#8 - 08-05-2012 16:50:56

absolument difdérent

#9 - 09-05-2012 11:39:34

Absolument dfférent

#10 - 09-05-2012 18:13:16

Absolument ifférent

Réponse rapide

Sujets similaires

Pied de page des forums