Pirates et noix de coco

[theluckyluke]

Salut tout le monde, bonne année!


Voilà une petite énigme sympa :

Cinq pirates, sur une ile déserte, ont amassé une certaine quantité de noix de coco. La nuit tombe, ils veulent partager le "trésor" et ils décident alors d'attendre le lendemain pour partager les noix de coco en 5 tas égaux.

Mais, pendant la nuit, un des pirates se lève, partage les noix de coco en cinq tas égaux avec un reste d'une noix de coco qu'il jette à un singe qui passe par là. Après avoir caché sa part, il rassemble tous les tas restants et retourne se coucher.
Le second marin fait de même, ainsi que le troisième, le quatrième et le cinquième.

Le matin, le nombre de noix de coco restantes moins une est encore divisible par 5.

Quel est le nombre minimum de noix de coco que pouvait contenir le tas d'origine?


Une petite précision : quand on dit que chaque pirate fait de même, cela veut bien dire qu'ils séparent le tas en 5 tas avec à chaque fois un reste de une noix de coco qu'ils jettent aux singes.


Bonne refléxion!

[scelerat]

J'ai du me tromper quelque part : je trouve que ca n'est pas possible, un marin ne pourrait pas partager 1951160 + 1 noix de coco en une nuit. :doh:

[theluckyluke]

J'ai du me tromper quelque part : je trouve que ca n'est pas possible, un marin ne pourrait pas partager 1951160 + 1 noix de coco en une nuit. :doh:

ta solution est peut etre juste, mais il y a beaucoup mieux que ça... bien-sûr on ne va pas non plus s'attendre à un nombre du genre quelques dizaines ou centaines, mais de là à quelques millions, y a encore de la marge...


après vérification, ta solution ne semble pas marcher, je m'explique :

le premier marin prend 4/5 de 1 951 160, c'est-à-dire 1 560 928... Le second prend 4/5 de (1 560 928-1)... n'est pas un nombre entier puisque non divisible par 5...

[alben]

Bonjour,
Tu ne précises pas combien il y a de singes ni comment ils se partagent les noix.
Je trouve qu'il ont 6 noix sur un total de 15 621(surligner pour voir).
S'il ya trois singes, le mâle en prend 3, la femelle 2 et le petit 1 et sans faire de calculs :++: . Ca démontre que les singes sont plus malins et plus honnêtes

[scelerat]

Le matin, mais aussi apres chaque passage de pirate, le nombre de noix est divisible par 4 et multiple de 5 + 1, donc il s'ecrit 20k-4.
d'ou l'on deduit , on s'est affranchi des singes, et 4 et 5 etant premiers entre eux, , il reste 5116 noix le dernier matin et il y en avait 15621 au depart.

Je pataugeais parce que je cherchais sous la forme 16 + 20k, et que je ne parvenais pas a une recurrence simple.

[theluckyluke]

ouais c'est juste!


bien joué!

[Anwanamë]

Bonjour,
J'avoue etre tenue en echec par ce probleme, et ta solution est certainement juste, mais je ne comprend pas vraiment ces "N1" i1" etc... si tu as le temps, pourrais tu m'eclairer s'il te plait ?

Merci :)

[YannTM]

Je propose une autre solution, peut-etre moins intuitive, mais aussi beaucoup moins calculatoire.

Soit N la part de chaque pirate à la fin (le matin).

Soit Ui la taille du stack de coco à l'étape i.
Etape 0 c'est le matin, 1 c'est juste avant ... on part vers le passé.

On sait que :
U0 = 5N + 1

A l'étape précédente, on sait que :
Un+1 = Un + 1/4Un + 1

Soit le tas qui restera le lendemain, + la part prélevée par le pirate (1/4 du reste), +1 coco pour le singe.

Calculons U1 en fonction de N.

U1 = U0 + 1/4 U0 + 1
U1 = 5/4 U0 + 1
U1 = 5/4 ( 5N +1 ) + 1
U1 = (25N+9) / 4
U1 = 6N + 2 + (N+1) / 4

Pour quelles valeurs de N entier est-ce que U1 reste un entier ?
U1 entier <=> (N+1) /4 entier

Donc N+1 multiple de 4, ce qui donne les solutions 3, 7, 11 , 15...

Mais aussi... N = -1

Aha ! testons un peu :
N= -1, donc U0 = 5N+1 = -4 noix de coco le matin.
On en jette une au singe, il en reste donc -5, on partage en 5, chacun prend -1 coco, ça marche.

En plus de ça, si on en jette une au singe (donc -5 restant) et que un des pirates prend sa part (on ne garde que 4/5), on retombe sur ... -4 noix de coco.

Génial, avec -1 comme valeur de N, on peut mettre autant de pirates qu'on veut et répéter ce petit jeu.
Je pense que c'est la seule solution "élégante", sinon c'est bêtement calculatoire comme énigme.

[Lostounet]

Le proverbe dit 'mieux vaut tard que jamais' mais là ... Ça fait quand même 11 ans que le sujet a été posé :p

[YannTM]

Une version code sur Z3, à tester ici
https://rise4fun.com/Z3


c'est du SMT, il faut lire en notation préfixe, par exemple (>= K 0) se lit K>=0
Ou encore (U K) est la valeur de la fonction U en k, U(k)
Donc (U (+ K 1)) se lit U_K+1

Code: Tout sélectionner

(declare-fun N () Int)
(declare-fun U (Int) Int)
(assert (= (U 0) (+ (* 5 N) 1)))
(assert (forall ((K Int)) (implies (and (>= K 0) (<= K 5)) (= (U (+ K 1)) (+ (* (/ 5 4) (U K)) 1)))))
(assert (> N 0))
(check-sat)
(get-model)

Si on enleve la contrainte (assert (> N 0)) , le solver est d'accord pour dire -4, sinon il trouve
(define-fun U!1 ((x!0 Int)) Int
(ite (= x!0 1) 25596
(ite (= x!0 2) 31996
(ite (= x!0 3) 39996
(ite (= x!0 4) 49996
(ite (= x!0 5) 62496
(ite (= x!0 6) 78121
20476)))))))

Donc 78121 initialement, et il en reste 20476 le matin.
Désolé pour le déterrement de cadavres je recherchais la formulation de cette énigme qu'on m'a posé il y a longtemps, je me souvenais de l'astuce de passer en négatif, mais pas de tout l'énoncé.