Casse-tête qui défie l'approche de la force brute?

Question

J'ai acheté un DVD vierge pour enregistrer mon émission de télévision préférée. Il est venu avec 20 autocollants numériques. 2 de chaque chiffre de '0' à '9'.
Je pensais que ce serait une bonne idée d'étiqueter numériquement ma nouvelle collection de DVD. J'ai collé l'autocollant '1' sur mon premier DVD enregistré et j'ai mis les 19 autocollants restants dans un tiroir.
Le lendemain, j'ai acheté un autre DVD vierge (recevant 20 nouveaux autocollants avec celui-ci) et après avoir enregistré l'émission, je l'ai étiqueté '2'.
Et puis je me suis demandé : quand les autocollants seront-ils épuisés et que je ne pourrai plus étiqueter un DVD?
Quelques lignes de Python, non?

Pouvez-vous fournir du code qui résout ce problème avec un temps d'exécution raisonnable?

Modifier : La méthode de force brute prendrait simplement trop de temps pour s'exécuter. Veuillez améliorer votre algorithme afin que votre code puisse renvoyer la bonne réponse en, disons, une minute?

Crédit supplémentaire : Et si les DVDs étaient livrés avec 3 autocollants de chaque chiffre?

Answer 1

Voici quelques réflexions sur la borne supérieure démontrée par @Tal Weiss :

Le premier nombre à 21 chiffres est 10^20, moment auquel nous aurons, au maximum, 20 * 10^20 autocollants. Chaque DVD supplémentaire nous coûtera alors, au moins, 1 autocollant net, donc nous aurons certainement épuisé nos autocollants d'ici 10^20 + 20 * 10^20, ce qui équivaut à 21 * 10^20. Il s'agit donc d'une borne supérieure de la solution. (Pas une borne supérieure particulièrement serrée en aucune manière ! Mais une qui est facile à établir).

En généralisant le résultat ci-dessus à la base b:

• chaque DVD est livré avec 2b autocollants
• le premier DVD qui nous coûte 1 autocollant net est le numéro b ^ (2b), moment auquel nous aurons au maximum 2b . b ^ (2b) autocollants
• nous aurons donc certainement épuisé nos autocollants d'ici b ^ (2b) + 2b . [b ^ (2b)], ce qui équivaut à (2b + 1)[b ^ (2b)]

Ainsi par exemple si nous travaillons en base 3, ce calcul donne une borne supérieure de 5103 ; en base 4, elle est de 589824. Ce sont des nombres avec lesquels il sera beaucoup plus facile de forcer la résolution mathématique.