par pianojo » 25 Nov 2015, 21:55
Content que tu te sois débrouillé à partir de nos indices. Comme Chan l'a expliqué, le cycle est bien lié au fait que 12 soit à la fois un multiple de 2, 3 et 4 :
Si le Ne gâteau a une noix, le N+12e aussi car N+12= N+2k avec k=6
Si le Ne gâteau a une fraise, le N+12e aussi car N+12= N+3k avec k=4.
Si le Ne gâteau a une dragée, le N+12e aussi car N+12= N+4k avec k=3.
Donc, si l'on ignore le gâteau sans décoration, le N+12e gâteau est toujours dans le même état que le Ne. Il suffit alors de regarder toutes les possibilités pour les 1ers 13 gâteaux, et de compter sur les 5 premiers, puis sur un cycle de 12, et de multiplier pour avoir les comptes totaux.
Ce problème se généralise facilement. Plus formellement, c'est un problème de PPCM (plus petit commun multiple: calcul très lié au PGCD) : 12 = PPCM(2,3,4). Quand on a N cycles comme ça, le cycle global a toujours pour période le PPCM des cycles.
Si tu veux plus d'informations pour aborder ce type de problème, notamment quand les cycles sont longs, tu peux chercher sur internet "théorème des restes chinois" et "algorithme d'Euclide". L'algorithme d'Euclide est un algorithme de calcul très rapide du PGCD, qui est une étape intermédiaire pour le théorèmes des restes chinois. Il se généralise aux polynômes.
Les algorithmes les plus rapides pour les calculs de PGCD sont des variations astucieuses de cet algorithme qui limitent la taille des données intermédiaires (en calculant avec des restes et en les recombinant par exemple), ou des algorithmes basés sur les nombres p-adiques... que tu aborderas peut-être en fin d'école d'ingénieur ou de fac, ou plus probablement dans des livres ou sur internet si les maths te passionnent.