Olympiades · Académique Nantes · 18 mars 2015 · Séries autres que S
Au pays de Mathami, la monnaie est le zed. On ne dispose que de billets de \(a\) et \(b\) zeds (entiers, en nombre illimité).
Partie A (on peut rendre la monnaie). \(a=3,b=5\). 1a. Payer 301 zeds. 1b. Payer 1 zed (en rendant la monnaie). 1c. Montrer qu'on peut payer toute somme entière. 2. \(a=6,b=10\) : a) payer 14 zeds ; b) quelles sommes sont impayables ?
Partie B (on ne peut pas rendre la monnaie). \(a=3\), \(b>3\) non multiple de 3. On note \(M(b)\) la plus grande somme impayable. 1. \(b=5\) : a) payer 8, 9, 10 ; b) montrer qu'on peut payer toute somme \(\ge8\) ; c) valeur de \(M(5)\). 2. \(b=7\) : a) payer toute somme \(\ge12\) ; b) valeur de \(M(7)\). 3. Valeur de \(M(8)\). 4. Placer les points \((5,M(5))\), \((7,M(7))\), \((8,M(8))\) et conjecturer une formule pour \(M(b)\) (sans justifier).
On considère maintenant \(a=5\), \(b>5\) non multiple de 5. 5. Montrer qu'on ne peut pas payer \(4b-5\) zeds avec des billets de 5 et \(b\) zeds.
A1c. Remarquer que \(10=2\times5\) et \(9=3\times3\) diffèrent de 1 : combiner ces deux paiements/rendus de monnaie pour atteindre n'importe quel entier.
B1b. Effectuer la division euclidienne de la somme \(S\) par 5 et distinguer les 5 restes possibles.
B4. Formule classique (théorème de Frobenius/Chicken McNugget pour deux nombres premiers entre eux) : \(M(b)=ab-a-b\).
B5. Chercher une identité de la forme \((4-v)b=5(1+u)\) et montrer qu'elle est impossible pour \(u,v\) entiers naturels.
A1a. \(301=59\times5+2\times3\).
A1b. On donne \(10=2\times5\) zeds et on nous rend \(9=3\times3\) zeds : net payé \(1\) zed.
A1c. Pour payer \(S\) zeds, on tend \(10S\) (billets de 5) et on nous rend \(9S\) (billets de 3) : net \(S\).
A2a. 4 billets de 6 zeds, on rend 1 billet de 10 (\(24-10=14\)).
A2b. Une somme impaire est impayable (billets tous pairs). La plus petite somme payable est 2 zeds.
B1a. \(8=3+5\), \(9=3+3+3\), \(10=5+5\).
B1b. Pour \(S\ge8\), division euclidienne \(S=5q+r\) (\(q\ge1\)) : selon \(r=0,1,2,3,4\), on ajuste avec des billets de 3 (détail dans le corrigé complet).
B1c. \(7\) zeds est impayable : \(M(5)=7\).
B2a-b. On paie toute somme \(\ge12\) ; \(11\) est impayable : \(M(7)=11\).
B3. \(M(8)=13\) (vérifié exhaustivement sur le tableau des sommes payables avec 0 à 4 billets de chaque sorte).
B4. Les points \((5,7),(7,11),(8,13)\) sont alignés selon \(M(b)=2b-3\) (formule de Frobenius \(M(b)=3b-3-b=2b-3\) pour \(a=3\)).
B5. Si \(4b-5=5u+bv\) avec \(u,v\) entiers naturels, alors \((4-v)b=5(1+u)\) : comme \(4-v\in\{1,2,3,4\}\) (pour \(v\ge0\)) n'est jamais multiple de 5, et \(b\) non plus par hypothèse, cette égalité est impossible.