Répondre

Zorglub · 23-02-2015 23:27:14

Je suis tombé sur ce problème, et avoue ne pas avoir lu en détail tous les échanges.
Le dernier message suggère qu'on n'a pas donné de solution générale. En voici une.
Un premier résultat :

———————
Lemme: Soit [tex]n > 0[/tex] et [tex]a \geq 0[/tex] des entiers tels que [tex]a(a+1) / 2 \leq n[/tex]
Pour toute paire d’entiers [tex]u \geq 0[/tex] et [tex]v \geq 0[/tex] avec [tex]u+v = a(a+1)/2[/tex],
il y a façon à partir de [tex][3n ; 0 ; 0][/tex] d’arriver à [tex][3n-u-v; u; v][/tex]
en exactement [tex]a[/tex] étapes.

La démonstration se fait par induction sur [tex]a[/tex].
———————

Montrons maintenant comment partir de [tex][3n; 0 ; 0 ][/tex] et d’arriver à [tex][n; n ;n][/tex] en exactement [tex]n[/tex] étapes, lorsque [tex]n \geq 12[/tex].
Note : on a besoin des conséquences suivantes dans la preuve, les cas avec [tex]n[/tex] inférieur à [tex]12[/tex] peuvent se faire à la main.

Soit [tex]n \geq 12[/tex], posons
[tex]a[/tex] le plus grand entier tel que [tex]a(a+1) / 2 \leq n[/tex]
[tex]b := n - a(a+1) /2[/tex] et donc [tex]0 \leq b \leq a[/tex]
[tex]c := n - a - 2b[/tex]

Puisque [tex]n \geq 12[/tex] on a alors
[tex]a \geq 4[/tex]
[tex]n \geq 3a[/tex]
[tex]c \geq 1[/tex]

Brisons la démarche en deux cas disjoints.

SI [tex]c[/tex] EST IMPAIR:
{
alors [tex]u := n-b-(c-1)/2[/tex] et[tex] v := (c-1)/2[/tex] sont des entiers positifs (découle du fait que [tex]n \geq 12[/tex])

Le lemme assure qu’on peut passer de [tex][3n; 0; 0][/tex] à [tex] [2n+b ; u ; v ][/tex] en [tex]a[/tex] étapes

En alternant des transferts entre les 2 premiers récipients on arrive en [tex]2b[/tex] étapes
supplémentaires à [tex][ 2n ; n - v; v][/tex].

En alternant des transferts entre les 2 derniers récipients on arrive en [tex] c-1 = 2v[/tex] étapes
supplémentaires à [tex] [ 2n ; n; 0][/tex]

À date on a un total de [tex]a+ 2b + c-1 = n-1[/tex] étapes de faites.
Un dernier transfert du premier au dernier récipient donne[tex] [n; n; n][/tex] comme désiré.
}

SI [tex]c \geq 2[/tex] EST PAIR:
{
alors [tex]u := n-a—b-c/2[/tex] et [tex]v := a+c/2[/tex] sont des entiers positifs (découle du fait que [tex]n \geq 12[/tex])

Le lemme assure qu’on peut passer de [tex][3n; 0; 0][/tex] à [tex][2n+b ; u ; v ][/tex] en [tex]a[/tex] étapes

Un transfert du premier au deuxième récipient donne [tex][2n+b; n-b-(c-2)/2; (c-2)/2][/tex].

En alternant des transferts entre les 2 premiers récipients on arrive en [tex]2b[/tex] étapes
supplémentaires à [tex][ 2n ; n-(c-2)/2; (c-2)/2][/tex].

En alternant des transferts entre les 2 derniers récipients on arrive en [tex]c-2[/tex] étapes
supplémentaires à [tex][ 2n ; n; 0][/tex]

À date on a un total de [tex]a+ 1+ 2b + c-2 = n-1[/tex] étapes de faites.
Un dernier transfert du premier au dernier récipient donne [tex] [n; n; n][/tex] comme désiré.
}

totomm · 11-09-2011 20:08:34

Bonsoir,

@jpp :
J'ai repris votre synthèse au post #144 (08/07/2011) pour les nombres de la forme p(p+1)/2.
Je vois bien les 2 exemples n=10 et n=15, mais cela ne me donne pas la méthode générale que j'appliquerais pour n=36 ou 78 (cas n et p pairs) ni pour n=45 ou 91 (cas n et p impairs)
Je n'ai pas non plus de méthode générale pour n et p de parités différentes.

Si la méthode est décrite précédemment, donnez-moi simplement les numéros des posts.

Je pense ne regarder le post #145 (avec q ou a) qu'après avoir bien testé les résultats du post #144.

Merci. Cordialement.
Note : Vous pouvez ouvrir une autre discussion si prolonger celle-ci pose des problèmes…

freddy · 08-08-2011 13:21:47

nerosson a écrit :

Salut à tous,
Te bile pas, mon bon Totomm, la critique était plutôt amicale, et elle avait surtout pour but d'injecter un peu fantaisie dans une discussion plutôt austère.
Et puis je crois que si je n'avais pas un peu chahuté une discussion inaugurée par freddy, ça l'aurait perturbé : il se serait dit : "il baisse, l'ancêtre, il commence à pencher du côté où il va tomber !"

Il penche déjà, non ?

Ton esprit sagace n'a même pas cherché à esquisser le début du commencement d'une critique constructive. Préviens Bernadette, ta moitié d'orange, qu'elle commence à chercher ton remplaçant pour ne pas avoir froid au lit, et dis lui de sortir Bernard de la commode du lavoir : depuis le temps, il doit être complètement desséché !
;-)

freddy · 08-08-2011 13:16:56

totomm a écrit :

Bonjour,
La solution mathématique, tout en étant incontestable, ne semble pas traiter les dépassements de B qui doit toujours rester dans l'intervalle [0, 3n] .
On peut certainement programmer un algorithme qui cherche une liste convenable, mais, en l'absence d'indications qui complèteraient cette solution mathématique, il lui faudrait itérer dans la génération de chacun des pas, sans même être certain qu'il existe une liste qui convienne pour tout n, sans débordement de B.
Mais je suis prêt à programmer s'il est démontrable, a priori, qu'une telle liste existe.
J'ai préféré présenter une solution par "suites récurrentes", car chacune de ces suites allant de m à n, leur algorithme de construction montre qu'aucun pas ne débordera de l'intervalle [0, 3n].

Salut,

je peux me tromper, j'ai l'impression que tu confonds mathématique et automatique.

On a montré qu'une solution existe pour tout n entier différent de 1,2 et 4.

Ensuite, si on veut la trouver via un logiciel de calcul, il faut bien entendu concevoir un pgm qui intègre les contraintes de résolutions auxquelles on se soumet "naturellement" quand on le fait avec un crayon et une gomme.

Dans le cas de n=13, j'ai tout simplement remplacé 11+3 par la somme ad hoc la plus proche : 9+5 puisque on ne peut se trouver avec une urne avec un nombre négatif de balle de golf, ce que ton pgm de recherche a fait.

nerosson · 07-08-2011 18:52:02

Salut à tous,

Te bile pas, mon bon Totomm, la critique était plutôt amicale, et elle avait surtout pour but d'injecter un peu fantaisie dans une discussion plutôt austère.

Et puis je crois que si je n'avais pas un peu chahuté une discussion inaugurée par freddy, ça l'aurait perturbé : il se serait dit : "il baisse, l'ancêtre, il commence à pencher du côté qu'il va tomber !"

totomm · 07-08-2011 17:39:03

Bonsoir,

Mais, cher ami nerosson, chacun sait dans ces communications ce que font les autres, et les airs qui sont joués sont tout à fait entendus malgré les apparences !

Cordialement.

nerosson · 07-08-2011 13:33:36

Salut à tous,

y ont pas bientôt fini de communiquer vos sacrés vases communicants ?

Ca me rappelle l'histoire de la bonne femme qui avait traîné son gosse de cinq ans à un récital de violoncelle :
le gosse : "Dis, maman, le monsieur, il a pas bientôt fini de scier sa petite armoire ?"

totomm · 07-08-2011 09:30:32

Bonjour,

La solution mathématique, tout en étant incontestable, ne semble pas traiter les dépassements de B qui doit toujours rester dans l'intervalle [0, 3n] .
On peut certainement programmer un algorithme qui cherche une liste convenable, mais, en l'absence d'indications qui complèteraient cette solution mathématique, il lui faudrait itérer dans la génération de chacun des pas, sans même être certain qu'il existe une liste qui convienne pour tout n, sans débordement de B.
Mais je suis prêt à programmer s'il est démontrable, à priori, qu'une telle liste existe.

J'ai préféré présenter une solution par "suites récurrentes", car chacune de ces suites allant de m à n, leur algorithme de construction montre qu'aucun pas ne débordera de l'intervalle [0, 3n].

@jpp : Votre solution est-elle suffisamment présentée globalement pour être testée "pour tout n" ?

Cordialement

freddy · 06-08-2011 22:12:36

totomm a écrit :

Bonsoir,
j'ai hier commencé une vérification systématique des posts #139 à 141
Après avoir été perturbé, j'ai rectifié et vérifié, mais je peux m'être encore trompé :
pour n=11 le nombre est 22 =10+ 9+ 3. B ne dépasse pas 3n=33 Méthode OK
pour n=12 le nombre est 27 =11+ 10+ 6. B ne dépasse pas 3n=36 Méthode OK
pour n=13 le nombre est 26 =12+ 11+ 3. B vaut 49 au pas 10 donc dépasse 3n=39. La Méthode est donc KO, même si en poursuivant B serait correct à 26 au pas 12.
pour n=18, le nombre est 58=16+15+14+13 qu'il faut remplacer par 16+14+13+11+4 et alors la méthode pour n=2[4] est OK : Comment choisir la bonne liste ??
(...)
A suivre.....

Salut,
pour n=13, il faut former 26=12+9+5 ... 3 termes, mais pas choisis n'importe comment.

Comment choisir la bonne liste ? Puisque la solution mathématique est incontestable, il faut le "dire" à l'ordinateur via un pgm adapté. C'est là où je trouve que l'ordinateur nous donne un très sérieux coup de main. Avec l'exemple de n=13, je pense que tu peux concevoir ce pgm de recherche de la bonne solution.

Sinon, excuses acceptées bien entendu, mais tu n'as pas besoin d'en faire, tout le monde peut se tromper, on le sait tous !

totomm · 06-08-2011 18:08:18

Bonsoir,

j'ai hier commencé une vérification systématique des posts #139 à 141
Après avoir été perturbé, j'ai rectifié et vérifié, mais je peux m'être encore trompé :

pour n=11 le nombre est 22 =10+ 9+ 3. B ne dépasse pas 3n=33 Méthode OK
pour n=12 le nombre est 27 =11+ 10+ 6. B ne dépasse pas 3n=36 Méthode OK

pour n=13 le nombre est 26 =12+ 11+ 3. B vaut 49 au pas 10 donc dépasse 3n=39. La Méthode est donc KO, même si en poursuivant B serait correct à 26 au pas 12.
pour n=17 le nombre est 51 =16+ 15+ 14+6. B vaut 54 au pas 11 donc dépasse 3n=51. La Méthode est donc KO, même si en poursuivant B serait correct à 34 au pas 16.

pour n=18, le nombre est 58=16+15+14+13 qu'il faut remplacer par 16+14+13+11+4 et alors la méthode pour n=2[4] est OK : Comment choisir la bonne liste ??

Mais peut-on toujours " fabriquer le nombre en un nombre minimal de termes décroissants à partir de (n-1) (ou n-2) jusqu'à 3 " ?
Eh bien NON, voici pour 8 <= n < 400 les erreurs :
Erreur sur n = 9 nombre = 9 , obtenu = 8
Erreur sur n = 27 nombre = 162 , obtenu = 161
Erreur sur n = 44 nombre = 451 , obtenu = 450
Erreur sur n = 86 nombre = 1741 , obtenu = 1740
Erreur sur n = 101 nombre = 2424 , obtenu = 2422
Erreur sur n = 160 nombre = 6280 , obtenu = 6279
Erreur sur n = 202 nombre = 9948 , obtenu = 9947
Erreur sur n = 259 nombre = 16576 , obtenu = 16575
Erreur sur n = 357 nombre = 31416 , obtenu = 31415

A suivre.....

totomm · 05-08-2011 22:17:01

Bonsoir,

@ freddy : Je vous présente mille excuses pour mon erreur dans les cas n=1[4]

car pour n=13, 17, 21,...(cas n=1[4] ) les nombres calculés sont bien entiers (respectivement 26, 51,84,,...). J'ai été perturbé par un de mes petits enfants, mais cela reste peu pardonnable ! Quasi endormi, je me suis relevé car une telle erreur de votre part m'est apparue impossible.
Je reste cependant sur l'imprécision du post #141 qu'il vous sera sans doute facile de dissiper

@+

totomm · 05-08-2011 17:35:32

Bonjour,

@ jpp : vous n'avez pas dû regarder le post #139 (du 06/07/2011) de freddy comme vous pensiez le faire (votre post #142) car pour n=13, 17, 21,...(cas n=1[4] ) le nombre calculé n'est pas entier ( respectivement 32.5, 59.5, 94.5,...)
Si pour n=13 on prend le nombre 32=12+11+9, après les pas 8 à 12, on a 36, 27,37,26,14 alors qu'on devrait terminer avec 13
Si pour n=13 on prend le nombre 33=12+11+10, on ne peut ajouter 9 à 36 pour le pas 9

Par ailleurs les indications des post #139, 140, et 141 ne permettent pas de comprendre comment construire dans le cas n=2[4] en tenant compte de la vague indication ;" inutile de préciser qu'il faut veiller à ce qu'aucun vase ne contienne un nombre négatif de boules. "

Sauf erreur de compréhension de ma part.
Cordialement

jpp · 09-07-2011 09:01:17

Bonjour.

pour les autres nombres qui sont de la forme [tex]n = \frac{p\times{(p+1)}}{2} + q[/tex]

je dois résoudre le système d'équations [tex]p^2 + 3p - 4n + 2a = 0 (1)[/tex]

[tex]r = p + a = 2n - \frac{p\times{(p+1)}}{2} (2)[/tex]

en résolvant (1) --> [tex]\Delta = 9 + 16n - 8a[/tex]

en remarquant que si je suprime [tex]8a[/tex] dans mon déterminant , j'obtiens alors une racine [tex]p[/tex]

supérieure à la racine entière que j'aurais du obtenir avec [tex]8a[/tex]

donc si je garde la partie entière de [tex]p[/tex] je peux trouver [tex]a[/tex] dans l'équation [tex](2)[/tex]

exemple. [tex]n = 999 --> p = \frac{-3 + \sqrt{9 + 16\times{999} - 8a}}{2}[/tex]

si je fais abstraction de [tex]2a[/tex] dans mon équation , donc de [tex]8a[/tex] dans mon

déterminant , je garde donc cette partie entière qui est dans ce cas [tex]p = 61[/tex]

mais comme je sais aussi que [tex]r = p + a = 2n - \frac{61\times62}{2} = 1998 - 1891 = 107[/tex]

je peux donc retrouver [tex]a = r - p = 107 - 61 = 46[/tex]

je peux maintenant définir ma stratégie en sachant qu'à [tex]P_{n-3}[/tex] je peux avoir

[tex]B = 3 A = 999 et C = 1995[/tex] alors à [tex]P_{r+1=108} --> B = 3 + \frac{996-108}{2} = 447 A = 999 et C = 1551[/tex]

à [tex]P_{107} B = 554 A = 999 C= 1444[/tex]

[tex]à P_{106} B = 447 A = 999 + 107 = 1106 C = 1444 et B + C = 1891 = \frac{61\times62}{2}[/tex]

puis entre [tex]P_{61} et P_{107}[/tex] j'échange à nouveau entre [tex]B <----> C[/tex]

à [tex]P_{62} --> B = 447 - \frac{106-62}{2} = 425 A = 1106 C = 1466[/tex]

et avant la remonté de toutes les boules dans l'urne A

à [tex]P_ {61} --> B = 425 + 62 = 487 A = 1106 et C = 1466 - 62 = 1404[/tex]

ma stratégie est donc la suivante:

je transfert la suite [tex]( 1 + 2 + 3 + 4 +...+52 + 53 ) sauf (27) A --> B puis 27 + ( 54+55+56+...+60+61) A--> C[/tex]

et ces 2 stratégies fonctionnent , la première avec les nombres 10 , 21 , 28 , 36 ....

et la seconde avec les autres meme n=3 ou n = 5

jpp · 08-07-2011 15:34:01

Bonjour.

Je vais commencer par les nombres de la forme [tex]n = \frac{p\times{(p+1)}}{2}[/tex]

a) si [tex]n et p[/tex] sont pairs alors à [tex]p_p --> B_p = \frac{(n-p)}{2} A_p = 2n et C_p = \frac{(n+p)}{2}[/tex]

b) si [tex]n et p[/tex] sont impairs , meme formule

ex: [tex]n = 10 .......................................................... n = 15[/tex]

[tex]n = 10 \begin{cases}Urne&B-----A-----C\\p_0&0-----30-----0\\p_1&1-----29-----0\\p_2&3-----27-----0\\p_3&3-----24-----3\\p_{p=4}&3-----20-----7\\p_5&8-----20-----2\\p_6&2-----20-----8\\p_7&9-----20-----1\\p_8&1-----20-----9\\p_9&10-----20-----0\\p_{10}&10-----10-----10\end{cases}

--- n = 15\begin{cases}Urne&B-----A-----C\\p_0&0-----45-----0\\p_1&0-----44-----1\\p_2&0-----42-----3\\p_3&0-----39-----6\\p_4&0-----35-----10\\p_{p=5}&5-----30-----10\\p_6&11-----30-----4\\p_7&4-----30-----11\\p_8&12-----30-----3\\p_9&3-----30-----12\\p_{10}&13-----30-----2\\p_{11}&2-----30-----13\\p_{12}&14-----30-----1\\p_{13}&1-----30-----14\\p_{14}&15-----30-----0\\p_15&15-----15-----15\end{cases}[/tex]

c) si [tex]n et p[/tex] sont de parité différente

alors [tex]B = partie-ent\left[\frac{(n-p)}{2}\right] A = 2n C = partie-ent\left[\frac{(n+p)}{2}\right] + 1[/tex]

alors pour [tex]n = 28 --> p = 7 --> B_p = 10 A_p = 56 C_p = 18[/tex]

et à [tex]p_{p+10} --> B_{p+10} = 5 C_{p+10} = 23[/tex]

ainsi qu'à[tex]p_{p+13} --> C_{p+13} = 4 B_{p+13} = 24[/tex]

freddy · 07-07-2011 10:29:01

Salut,

comme totomn l'a montré, il n'y a pas qu'une seule manière d'arriver au résultat pour n fixé.

Donc ta tactique est probablement aussi bonne que la mienne.

La seule différence, si je puis dire, est que la mienne prouve qu'une solution existe quel que soit n >= 8 ; c'est ce qu'il reste à faire pour la tienne, de mon humble point de vue.

Forum de mathématiques - Bibm@th.net

Répondre

Résumé de la discussion (messages les plus récents en premier)

Pied de page des forums