Bonsoir,
sans trop de réflexion, une piste.

 Cliquez pour afficher

On paye avec au minimum    pièces si n est multiple de 3 ou    pièces sinon.

Ensuite on remplace les pièces de 3 par 2+1 ou 1+1+1.

Il reste à compter.

pour la formule finale, disons F(n), on pourra utiliser la fonction (a mod k) qui renvoie la reste de la division de a par k

si elle n'apparait pas, je donnerai ma méthode dans ... disons une semaine .

Bonjour,
Merci matheuxmatou d'animer et de nous laisser un peu de temps

ben oui quand même, parce que la formule finale, elle est velue

la méthode est sympa aussi (enfin la mienne... elle m'avait tellement étonné à l'époque que je m'en souviens encore... c'est dire !)

salut

si note le nombre de façons de payer n écus (francs, euro, ...) alors :

 Cliquez pour afficher

et on  reconnait une suite récurrente linéaire d'ordre 3 qu'on sait résoudre ...

on pose et q est solution de l'équation

mais pénible ... s'il n'y a pas de racine entière ...

Salut carpediem.

 Cliquez pour afficher

Il est facile de calculer u₄
4=1+1+1+1
4=1+1+2
4=2+2
4=1+3
donc u₄=43+22+31

ahrg !! merci verdurin

Bonjour,

je ne sais pas si c'est la même méthode que celle de matheuxmatou mais il existe une formule de récurrence vraiment très simple qui exprime en fonction de et de n.

jandri

certes, on peut établir une formule de récurrence... mais le problème est la formule explicite

pour info : non, ce n'est pas ma méthode.

histoire que vous puissiez vérifier vos valeurs, voici un tableau des 20 premiers termes :

Une formule de récurrence générale pour le nombre façon de payer n écus avec des écus de valeur 1 à m est :

 Cliquez pour afficher

Ça se calcule facilement à l'aide d'un tableau et nous permet de "deviner" des formules:







Ça se complique pour m = 3:



On repère un pattern de longueur 6 dans les différences:



On peut en déduire une formule:

Attention :

 Cliquez pour afficher

On peut rentrer ces données dans le site de l'OEIS...
Pas besoin d'aller aussi loin.
Je l'ai fait depuis un moment, mais ne voulais pas casser l'ambiance

oops:

 Cliquez pour afficher

dans les conditions

LittleFox

merci de blanker afin que les autres puissent explorer d'autres pistes...

 Cliquez pour afficher

et alors finalement c'est quoi F(n) ? (je ne comprends rien à ton "r" ...)

Ma réponse de 11h12 concernait le message de matheuxmatou.

@LittleFox,
Pourquoi ne blankes-tu pas tes réponses ?

LittleFox

 Cliquez pour afficher

seul F(n) = u(3,n) nous intéresse ici

bien que "alambiqué" et pas sous une seule formule explicite, ton résultat final semble fonctionner sur les 20 premières valeurs.

cela dit, il y a beaucoup de remarques et d'intuitions ... mais je ne vois pas de démonstration rigoureuse des résultats

Je suis d'accord avec ce qu'a trouvé LittleFox

On peut simplifier la formule finale (nombre de façons de payer n avec 1, 2 et 3) :

 Cliquez pour afficher

C'est l'entier le plus proche de

La démonstration par récurrence est immédiate avec la formule de récurrence dont j'ai parlé :

 Cliquez pour afficher

jandri

 Cliquez pour afficher

à préciser lorsque ce nombre est du type k+1/2

et toujours pas de démonstration... ?

matheuxmatou

 Cliquez pour afficher

Le nombre n'est jamais du type k+1/2.

Comme je l'ai dit, la démonstration par récurrence est immédiate (on vérifie la formule pour ).

Je n'ai pas donné la démonstration de la relation de récurrence donnant en fonction de mais ce n'est pas bien compliqué en utilisant :

 Cliquez pour afficher

jandri

 Cliquez pour afficher

la formule finale est jolie et je viens de la vérifier avec mon résultat, surtout que on ne tombe jamais sur un k + 1/2 ...

mais bon, je bien croire que c'est "élémentaire"... mais c'est assez tarte quand même à rédiger proprement d'un bout à l'autre

1 : la formule de récurrence (je ne vois pas bien où intervient cette indication)
2 : la forme finale (6 pas de récurrences...)

...

@Sylvieg
Désolé pour les blank
C'est plus simple quand on prévisualise plein de fois avant de poster mais j'ai oublié de le mettre à la fin.

@matheuxmatou

 Cliquez pour afficher

J'avais oublié de remplacer mon dans ma formule. Comme indiqué à 11:12 :

 Cliquez pour afficher

En posant , le reste de la division de n par 6:



Et donc



(r-3)^2 est maximal quand et on peut donc s'en servir pour inclure le cas :

LittleFox

 Cliquez pour afficher

ah elle est pas mal non plus cette dernière formule...

plus épurée que la mienne...

mais bon... toujours pas de démo rigoureuse d'un bout à l'autre

On ne demandait pas une démonstration mais en voici une:

 Cliquez pour afficher

La formule de récurence générale est correcte :
Le cas exprime simplement que pour payer n écus avec des écus de valeur 1 à m, soit on utilise pas de pièce de valeur m, soit on en utilise. Le nombre de façon étant la somme du nombre de façon de ces deux cas.
Les autres cas (cas de base) ont ces valeurs par définition.

Les formule pour sont correctes par définition.

La formule de est correcte par définition.

La formule de est correcte pour . En effet,

La formule de est correcte pour . En effet,

La formule de est correcte pour . En effet, . Or .

La formule de est correcte pour . En effet, . Or .

La formule de est correcte pour . En effet, .

La formule de est correcte pour . En effet, . Or .

La formule de est correcte pour . En effet, . Or .

La formule de est correcte pour . En effet, . Or .

La formule de est correcte pour . En effet,
La dernière égalité est vraie car le reste de la division de par 12 est au plus 7 et donc ajouter 3 avant la division entière par 12 ne change rien.

C'était pas très compliqué, juste long à écrire.

Petite note:

 Cliquez pour afficher

Toutes les formules de la forme avec fonctionnent.

En particulier, celle de jandri est avec .

Bonjour,
Je ne comprends pas la 1ère formule de LittleFox.

 Cliquez pour afficher

u(m,n) = u(m-1,n) + u(m,n-m)
Elle donnerait u(3,5) = 2+2 ou encore u(3,7) = 3+4.
Ce qui est faux.

 Cliquez pour afficher

pour payer n écus avec des écus de valeur 1 à m, soit on n'utilise pas de pièce de valeur m, soit on en utilise au moins une.
J'y ai rajouté le "au moins une".
Mais il ne faut pas singulariser cette "au moins une".

Bon, mes contre exemples ne marchent pas

Oubliez mon message de 14h42.

LittleFox

 Cliquez pour afficher

ah ben voilà, cela commence à prendre de la valeur

il fallait quand même "voir" la formule pour la démontrer par récurrence... mais le résultat final est élégant.

Ce n'est pas ma méthode.... la mienne, bien que calculatoire aussi, permet d'avoir le résultat sans avoir à l'intuiter...

 Cliquez pour afficher

une fois établie ta relation de récurrence, le passage de n-3 à n+3 se fait effectivement sans trop de problème... mais bon faut quand même l'écrire

par contre j'aimerais le détail de la formule de récurrence

et il faut "intuiter" la formule... comme pour LittleFox...

cela dit ton résultat est également très élégant !

Une tentative d'explication :

 Cliquez pour afficher

u(m,n) est le nombre de façon de payer n écus avec des pièces de valeur 1,2,3,...,m.

Pour payer n écus avec des pièces de de valeur 1,2,3,...,m je peux:
Soit payer sans aucune pièce de valeur m. Il y a u(m-1, n) façons de le faire.
Ou bien payer avec au moins une pièce de valeur m. L'ordre n'ayant pas d'importance on peut commencer par retirer cette pièce de valeur m, le nombre de façon de payer avec au moins une pièce de valuer m est égal au nombre de façon de payer n-m écus avec des pièces de valeur 1,2,3,...,m : u(m,n-m).

Au total, u(m,n) = u(m-1,n) + u(m,n-m).

Voici un tableau de u(m,n) pour les premières valeur de m et n :


J'ai ajouté quelques flêches pour montrer les termes de la somme.
Il faut prendre la valeur juste au dessus: u(m-1,n), plus la valeur m cases à gauche u(m,n-m).

On a u(3,5) = u(2,5) + u(3,2) = 3 + 2 = 5 et u(3,7) = u(2,7) + u (3,4) = 4+4 = 8.

@matheuxmatou
Je commence à me vexer. J'ai une réponse propre et concise avec une démonstration défendable. Et pour toi, ça commence seulement à prendre de la valeur?
J'ai passé beaucoup trop de temps dessus au lieu de travailler aujourd'hui d'ailleurs

Sans intuition, on n'arrive à rien.
J'aimerais bien voir ta démonstration rigoureuse sans intuition

Merci LittleFox pour ton explication de 15h23.
Je croyais bien avoir finalement compris le raisonnement. Mais maintenant j'en suis certaine

matheuxmatou

La formule de récurrence est simple à démontrer :

 Cliquez pour afficher

On montre d'abord que le nombre de solution dans pour est égal à (nombre de choix pour ).

Ensuite, pour l'équation , il y a :
solutions avec ,
puis solutions avec
et enfin solutions avec (on pose ).

Donc

LittleFox

je n'ai pas du tout critiquer ta démonstration... elle est même assez complète et convaincante... c'était juste un doux euphémisme en forme de clin d'œil !

pardon si tu l'as prise au pied de la lettre...

et c'est vrai que sur ce genre de problème c'est souvent comme ça qu'on procède : on regarde, on imagine, puis on démontre.

en plus ta formule final est très concise, plus que la mienne avant amélioration.

jandri

ah oui, j'avoue... je ne la voyais pas aussi simple... donc bravo... et ta formule finale est sympa aussi... disons que LittleFox la convertit en une formule utilisant une fonction plus classique (la partie entière) que l'approximation à l'entier le plus proche... où il faut voir que (n+3)²/12 ne sera jamais de la forme k+1/2 afin de lever toute ambiguïté.

donc à jandri et LittleFox pour leur approche et leur résultat.

Oui, bravo à eux deux
Mais saurons-nous avant une semaine quelle était ta solution, matheuxmatou ?

oui, maintenant je vais vous donner l'idée :

 Cliquez pour afficher

en fait cette question venait en fin d'un DM de math spé sur les séries entières et décompositions en éléments simple.

ce qui m'avait cloué était de voir un tel résultat apparaître à un endroit où on ne l'attendait pas.

au final, la démonstration est plus longue que celle proposée par jandri, de loin la plus courte, mais a l'avantage de ne pas avoir besoin d'intuiter une formule.

le problème consistait à décomposer en éléments simples, puis en série entière



dans on obtient (c'est relativement rapide en fait)



ensuite la décomposition en série entière de chaque morceau se fait assez bien puisque chacun est du type (1-u)^a

on obtient comme coefficient de xⁿ :



mais comme



le coefficient de xⁿ est le nombre cherché F(n)

d'où F(n) = a_n

ensuite, suivant les cas, l'expression s'arrange bien... pour retomber sur les résultats de LittleFox ou jandri

si ça peut donner une idée de devoir pour les enseignants en prépas ...

La méthode de matheuxmatou est la méthode que l'on utilise classiquement pour ce type de dénombrement.

Son inconvénient est qu'elle utilise une décomposition en éléments simples qui donne en général des calculs !

à l'époque, en prépa on mangeait pas mal de calcul... et y'avait pas les logiciels ou calculettes !

et si ma mémoire est bonne, je crois même que c'était avec des pièces de 1, 2 et 5 francs...

les amateurs pourront essayer et là ce sont les racines 5-ième de l'unité qui interviennent..

Pour des pièces de 1, 2 et 5 la méthode que j'ai proposée pour des pièces de 1, 2 et 3 marche également très bien.

Formule de récurrence :

 Cliquez pour afficher

 Cliquez pour afficher

est l'entier le plus proche de

oui, elle se généralise bien ta méthode jandri

elle me plait bien d'ailleurs !

celle que j'avais retenue n'était en fait qu'un "en déduire" à la fin d'un exo.

Bonsoir,
Ce que je trouve étonnant, c'est la variété dans la forme du résultat final quand il est concis !
Les unes avec "entier le plus proche" ou partie entière, peu différentes.
L'autre avec du (-1)ⁿ et cos(2n/3).

J'en propose une autre un peu moins concise :

Si n est un multiple de 6,
Sinon où désigne la partie entière de .

Pour les trouver, pas besoin de "intuiter"
Il suffit d'utiliser F(n) = F(n-6) + n après avoir calculé les valeurs de F(n) pour n de 0 à 5.

J'aime bien aussi le colimaçon dans le site de l'OEIS que j'avais consulté dès le 8 avril :