Dm de 1erL

[fiona]

bonjour à tous j'aurais besoin d'aide pour cette exercice que je ne comprend pas, dont voici l'énoncé:
au pays des pierres, la monnaie s'appelle le caillou, qu'on écrit C avec de traits dessus.
les pièces ont pour valeurs 1caillou,2caillou,4caillou,8,caillou,16caillou,32caillou,64caillou,128caillou,256caillou,512caillou.
montrer qu'on peut payer n'importe quelle somme de 1à 1023 caillou sans jamais utiliser plus d'une pièce de chaque sorte.
merci de votre aide, bonne journée à tous...

[Sphinx]

Bonjour Fiona!
Je ne sais pas si tu as déjà eu affaire à l'écriture binaire des entiers mais tu remarqueras que chaque nombre de 0 à 1023 peut s'écrire en binaire en 10 chiffres ou moins(chaque chiffre valant 0 ou 1).Quand c'est 0,pas de pièce,quand c'est 1,une pièce.C'est aussi simple que ça!Il se trouve que 1024= .Aussi pour payer 1024,il te faudrait une 11ème pièce valant 1024 cailloux,or cela ne va que jusqu'à 512 cailloux.
Si tu as fait les suites géométriques,tu remarqueras que 1+2+4+8+...+512= ,soit 1023.
Ciao et bonne continuation!

[flight]

les pièces ont pour valeurs 1caillou,2caillou,4caillou,8,caillou,16caillou,32c aillou,64caillou,128caillou,256caillou,512caillou.
montrer qu'on peut payer n'importe quelle somme de 1à 1023 caillou sans jamais utiliser plus d'une pièce de chaque sorte.

salut

visiblement on dispose d'un numeraire ou chaque pièce est une puissance de 2
2^0, 2^1,2^2, ..,2^9.

prenons par exemple un total de 1023 cailloux
la question est de savoir tout simplement si on peut decomposer1023 en une somme de termes contenant du 2^k avec k appartenant à {0,1,2,3,4,5...,9}

posons 1023=SOM(2^k) pour k compris entre 0 et une certaine valeur n comprise entre 0 et 9

on sait que som(2^k) pour k compris entre 0 et n vaut :

S=2^(n+1)-1 on doit donc trouver n tel que


2^(n+1)-1=1023 soit n=9 et donc 1023 s'ecrit comme somme de terme en 2^k pour k compris entre 0 et 9
et donc 1023 utilise une fois toutes les sortes de pièces comprise entre 1caillou et 512 caillou.


si à present on cherche à composer une somme depassant 1023 avec le numeraire dont on dispose , par exemple 1024
est il possible de la faire en utilisant une fois seulement une pièce de chaque sorte

1024=2^10 donc c'est pas possible de composer avec le numeraire proposé.


a+

[fiona]

merci de votre aide! bonne journée à vous 2!