Bonjour,

Dans un pays imaginaire, il n'y a que deux types de pièces de monnaie:

*) les pièces de 68 Unités
*) les pièces de 31 Unités.

Ainsi, certaines sommes peuvent être réglées pile-poil comme 130 U (1 pièce de 68 U et 2 pièces de 31 U). En revanche, d'autres sommes ne peuvent pas être réglées, comme un montant de 100 U. Plus précisément, on dira qu'une somme S peut être réglée si S peut s'écrire sous la forme <math>\(68x+31y\)</math> avec <math>\(x\)</math> et <math>\(y\)</math> entiers positifs ou nuls.



Deux questions :

1°) Montrer qu'à partir d'un certain montant p, on peut régler TOUS les montants supérieurs ou égaux à p.

2°) Calculer ce montant plancher p.

Pour pouvoir être résolu, je pense qu'il faut connaître de l'arithmétique de terminale.

On a pas le droit de retrancher des termes ? Par exemple, on peut avoir 100 avec 1100 Unités 31 et 500 unités 68 (1100 *31 - 500*68 = 100).

Citation : robocop

On a pas le droit de retrancher des termes ?

Non

Citation : robocop

Par exemple, on peut avoir 100 avec 1100 Unités 31 et 500 unités 68 (1100 *31 - 500*68 = 100).

Non, ça ne correspond à rien dans la réalité, tu vois bien qu'on ne peut pas régler 100 U avec ce type de monnaie. D'ailleurs, en soustrayant, on pourrait atteindre n'importe quel montant.

Non à mon avis le but de jeu c'est que la personne en face ne puisse pas te rendre de monnaie, sinon l'exercice n'a plus d'intérêt.

Edit : Grillé

Je suis d'accord, mais je pense que ça aurait du être précisé pour lever toute ambiguïté :p.

Sinon l'exercice est amusant, je vais essayer de me motiver à le chercher.

Citation : robocop

je pense que ça aurait du être précisé pour lever toute ambiguïté :p.

OK, je vais compléter l'énoncé.

Pour le premier point, il suffit de le faire par récurrence. L'ennui, c'est que pour le faire, faut avoir une intuition du premier n xD

Je m'exprime : Fait le même, mais avec des pièces de 3 et 5 euros. A partir de 8 euros, c'est faisables. Pourquoi ?

Cas de base : 8 = 1 * 3 + 1 * 5. C'est réglé.
Cas général : tu sais que ça marche pour tous les n jusque k, on regarde pour k + 1

k + 1 = x * 3 + y * 5 + 1 (par hyp de rec, on sait que k se décompose en x * 3 + y * 5).
k + 1 = x * 3 + y * 5 + 1 + 5 - 5 (artifice de calcul)
k + 1 = x * 3 + y * 5 + 2 * 3 - 1 * 5 (on dévelope un peu que tu vois un peu mieux le cheminement)
k + 1 = (x + 2) * 3 + (y - 1) * 5

ATTENTION ! Si y = 0, ça foire, car ça veut dire qu'on doit donner -1 billet, c'est pas possible. Faut faire un cas à part.
En effet, si y = 0, tu as que k, à la base, se décompose uniquement en billet de 3. C'est à dire, k = x * 3.
k + 1 = x * 3 + 1
k + 1 = x * 3 - 3 * 3 + 2 * 5 (artifice de calcul, car +1 = -9+10)
k + 1 = (x - 3) * 3 + 2 * 5


TADA !
Au final, tu sais qu'il faut que x >= 3 et y >= 0 pour qu'il n'y ai aucun soucis, c'est à dire si on te demande au moins une valeurs de 9. Il se fait qu'ici, c'es 8, car 8 C'est tout bêtement 1 * 5 + 1 * 3. Donc ça marche, et ton cas de base est est un cran plus petit.

k + 1 est donc décomposable en piece de 3 et 5.
Si par exemple tu sais que 9 c'est décomposable en 3 pièces de 3, tu obtiens que 10 est décomposable en 0 pièces de 3 et 2 pièces de 5 (cas où y = 0).
Pour 11, tu rajoute 2 pièces de 3 et retire une de 5, ça te fait 2 * 3 + 5 = 11. Génial hein ?


Tu devras donc pour toi faire le même raisonnement.

Donc tu as que k = x * 68 + y * 31

Comment passer a k + 1 ?

Comment écrire + 1 avec des 68 et des 31 ?
Ecrit leurs tables :
68 136 204 272 340
31 62 ... 248 279 341 !!!

YOUPI ! Tu as donc que 1 = 11 * 31 - 5 * 68
Donc k + 1 = x * 68 + y * 31 + 11 * 31 - 5 * 68
k + 1 = (x - 5) * 68 + (y + 11) * 31
ATTENTION ! Si x = 4, ça foire ! Dans le sens où ta pas assez de billet de 68 ! On va faire un "change".
On va calculer le PPCM(68,31) = 68 * 31 / pgcd(68,31) = 68 * 31 / 1 = 2108
Nombre de piece de 68 pour faire 2108 = 31
Nombre de piece de 31 pour faire 2108 = 68
On va retirer donc 68 pieces de 31, pour y mettre à la place 31 pièces de 68, on a donc que
Ca veut dire que k = 35 * 68 + (y - 68) * 31
Et l'algo reprend avec la formule précedente !

Donc, a partir de combien ça marche maintenant .. Faut au moins la valeur de 5 * 68, non ? Car si on a moins, on saura pas appliqué la formule trouvée dans le cas general, ni utilisée le "change" vu qu'on aura pas la somme suffisante non plus en piece de 31. 5 * 68 = 340. Une fois le change fait, t'auras 7 tours gagné (t'auras 35 billets de 68, et 5 qui partent par nombre + 1, donc tu pourras allez jusque nombre + 6 avant de devoir faire le change). A chaque tour, tu gagne +11 à y, donc tu auras 77, avant de retirer 68 pieces pour le change .. Donc, ça a l'air d'aller !

340, ça a l'air de marcher ! Mais rien de très formel, et je suis pas sur de mon coup ! Mais au moins, j'espère que ça t'aidera !

Expérimentalement la réponse semble être 2010 (25*68+10*31) mais je n'ai aucune idée de comment le prouver

Citation : Biiiinoit

Expérimentalement la réponse semble être 2010 (25*68+10*31) mais je n'ai aucune idée de comment le prouver

La première question posée est assez facile. Ensuite, il suffit d'écrire un petit programme dans le langage de ton choix (après tout, on est sur le sdz !!) ce qui te permet d'en déduire à coup sûr le montant demandé, qui est effectivement 2010. Maintenant, trouver dans le cas général le montant plancher et le démontrer n'est pas très facile même si ça ne demande pas de connaître beaucoup de choses (Bézout suffit).

Ci-dessous, un programme qui teste les montants que l'on peut régler entre 0 Unité jusqu'à 100000 Unités :

# -*- coding: utf-8 -*-
a=68
b=31

maxi=10**5
t=[0]*(maxi+1)
for x in range(maxi//a):
    for y in range(maxi//b):
        s=x*a+y*b
        if s<=maxi and t[s]==0:
            t[s]=1
print max([i for i in range(maxi+1) if t[i]==0])+1

Houlà, je ne comprends pas trop ce que tu me dis.

Pour démontrer que à partir de 2010 il est possible de décomposer toutes les sommes en pièces de 31€ et 68€ j'avais pensé utiliser la technique de blacktiger.jona en remarquant que pour rajouter un à une somme il suffit soit de rajouter 11 pièces de 31€ et de supprimer 5 pièces de 68€ (opération A) soit de rajouter 26 pièces de 68€ et de supprimer 57 pièces de 31€ (opération B).

On peut remarquer que pour passer d'une somme du type 68x+31y à 68(x+1)+31y en passant par tous les nombres intermédiaires il suffit de faire 5 fois (5 opérations A et une opération B) puis 6 opérations A puis une opération B puis 4 fois (5 opérations A et une opération B) puis 6 opérations A puis enfin une opération B.

Les conditions pour effectuer cet algorithme étant justement x>=25 et y>=10 ce qui est justement le cas pour 25*68+10*31 = 2010.

En initialisant la récurrence à 2010 on peut montrer par récurrence en passant par 68 nombres à chaque itération que tous les nombres supérieurs à 2010 sont décomposables en une somme de pièces de 68€ et de 31€.

Maintenant ma démonstration est quand même assez compliquée à comprendre puis il est très difficile de l'intuiter et pour la généraliser pour deux pièces de a€ et b€ avec a et b premiers entre eux ce n'est même pas la peine .

Voilà j'attends de voir si certains y arrivent mieux

PS Très beau programme en Python, très concis !

Citation : candide

Ci-dessous, un programme qui teste les montants que l'on peut régler entre 0 Unité jusqu'à 100000 Unités :

On peut montrer qu'il est inutile d'aller au delà de 2107, ce qui permet de répondre à la première question sans se lancer dans une récurrence. Bon c'est un peu long par contre.

<math>\(\text{Soit } p \in \mathbb{N}\)</math>
<math>\(\text{Soit } (E) : 68x+31y=p\)</math>

<math>\(\text{On applique l'algorithme d'Euclide a 68 et 31}\)</math>
<math>\(68=31\times2+6\)</math>
<math>\(31=6\times5+1\)</math>

<math>\(\text{On "remonte" l'algorithme pour obtenir une solution particuliere de (E)}\)</math>
<math>\(1=31-6\times5\)</math>
<math>\(1=31-(68-31\times2)\times5\)</math>
<math>\(1=(-5)\times68+11\times31\)</math>
<math>\(p=(-5p)\times68+11p\times31\)</math>

<math>\(\text{Resolvons (E)}\)</math>
<math>\(\begin{align} 68x+31y=p&\Leftrightarrow 68x+31y=68\times(-5p)+31\times11p \\ & \Leftrightarrow 68(x+5p)=31(11p-5) \\ & \Leftrightarrow \begin{cases}68(x+5p)=31(11p-5) \\ \exists k \in \mathbb{Z} \diagup 11p - y = 68k \text{ (Theoreme de Gauss)} \end{cases} \\ & \Leftrightarrow \exists k \in \mathbb{Z} \diagup \begin{cases}x+5p=31k \\ 11p - y = 68k \end{cases} \\ & \Leftrightarrow \exists k \in \mathbb{Z} \diagup \begin{cases}x=31k-5p \\ y = 11p - 68k \end{cases} \end{align}\)</math>

<math>\(\text{L'ensemble des solutions (x,y) de (E) est :}\)</math>
<math>\(\mathcal{S}=\{ (31k-5p,11p-68k), k \in \mathbb{Z} \}\)</math>


<math>\(\text{Supposons que p ne puisse pas etre reglee}\)</math>
<math>\(\text{Alors } \forall (x,y) \in \mathcal{S}, x<0 \text{ ou } y<0\)</math>
<math>\(\text{i.e. } \forall k \in \mathbb{Z}, 31k-5p<0 \text{ ou } 11p-68k<0\)</math>
<math>\(\text{Donc } \forall k \in \mathbb{Z}, k<\frac{5p}{31} \text{ ou } k>\frac{11p}{68}\)</math>


<math>\(\text{Si par l'absurde on avait } E(\frac{5p}{31})\neq E(\frac{11p}{68}) \text{ , E est la fonction partie entiere}\)</math>
<math>\(\text{Alors } E(\frac{5p}{31})<\frac{5p}{31}<\frac{11p}{68}<E(\frac{11p}{68}) + 1\)</math>
<math>\(\text{S'agissant d'entiers, } E(\frac{5p}{31})<E(\frac{11p}{68}) + 1 \text{ donne } E(\frac{5p}{31})\leqslant E(\frac{11p}{68})\)</math>
<math>\(\text{Or, par hypothese } E(\frac{5p}{31})\neq E(\frac{11p}{68}) \text{, donc } E(\frac{5p}{31})< E(\frac{11p}{68})\)</math>
<math>\(\text{Et comme il s'agit encore d'entiers, } E(\frac{5p}{31})+1 \leqslant E(\frac{11p}{68})\)</math>
<math>\(\text{On a alors l'entier } E(\frac{11p}{68}) \text{ qui verifie } \frac{5p}{31}<E(\frac{5p}{31})+1 \leqslant E(\frac{11p}{68})<\frac{11p}{68}\text{, }\)</math>
<math>\(\text{ce qui est en contradiction avec le resultat precedent.}\)</math>


<math>\(\text{Donc } E(\frac{5p}{31}) = E(\frac{11p}{68}) = A\)</math>
<math>\(A\leqslant\frac{5p}{31}<A+1\)</math>
<math>\(A\leqslant\frac{11p}{68}<A+1\)</math>
<math>\(\begin{align}\text{On en deduit } -1<\frac{11p}{68}-\frac{5p}{31} &< 1 \\ \frac{p}{2108} &< 1 \\ p &< 2108 \end{align}\)</math>


Voilà, je n'ai pas réussi à affiner plus le résultat pour tomber sur la valeur 2010, si quelqu'un a une solution autre que la méthode exhaustive, ça m'intéresse.

Citation : robocop

Je suis d'accord, mais je pense que ça aurait du être précisé pour lever toute ambiguïté :p.

Sinon l'exercice est amusant, je vais essayer de me motiver à le chercher.

Heu en fait c'était précisé sous cette forme :

Citation

Plus précisément, on dira qu'une somme S peut être réglée si S peut s'écrire sous la forme 68x+31y avec x et y entiers positifs ou nuls.

Puisqu'il faut que x et y soit positifs.

Je planche sur le problème depuis quelques 10ène de minutes. Je n'avançais pas donc je suis parti avec d'autres paires de nombres. J'ai remarquer des trucs marrant, se n'est pas expliqué très mathématiquement et je ne sais pas si ça a un intérêt :

-Avec 2U et 3U

S=2x+3y 1=impossible 2=2*1+3*0 3=2*0+3*1 4=2*2+3*0 5=2*1+3*1 6=2*3+3*0 7=2*2+3*1

Pour les valeur de x, elles suivent une logique on enchaine -1; +2; -1; +2; -1 ... Pour les y 0; 1; 0; 1 ... Ça semble toujours fonctionner.

-Avec 3U et 4U

S=3x+4y 5= impossible 6=3*2+4*0 7=3*1+4*1 8=3*0+4*2 9=3*3+4*0 10=3*2+4*1 11=3*1+4*2 12=3*4+4*0 13=3*3+4*1 14=3*2+4*2 15=3*5+4*0

Pour les valeurs de x, on a encore une "suite" : -1 -1 +3 De même pour les y : 0 1 2 0 1 2 0...

-Pour 3U et 8U

S=3x+8y 9=3*3+8*0 10= impossible 11=3*1+8*1 12=3*4+8*0 13= impossible 14=3*2+8*1 15=3*5+8*0 16=3*0+8*2 17=3*3+8*1 18=3*6+8*0 19=3*1+8*2 20=3*4+8*1 21=3*7+8*0 22=3*2+8*2

Pour les x : -5 +3 +3 ... Pour les y : 1 0 2 1 0 2 . . .

Le plus marrant !(on se fend la poire en maths, c'est dingue)
Ok alors après, je me suis pencher sur les valeurs impossible a obtenir avec notre consigne, et je leur ai appliquer les suites de chiffres que j'avais reperé.

-Pour 3U et 8U

S=3x+8y 7=3*(-3)+8*2 8=3*0+8*1 9=3*3+8*0 10= 3*(-2)+8*2 11=3*1+8*1 12=3*4+8*0 13= 3*(-1)+8*2 14=3*2+8*1 15=3*5+8*0

Si on autorise les nombres négatifs, les suites trouvé marche pour l'ensemble des chiffres apparemment (simple conjecture). Dans notre exercice, les valeurs de S pour lesquels il n'y a pas de solution se remarque par le fait que les composantes "x" ou "y" soit négatives.

Les questions qui me restent a l'esprit sont :
-Comment trouver les "suites" qui correspondent au paires de chiffres utiliser pour la monnaie
-Comment résoudre le problème que je n'ai fait que contourner jusque là

Citation : yonk

Heu en fait c'était précisé sous cette forme :

Citation

Plus précisément, on dira qu'une somme S peut être réglée si S peut s'écrire sous la forme 68x+31y avec x et y entiers positifs ou nuls.

J'ai justement rajouté ce passage suite à la remarque de robocop

Citation : yonk

Les questions qui me restent a l'esprit sont :
-Comment trouver les "suites" qui correspondent au paires de chiffres utiliser pour la monnaie
-Comment résoudre le problème que je n'ai fait que contourner jusque là

Il te faut Bézout. Montrer que toutes les sommes assez grandes peuvent être réglées est assez facile si on a fait de l'arithmétique niveau bac. Trouver la plus petite valeur est plus délicat mais ça peut se faire en quelques lignes. Par ailleurs, il n'est pas impossible que vos méthodes un peu artisanales avec les tableaux puissent donner une preuve mais moi je trouve assez dur de trouver comme ça, faut avoir beaucoup d'intuition et parfois le formalisme supplée le manque d'imagination

Citation : Damneth

Voilà, je n'ai pas réussi à affiner plus le résultat pour tomber sur la valeur 2010, si quelqu'un a une solution autre que la méthode exhaustive, ça m'intéresse.

Je pense avoir réussi, par contre c'est quand même assez long :

En repartant de la démonstration de Damneth on montre que si p ne peut pas être réglé cela signifie que :

<math>\(\forall k \in \mathbb{Z}\)</math>, on a <math>\(k<\frac{5p}{31}\)</math> ou <math>\(k>\frac{11p}{68}\)</math>

Il existe donc un unique <math>\(A_p = E(\frac{5p}{31})\)</math> pour lequel on a :
<math>\(A_p<\frac{5p}{31}\)</math> et <math>\(A_p+1>\frac{5p}{31}\)</math> ce qui n’est possible que si <math>\(A_p+1>\frac{11p}{68}\)</math>

De plus, on sait que <math>\(\frac{5p}{31}<\frac{11p}{68}\)</math> on a donc :
<math>\(A_p<\frac{5p}{31}<\frac{11p}{68}<A_p+1\)</math>

On remarque que cette proposition est bien équivalente à la proposition précédente vu que <math>\(\forall k \in \mathbb{Z}\)</math> on a soit <math>\(k\leq A_p\)</math> soit <math>\(k\geq A_p+1\)</math>

Soit <math>\(l_p = \frac{11p}{68}-\frac{5p}{68}=\frac{p}{2108}\)</math>

L’inéquation précédente se réécrit
<math>\(A_p<\frac{5p}{31}<\frac{5p}{31}+l_p<A_p+1\)</math>
<math>\(\Leftrightarrow A_p<\frac{5p}{31}\)</math> et <math>\(\frac{5p}{31}<A_p+1-l_p\)</math>
<math>\(\Leftrightarrow A_p<\frac{5p}{31}<A_p+1-l_p\)</math>
<math>\(\Leftrightarrow 0<\frac{5p}{31}-A_p<1-l_p\)</math>

On cherche le plus grand p pour lequel cette inégalité est vérifiée. On peut remarquer que l’expression <math>\(\frac{5p}{31}-A_p\)</math> ne dépend que de p%31.

On peut légitimement supposer que le modulo 31 du plus grand p vérifiant cette inégalité sera tel que <math>\(\frac{5p}{31}-A_p\)</math> sera minimum tout en étant strictement positif. En écrivant le tableau des 31 valeurs de <math>\(\frac{5p}{31}-A_p\)</math> en fonction de p%31 on remarque que
<math>\(\forall p \in \mathbb{N}\)</math><math>\(\frac{5p}{31}-A_p \geq \frac{1}{31}\)</math> ou <math>\(\frac{5p}{31}-A_p=0\)</math>
et que pour p%31=25 on a <math>\(\frac{5p}{31}-A_p=\frac{1}{31}\)</math>

On cherche donc p_max le plus grand p tel que p%31=25 et <math>\(0<\frac{5p}{31}-A_p<1-l_p\)</math>. Ceci se réécrit :
<math>\(\frac{1}{31}<1-\frac{p}{2108}\)</math>
<math>\(\Leftrightarrow \frac{p}{2108}<\frac{30}{31}\)</math>
<math>\(\Leftrightarrow p<2040\)</math>

On cherche donc le plus grand p tel que p%31=25 et p<2040 et on trouve 2009.

Supposons maintenant par l’absurde qu’il existe p>2009 tel que p%31 <math>\(\neq\)</math> 25 et
<math>\(0<\frac{5p}{31}-A_p<1-l_p\)</math>.
On a alors nécessairement <math>\(\frac{5p}{31}-A_p>\frac{1}{31}\)</math> et, vu que la plus petite valeur de <math>\(\frac{5p}{31}-A_p\)</math> supérieure à <math>\(\frac{1}{31}\)</math> est <math>\(\frac{2}{31}\)</math> on a :
<math>\(\frac{5p}{31}-A_p \geq \frac{2}{31}\)</math>

On a alors <math>\(\frac{2}{31} \leq \frac{5p}{31}-A_p < 1-\frac{p}{2108}\)</math> ce qui implique <math>\(\frac{2}{31}<1-\frac{p}{2108} \Leftrightarrow p<1972\)</math> ce qui est en contradiction avec p>2009.

Le plus grand p qui n’est pas réglable est donc 2009. Tout les nombres supérieurs ou égal à 2010 sont donc réglables. CQFD !

Citation : Damneth

<math>\(\text{L'ensemble des solutions (x,y) de (E) est :}\)</math>
<math>\(\mathcal{S}=\{ (31k-5p,11p-68k), k \in \mathbb{Z} \}\)</math>

Oui, tout à fait. La suite de ta solution est inutilement compliquée, on peut conclure en trois lignes en remarquant que pour qu'entre deux réels z1 et z2 tu aies un entier, il suffit que l'écart entre z1 et z2 vaille au moins 1.

Citation : Biiiinoit

Le plus grand p qui n’est pas réglable est donc 2009. Tout les nombres supérieurs ou égal à 2010 sont donc réglables. CQFD !

Ta solution me semble compliquée mais c'est bien la réponse attendue. Je t'invite à essayer de raisonner de la manière suivante : si M est la plus grande somme qu'on ne puisse pas régler, alors M+a et M+b peuvent être réglées, ce qui permet assez facilement de trouver M.


J'ai rédigé une solution basée sur une autre idée : le fichier pdf ICI

Citation : candide

J'ai rédigé une solution basée sur une autre idée : le fichier pdf ICI

Eh bien merci de ta réponse courte et efficace ! Qui plus est, le résultat de ta démonstration dans le cas général est amusant et vaut le coup d'être retenu.

Bien que moins concise, la solution de Biiiinoit est intéressante également, merci d'avoir continué sur ma lancée

Citation : Damneth

Qui plus est, le résultat de ta démonstration dans le cas général est amusant et vaut le coup d'être retenu.

Je ne sais pas si ça vaut la peine d'être retenu mais c'est un problème qui a été très étudié. Comme on vient de le voir, le cas de deux pièces est assez facile et connu depuis la fin du 19ème siècle mais le cas de n pièces, avec n>2 est beaucoup plus compliqué et reste d'ailleurs non résolu à l'heure actuelle (trouver explicitement le montant maximal non réglable). Pour ceux qui veulent avoir des infos, ce problème est référencé sous différents appellations :

*) le problème de Frobenius
*) The Postage Stamp Problem
*) The Money Changing Problem

La plus grande somme que l'on ne peut pas régler s'appelle souvent le nombre de Frobenius.