Les vases communicants ...

freddy · 19-04-2011 22:41:13

Hello,

voici quelques jours que je cherche à résoudre ce petit problème glané sur la toile et conçu par un brillant esprit.

Face à nous, trois urnes transparentes.

Dans la première se trouvent 3n boules, les deux autres sont vides.

Je dois, en n étapes, arriver à avoir n boules dans chaque urne avec la règle de gestion suivante : à chaque étape p, je peux déplacer exactement p boules d'une urne vers une autre.

Comment fait on ?

jpp · 20-04-2011 00:12:27

Bonsoir.

Je ne sais pas si ça peut fonctionner quelque soit N

Mais il faut déplacer à la p ieme opération p boules d'une urne A dans une urne B

alors je déplace les 3N boules en N-1 opérations car à la n ieme opération je ramene N

boules à sa place d'origine

je dois donc avoir [tex]3n = \frac{n\times(n-1)}{2} \; alors \; n=0 et n = 7[/tex]

je préleve donc dans l'urne 1 1 b ------> urne 2

2 b -------> urne 2

3 b --------> urne 3

4 b -------> urne 3 ----> TOTAL 7 b

5 b --------> urne 2

6 b --------> urne 2 -----> total 14 b

urne 1 <-------------------------------7 b ---- urne 2

jpp · 20-04-2011 06:10:13

Re.

Et sans enlever les boules de la première urne alors [tex] 2n = \frac{n\times(n+1)}{2}[/tex]

alors [tex] n = 3 [/tex]

urne 1 ----------> 1 b urne 2

-----------> 2 b urne 2 total 3 b

-----------> 3 b urne 3 total 3 b

Il n'y aurait donc que 2 solutions à mon avis

Dernière modification par jpp (20-04-2011 06:44:46)

freddy · 20-04-2011 12:06:49

Salut jpp,

c'est pas mal, mais en effet, il faut prouver qu'on n'y arrive pas quel que soit n, et montrer comment on fait quand c'est possible.

Donc il reste à montrer qu'il n'y a pas d'autres solutions, étant fait observer qu'à ce jour, je ne sais combien il y a de réponse possible.

A plus !

totomm · 20-04-2011 14:19:15

Bonjour,

il y a des solution pour n = 3, 5, 6, 7, 8, 9, 10....

Exemple pour n = 10, Les vases étant numérotés 0, 1, 2 :

n=10    p=1    de 0 vers 1    en 0: 29    en 1: 1    en 2 : 0
n=10    p=2    de 0 vers 1    en 0: 27    en 1: 3    en 2 : 0
n=10    p=3    de 0 vers 1    en 0: 24    en 1: 6    en 2 : 0
n=10    p=4    de 0 vers 1    en 0: 20    en 1: 10    en 2 : 0
n=10    p=5    de 0 vers 2    en 0: 15    en 1: 10    en 2 : 5
n=10    p=6    de 0 vers 2    en 0: 9    en 1: 10    en 2 : 11
n=10    p=7    de 0 vers 1    en 0: 2    en 1: 17    en 2 : 11
n=10    p=8    de 1 vers 0    en 0: 10    en 1: 9    en 2 : 11
n=10    p=9    de 1 vers 2    en 0: 10    en 1: 0    en 2 : 20
n=10    p=10    de 2 vers 1    en 0: 10    en 1: 10    en 2 : 10

cordialement

totomm · 20-04-2011 14:41:20

re,

apparemment pas de limite...
n=30    p=0    de 0 vers 0    en 0: 90    en 1: 0    en 2 : 0
n=30    p=1    de 0 vers 1    en 0: 89    en 1: 1    en 2 : 0
n=30    p=2    de 0 vers 1    en 0: 87    en 1: 3    en 2 : 0
n=30    p=3    de 0 vers 1    en 0: 84    en 1: 6    en 2 : 0
n=30    p=4    de 0 vers 1    en 0: 80    en 1: 10    en 2 : 0
n=30    p=5    de 0 vers 1    en 0: 75    en 1: 15    en 2 : 0
n=30    p=6    de 0 vers 1    en 0: 69    en 1: 21    en 2 : 0
n=30    p=7    de 0 vers 1    en 0: 62    en 1: 28    en 2 : 0
n=30    p=8    de 0 vers 1    en 0: 54    en 1: 36    en 2 : 0
n=30    p=9    de 0 vers 1    en 0: 45    en 1: 45    en 2 : 0
n=30    p=10    de 0 vers 1    en 0: 35    en 1: 55    en 2 : 0
n=30    p=11    de 0 vers 1    en 0: 24    en 1: 66    en 2 : 0
n=30    p=12    de 0 vers 1    en 0: 12    en 1: 78    en 2 : 0
n=30    p=13    de 1 vers 2    en 0: 12    en 1: 65    en 2 : 13
n=30    p=14    de 1 vers 2    en 0: 12    en 1: 51    en 2 : 27
n=30    p=15    de 1 vers 2    en 0: 12    en 1: 36    en 2 : 42
n=30    p=16    de 1 vers 2    en 0: 12    en 1: 20    en 2 : 58
n=30    p=17    de 1 vers 2    en 0: 12    en 1: 3    en 2 : 75
n=30    p=18    de 2 vers 1    en 0: 12    en 1: 21    en 2 : 57
n=30    p=19    de 1 vers 2    en 0: 12    en 1: 2    en 2 : 76
n=30    p=20    de 2 vers 1    en 0: 12    en 1: 22    en 2 : 56
n=30    p=21    de 1 vers 2    en 0: 12    en 1: 1    en 2 : 77
n=30    p=22    de 2 vers 1    en 0: 12    en 1: 23    en 2 : 55
n=30    p=23    de 1 vers 0    en 0: 35    en 1: 0    en 2 : 55
n=30    p=24    de 2 vers 0    en 0: 59    en 1: 0    en 2 : 31
n=30    p=25    de 0 vers 2    en 0: 34    en 1: 0    en 2 : 56
n=30    p=26    de 2 vers 0    en 0: 60    en 1: 0    en 2 : 30
n=30    p=27    de 2 vers 0    en 0: 87    en 1: 0    en 2 : 3
n=30    p=28    de 0 vers 2    en 0: 59    en 1: 0    en 2 : 31
n=30    p=29    de 0 vers 2    en 0: 30    en 1: 0    en 2 : 60
n=30    p=30    de 2 vers 1    en 0: 30    en 1: 30    en 2 : 30

freddy · 20-04-2011 15:57:46

Salut totomn,

chapeau ! Mais pour trouver toutes les solutions, il faut énoncer la règle complète de gestion et les caractérisques des cas où ce n'est pas possible (par exemple, n = 4 semble ne pas convenir).

A te lire.

totomm · 20-04-2011 17:03:01

re,

Enoncer la règle complète de gestion !!
aux symétries près (prmutations des 3 cases), le nombre de façons de trouver une solution est de :
4 pour n=5
4 pour n=6
16 pour n=7
56 pour n=8
104 pour n=9
410 pour n=10
1418 pour n=11
4446 pour n=12
15854 pour n=13

ensuite mon ordinateur risque d'exploser...
Qui dit mieux ?

freddy · 20-04-2011 17:23:53

Re,

je me suis mal exprimé : donne la stratégie à appliquer pour montrer comment on arrive à la solution pour n > 4.

L'argument "mon ordi va exploser" n'est pas une preuve irréfutable !

Do you see what I mean ?

Dernière modification par freddy (20-04-2011 22:40:14)

freddy · 20-04-2011 17:33:31

Re,

pour n= 6 & 7, tu fais comment par exemple ?

totomm · 20-04-2011 17:51:41

re,

c'est mon ordinateur qui fait, moi je le regarde ! je ne vais pas me lancer dans une théorie générale...
La solution la plus sensée pour beaucoup de problèmes, c'est de bien se servir de son ordinateur, et cela ne réduit pas, je pense, la capacité de raisonner et de trouver des lois générales quand nécessaire.

les 2 solutions pour 6
n=6    p=0    de 0 vers 0    en 0: 18    en 1: 0    en 2 : 0
n=6    p=1    de 0 vers 1    en 0: 17    en 1: 1    en 2 : 0
n=6    p=2    de 0 vers 1    en 0: 15    en 1: 3    en 2 : 0
n=6    p=3    de 1 vers 2    en 0: 15    en 1: 0    en 2 : 3
n=6    p=4    de 0 vers 2    en 0: 11    en 1: 0    en 2 : 7
n=6    p=5    de 0 vers 2    en 0: 6    en 1: 0    en 2 : 12
n=6    p=6    de 2 vers 1    en 0: 6    en 1: 6    en 2 : 6

et aussi
n=6    p=0    de 0 vers 0    en 0: 18    en 1: 0    en 2 : 0
n=6    p=1    de 0 vers 2    en 0: 17    en 1: 0    en 2 : 1
n=6    p=2    de 0 vers 1    en 0: 15    en 1: 2    en 2 : 1
n=6    p=3    de 0 vers 1    en 0: 12    en 1: 5    en 2 : 1
n=6    p=4    de 1 vers 2    en 0: 12    en 1: 1    en 2 : 5
n=6    p=5    de 2 vers 1    en 0: 12    en 1: 6    en 2 : 0
n=6    p=6    de 0 vers 2    en 0: 6    en 1: 6    en 2 : 6

exemple pour
n=7    p=0    de 0 vers 0    en 0: 21    en 1: 0    en 2 : 0
n=7    p=1    de 0 vers 1    en 0: 20    en 1: 1    en 2 : 0
n=7    p=2    de 0 vers 1    en 0: 18    en 1: 3    en 2 : 0
n=7    p=3    de 0 vers 2    en 0: 15    en 1: 3    en 2 : 3
n=7    p=4    de 0 vers 1    en 0: 11    en 1: 7    en 2 : 3
n=7    p=5    de 0 vers 2    en 0: 6    en 1: 7    en 2 : 8
n=7    p=6    de 0 vers 2    en 0: 0    en 1: 7    en 2 : 14
n=7    p=7    de 2 vers 0    en 0: 7    en 1: 7    en 2 : 7

Cordialement

totomm · 20-04-2011 18:23:06

re,

Pour ce problème, pour n'oublier aucun cas, le programme essaie tous les transferts possibles à chaque étape.
C'est bestial, mais efficace. Utilise itérations et récursions...en VBasic 2008 express.

Cordialement

freddy · 20-04-2011 22:41:47

Re,

OK, mais ce n'est pas l'ordinateur qui a programmé tout seul la solution.

Quel pgm as tu conçu ? Répondre à cette question donne déjà l'idée de la stratégie utilisée, non ?

totomm · 21-04-2011 10:43:20

Bonjour,
Organigramme ci-dessous :

Mais n'est-ce pas tellement évident !? C'est ce que l'on commence à faire soi-même avec crayon-papier...

totomm · 21-04-2011 13:52:23

reBonjour,

Pour ceux qui rechercheraient une bonne "stratégie", voici un cas particulier où l'égalité est obtenue avant la n-ième étape an partant de l'étape 14, égalité obtenue soit étape 17, soit étape 19:

n=19    p=14    de 1 vers 2    en 0: 2    en 1: 5    en 2 : 50
n=19    p=15    de 2 vers 1    en 0: 2    en 1: 20    en 2 : 35
n=19    p=16    de 2 vers 1    en 0: 2    en 1: 36    en 2 : 19
n=19    p=17    de 1 vers 0    en 0: 19    en 1: 19    en 2 : 19

n=19    p=14    de 1 vers 2    en 0: 2    en 1: 5    en 2 : 50
n=19    p=15    de 2 vers 0    en 0: 17    en 1: 5    en 2 : 35
n=19    p=16    de 0 vers 1    en 0: 1    en 1: 21    en 2 : 35
n=19    p=17    de 2 vers 1    en 0: 1    en 1: 38    en 2 : 18
n=19    p=18    de 2 vers 0    en 0: 19    en 1: 38    en 2 : 0
n=19    p=19    de 1 vers 2    en 0: 19    en 1: 19    en 2 : 19

freddy · 21-04-2011 16:58:31

Salut,

ce n'est pas exactement la question : il faut donner la bonne stratégie pour arriver au résultat au dernier coup, celui numéroté "n".

Et un pgm ne constitue toujours pas, pour moi, la preuve formelle de la validité du résultat quel que soit n > 4.

Mais ce n'est ni grave, ni important.
Ciao

PS : je réalise que ce programme de recherche "force brute" est la négation même de toute forme de pensée élaborée.

Question : pourquoi a t-on mis tant de temps à prouver la conjecture de Fermat alors qu'un pgm de recherche force brute aurait bien montré, "sans chercher à faire une théorie générale", qu'elle était, pour un nombre suffisemment grand d'entier, vrai seulement pour n=2, et pas au-delà.

Des fois, je me demande pourquoi Ducros, y se décarcasse.

Dernière modification par freddy (21-04-2011 17:23:00)

yoshi · 21-04-2011 18:56:46

Re,

@freddy
Programme ou pas, on m'a appris que quel que soit le nombre n aussi grand que l'on veut, si une propriété est toujours vraie après n essais consécutifs, rien ne prouve qu'elle est vraie. Seule une démonstration d'ordre général est valable.
Par contre, exhiber un contre exemple pour prouver qu'une propriété est fausse via la brute force pour gagner du temps, c'est tout à fait louable...

@totomm
Désolé ton organigramme m'apparaît, à première vue, un peu confus : c'est très clair pour toi, bien moins pour moi. J'aimerais assez reproduire en Python ce que tu as fait, mais je ne peux pas essayer tant que je ne pige pas :
dans un organigramme, pour moi, il y a une entrée et une sortie et entre les deux, ici, un appel à une fonction récursive...
Tu pourrais expliciter ça, s'il te plaît ?

@+

totomm · 22-04-2011 01:14:35

Bonjour à tous,

Vous ne croyez pas, je pense, que j'ignorerais que la force brute ne vaut pas une démonstration. A moins que le nombre de cas soit fini et bien déterminé.
Mais c'est disposer d'une intéressante possibilité d'investiguer la nature des solutions.
Ici c'est montrer que de 5 à n allant au moins audelà de 13, il y a un nombre de plus en plus grand de solutions....ce qui ne paraissait pas initialement établi...

Organigramme
confus: non. Succint : oui. En effet je n'ai pas mis "Début" suivi d'une flèche, ni une flèche se terminant par "fin". (C'est en général assez inutile sauf à des fins didactiques)
On entre dans la fonction récursive à chaque étape (p+1) bien sûr tant que p < n
On sort de chaque étape récursive quand les 6 transferts envisageables d'un vase à un autre ont été explorés.
On explore ainsi (6 puissance n) transferts... et c'est fini...
Pour être plus clair, j'aurais pu écrire "Retour de récursion p+1" au lieu de "Retour récursion" mais cela parait évident quand il faut "annuler tranfert(p)" qui a été mémorisé antérieurement...

Cordialement

jpp · 22-04-2011 05:06:45

Bonjour.

je crois que ce problème mérite qu'on y réfléchisse encore quelques jours. A moins que
quelqu'un vienne à le solutionner avant.

Donc Freddy, si tu pouvais faire durer le suspens tout le week-end...

Merci.

freddy · 22-04-2011 07:35:19

Salut,

@jpp : oui, tout le we et au-delà.

C'est une marche un peu particulière dans un des dédales de l'espace [tex]\mathbb{N}^3[/tex]

@totomn : je te sais trop intelligent pour l'avoir pensé un seul instant ! Je pense que tu l'es suffisamment pour exhiber une belle solution générale. C'est pour cela que je grogne un peu.

Bb

totomm · 22-04-2011 09:05:09

Bonjour,

Non, je n'ai réellement pas de solution générale !

Il suffit de voir quelques exemples sortis par l'ordinateur pour se rendre compte de la diversité d'utilisation des étapes. (jai sorti des solutions au hasard jusqu'à n = 506 et mon ordinateur ne sort plus rien ( en quelques minutes ) à partir de n=507...!
ce qui est remarquable, c'est que des étapes p et p+1 se suivent beaucoup 2 par 2 pour ajuster un vase A à A -1 et B à B+1.

j'attendrai donc qu'un chercheur plus éclairé ou plus acharné publie sur ce problème.

@yoshi : Sans doute êtes-vous connaisseur en PYTHON, Je suis bien plus à l'aise avec VBasic, mais je peux trancrire en PYTHON...

Cordialement

yoshi · 22-04-2011 12:06:14

Re,

totomm, je dois m'être mal exprimé : j'ai dit que pour moi (avis subjectif), ce n'était pas clair...
Mais si tu me renvoies sur les roses en disant que si, c'est clair même pour moi, alors je ne peux rien ajouter.

En effet je n'ai pas mis "Début" suivi d'une flèche, ni une flèche se terminant par "fin". (C'est en général assez inutile sauf à des fins didactiques)

Argumentation très spécieuse qui laisse la porte ouverte à bien des transgressions et je ne parlais pas des mots Entrée et Sortie, m'enfin ce n'est pas le problème.
Donc, à défaut d'expliciter ton organigramme, peux-tu mettre ton prog en VB (sauf il a un copyright, bien sûr ;-)), que je l'étudie, récrive mon propre organigramme et le transcrive (je souhaite le faire moi) en Python : j' ai fait quelques essais à la main, mais j'ai une question à freddy.
C'est bien 3n boules et n étapes : n étapes obligatoires ?
Parce que pour n=5, je peux faire :
A(15) B(0) C(0) --> A(14) B(1) C(0) --> A(12) B(1) C(2) --> A(9) B(1) C(5) --> A(5) B(5) C(5) ce qui ne me fait que 4 coups. Je présume qu'il en faut impérativement 5 ?

@+

freddy · 22-04-2011 15:25:14

Re,

oui, en exactement n étapes, ce qui veut dire qu'à l'étape précédente, une urne est vide, une autre contient n boules et la dernière en contient 2n.

Il faut trouver pour quelles valeurs de n on peut le faire et donner la stratégie (ou la bonne méthode) à appliquer (raisonnement mathématique à appliquer, ce qui permet de prédire dans pour quelles valeurs de n on ne peut rien faire. Déjà, on sait que pour n=1, 2 ou 4, on ne peut pas).

On doit pouvoir établir dans quelles conditions on peut on non le faire. D'où ma grogne à propos de l'usage de la pseudo intelligence artificielle.

totomm · 22-04-2011 16:07:07

Bonjour,

@ yoshi
J'ai mis mon code VBasic dans le forum "programmation" poir ne pas encombrer celui-ci
espérant qu'il sera suffisamment compréhensible...

@freddy : Pourquoi s"emballer, je n'ai jamais prétendu faire de l'intelligence artificielle !
je n'ai jamais parlé de démonstration pour toutes valeurs de n
j'ai simplement concocté un petit programme pour y voir plus clair après les réactions dans les premiers post, et post #4 en particulier
Je trouve que jpp a très bien commencé à traiter le problème, mais qu'il est intéressant de voir comment peuvent s'élaborer d'autres cheminements

freddy a écrit :

je réalise que ce programme de recherche "force brute" est la négation même de toute forme de pensée élaborée.

Bien sûr qu'un programme ne fait que présenter des résultats, mais il a fallu penser correctement pour obtenir des résultats pertinents...
Il faut quand même convenir qu'utiliser un bon outil aide la pensée à "devenir plus élaborée", et non le contraire !

Alors, freddy, quelle est votre approche de ce problème ?

Cordialement

totomm · 22-04-2011 17:03:02

Bonjour,

Une piste (entre autres) pour une approche "générale" :

totomm a écrit :

ce qui est remarquable, c'est que des étapes p et p+1 se suivent beaucoup 2 par 2 pour ajuster un vase A à A -1 et B à B+1.

Utilisé judicieusement pour n=20, 40, 80, 160...cela permet une solution où les transferts ne se font qu'entre les 2 premières urnes jusqu'à l'étape n-1, la troisième urne restant à 0 jusqu'à l'étape n.

A vous, Cordialement

Forum de mathématiques - Bibm@th.net

#1 19-04-2011 22:41:13

Les vases communicants ...

#2 20-04-2011 00:12:27

Re : Les vases communicants ...

#3 20-04-2011 06:10:13

Re : Les vases communicants ...

#4 20-04-2011 12:06:49

Re : Les vases communicants ...

#5 20-04-2011 14:19:15

Re : Les vases communicants ...

#6 20-04-2011 14:41:20

Re : Les vases communicants ...

#7 20-04-2011 15:57:46

Re : Les vases communicants ...

#8 20-04-2011 17:03:01

Re : Les vases communicants ...

#9 20-04-2011 17:23:53

Re : Les vases communicants ...

#10 20-04-2011 17:33:31

Re : Les vases communicants ...

#11 20-04-2011 17:51:41

Re : Les vases communicants ...

#12 20-04-2011 18:23:06

Re : Les vases communicants ...

#13 20-04-2011 22:41:47

Re : Les vases communicants ...

#14 21-04-2011 10:43:20

Re : Les vases communicants ...

#15 21-04-2011 13:52:23

Re : Les vases communicants ...

#16 21-04-2011 16:58:31

Re : Les vases communicants ...

#17 21-04-2011 18:56:46

Re : Les vases communicants ...

#18 22-04-2011 01:14:35

Re : Les vases communicants ...

#19 22-04-2011 05:06:45

Re : Les vases communicants ...

#20 22-04-2011 07:35:19

Re : Les vases communicants ...

#21 22-04-2011 09:05:09

Re : Les vases communicants ...

#22 22-04-2011 12:06:14

Re : Les vases communicants ...

#23 22-04-2011 15:25:14

Re : Les vases communicants ...

#24 22-04-2011 16:07:07

Re : Les vases communicants ...

#25 22-04-2011 17:03:02

Re : Les vases communicants ...

Réponse rapide

Pied de page des forums