[Indovinello] Algebrico con le monete

Buona sera a tutti. Qualche giorno fa, durante una sfida matematica fra amici, mi hanno proposto un problema del genere:

L'Orue è una valuta che dispone di due sole monete, da 3 e da 11 centesimi.
Qual'è la massima cifra che non può essere pagata esattamente?

la risposta mi han detto che è: 19 centesimi. Vi vorrei chiedere se c'è qualcuno che mi può dare una dimostrazione formale di questo risultato, cioè spiegarmi come ci si arriva, perché io non ci sono riuscito. Grazie!

Ciao Ruben96, cerco di risponderti io, con la speranza di essere chiaro..

Ovviamente potrai pagare tutte le cifre che sono multiple di 3, ovvero, per intenderci:



con .

Inoltre si possono pagare tutte le cifre della forma che però siano maggiori o uguali a 22 e tutti i numeri della forma che siano maggiori o uguali a 11.

Questo perché e , ovvero da a posso proseguire 3 alla volta, da a (grazie alla scomposizione di 11 come ) (2 alla volta) e da 22 all'infinito, grazie alla scomposizione di 22 come , posso proseguire (e quindi pagare) aumentando una cifra alla volta.

Da un punto di vista matematico (più rigoroso) la spiegazione è che da 20 a più infinito, TUTTI i numeri naturali si possono esprimere nella forma , mentre da 3 a 11 sono esprimibili in quella forma solo i multipli di 3 e da 11 a 22 solo



In definitiva, da 1 a più infinito, le cifre non pagabili con quelle monete sono:

1, 2, 4, 5, 7, 8, 10, 13, 16, 19 (questo, per quanto detto prima è quindi il maggiore non pagabile).

Spero di essere stato chiaro e di non averti confuso le idee, ma spiegare indovinelli non è mai semplice.

Chiarissimo!