Bonjour,

 Cliquez pour afficher

j'ai du mal déjà pour n=5
        A         B         C
       15        0         0
1/  14        1          0
2/   12       1         2        ou      12       3        0
3/    9         1         5                      9       4        2
        12       0        3                      15      0       0   inutile
4/     5        5        5      mais  p= 4  donc trop  tôt
          8        0        7                       8      4        3
          5        8        2                       5      4        6
          9       0         6
  5/    3       5         7                        3       0       12
           3       9         3                        3        4        8  
         10       3         2                       5        3       7
           0       9       6                           0       4      11
           9       5       1                          14       0       1
  

Bonsoir

 Cliquez pour afficher

n=3
9 0 0
8 1 0
6 3 0
3 3 3
n=5
15 0 0
14 1 0
12 1 2
9 1 5
5 5 5
n=6
18 0 0
17 1 0
15 1 2
12 1 5
12 5 1
12 0 6
6 6 6

 Cliquez pour afficher

Il me semble que tu n'as pas respecté les règles imposées

Bonsoir,
on peut coder chacun des transferts. Je propose :
1 pour transfert de A vers B et -1 de B vers A
2 pour transfert de A vers C et -2 de C vers A
3 pour transfert de B vers C et -3 de C vers B.
n transferts sont ainsi une liste de n nombres et la suite des valeurs dans les 3 urnes est facile à reconstituer et contrôler.
Mais démontrer qu'une solution existe Pour tout n autre que 1, 2 et 4 n'est pas si facile, et présenter un algorithme complet non plus.

Avec les premières solutions on peut essayer de voir si une loi se dégage.
Cas suivant :

 Cliquez pour afficher

n=7 : 1  2  2  2  2  1  -2

Pour n=5 j'avais une réponse en (n-1) au lieu de n transferts. Je rectifie :

 Cliquez pour afficher

n=5 : 1  1  1  1  3

Bonsoir,

Liste exhaustive (sauf erreur) des solutions pour n <=7 et nombre de solutions pour n<= 12

 Cliquez pour afficher

n= 1
n= 2
n= 3
1 [1, 1, 2]
2 [2, 2, 1]
n= 4
n= 5
1 [1, 1, 1, 1, 3]
2 [2, 2, 2, 2, -3]
n= 6
1 [1, 1, 3, 2, 2, -3]
2 [1, 2, 2, -3, 3, 1]
3 [2, 1, 1, 3, -3, 2]
4 [2, 2, -3, 1, 1, 3]
n= 7
1 [1, 1, 2, 1, 2, 2, -2]
2 [1, 1, 2, 2, 1, 1, -1]
3 [1, 2, 1, 1, 2, 1, -1]
4 [1, 2, 1, 3, -2, 2, 1]
5 [1, 2, 2, 2, 2, 1, -2]
6 [1, 2, 2, -3, -1, 2, 1]
7 [1, 2, 2, -2, 1, 3, 1]
8 [1, 2, 2, -2, 2, -3, 2]
9 [2, 1, 1, 1, 1, 2, -1]
10 [2, 1, 1, -1, 1, 3, 1]
11 [2, 1, 1, -1, 2, -3, 2]
12 [2, 1, 1, 3, -2, 1, 2]
13 [2, 1, 2, 2, 1, 2, -2]
14 [2, 1, 2, -3, -1, 1, 2]
15 [2, 2, 1, 1, 2, 2, -2]
16 [2, 2, 1, 2, 1, 1, -1]
n= 8
40
n= 9
78
n= 10
312
n= 11
1090
n= 12
3410

 Cliquez pour afficher

Je me suis intéressé aux 'chaines' solutions pour qui sont aussi sous chaines d'une solution pour
Pour
Il n'a a jamais de sous-chaîne de taille ou par contre il y en a toujours (à démontrer ..)  de taille
Si est solution pour alors   est solution pour

On a aussi les correspondances :



Finir par une de ces combinaisons semble être une CNS pour retrouver la chaîne dans le cas suivant.

J'ai aussi regardé le cas
et j'ai trouvé le cycle

Mais la condition n'est plus suffisante ...

Bonjour,

Le nombre de solutions pour n donné augmente avec n
Il faut donc en même temps  choisir une méthode et trouver des régularités entre des n voisins....

Bonsoir
Apparemment pas de réponse à la question initiale (difficile).
vham peut-être ? Sinon, lg124 peux-tu indiquer ton programme qui donne le nombre de solutions ?
Pour les petites valeurs de n (jusqu'à 7) je m'étais amusé avec une méthode graphique. Sur le diagramme ci-dessous, qui peut servir jusqu'à n=7,  2 trajets sont tracés pour n=7. On part du point en haut pour arriver au gros point central noir. En fait, à l'avant dernière étape on doit arriver sur 6 points du périmètre (facile à repérer) et à l'avant-dernière étape on doit arriver sur un des 6 points de l'hexagone qui entoure le point central. Grace aux symétries on a peu de solutions "vraiment différentes".

Bonsoir,

Une voie pour une solution (j'en ai une entièrement démontrée) :
Trouver des listes partielles de transferts entre seulement 2 urnes, Soit entre A et B en ayant 0 dans C, Soit entre A et C en ayant 0 dans B, listes partielles qui pourront ultérieurement être concaténées.

Bonjour,

On ne peut apparemment pas se dispenser, si l'on trouve une solution pour n₁, de montrer comment cette solution peut être  étendue à toute une famille de nombres par exemple en progression arithmétique....

Bonsoir,

Effectivement c'est plus simple dans ce sens ...

Avec l'indication :

 Cliquez pour afficher

si est solution pour :
est solution pour
est solution pour   et
est solution pour


Reste à expliciter des solutions quelconques pour les petits n,
par exemple
n=3 : [1, 1, 2]
n= 5 : [1, 1, 1, 1, 3]
n = 6 : [1, 1, 3, 2, 2, -3]
n = 7 : [1, 1, 2, 1, 2, 2, -2]
n = 8 : [1, 1, 1, 1, 1, -1, 1, 3]
n = 12 : [1,1,2,2, -3, 3, -3, -1, 2, -2, 1, 2]
n = 13 : [1,1,2,2, -3, 3, -3, 1, 2, -3, 1, -1, 3]
n = 14 : [1,1,2,2, -3, 3, -3, 3, 2, 1, 3, 2, -2, -3]

Bonjour,

>> lg124 j'essaie avec n=15 votre solution . Le départ est donc 45 0 0

 Cliquez pour afficher

1 44 1 0
2 42 3 0
3 39 6 0
4 35 10 0
5 35 5 5       Solution pour n=5 avec 30 de plus dans A
6 29 5 11
7 29 -2 18     il faut B n'est pas >7 pour transfert dans C !
sauf si je me trompe en interprétant les codes qui doivent suivre n= 5 : [1, 1, 1, 1, 3]
que vous donnez pour 2 puis 3

Bonjour,

A trop faire de copier-coller les trois finissent fausses ...

 Cliquez pour afficher

Citation :

si est solution pour :
est solution pour
est solution pour   et
est solution pour

 Cliquez pour afficher

tab = {}
tab[3] = [1, 1, 2]
tab[5] = [1, 1, 1, 1, 3]
tab[6] = [1, 1, 3, 2, 2, -3]
tab[7] = [1, 1, 2, 1, 2, 2, -2]
tab[8] = [1, 1, 1, 1, 1, -1, 1, 3]
tab[12] = [1,1,2,2, -3, 3, -3, -1, 2, -2, 1, 2]
tab[13] = [1,1,2,2, -3, 3, -3, 1, 2, -3, 1, -1, 3]
tab[14] = [1,1,2,2, -3, 3, -3, 3, 2, 1, 3, 2, -2, -3]


def gen(N):
  if N in [1,2,4] : return []
  if N in [3,5,6,7,8,12,13,14] :  return tab[N]
  n = N // 3
  r = N % 3
  s = gen(n)
  
  l = [2]
  for i in range(n-2):
    l += [-3,3]
  
  if r == 0 :
    l += [1,-2,2]
  elif r == 1 :
    l += [-3,3,-3,2]
  else :
    l += [-3,3,-2,1,2 ]

  return s+l
    

def verif(a,b,c,sol,start=0):
  i = start
  for e in sol :
    #print(a,b,c)
    i += 1
    if e == 1 :
      if a < i : print("fail a 1")
      a,b,c = a-i,b+i,c
    elif e == 2 :
      if a < i : print("fail a 2")
      a,b,c = a-i,b,c+i
    elif e== 3:
      if b < i : print("fail b 3")
      a,b,c = a,b-i,c+i
    elif e == -1 :
      if b < i : print("fail b -1")
      a,b,c = a+i,b-i,c
    elif e == -2 :
      if c< i : print ("fail c -2")
      a,b,c = a+i,b,c-i
    elif e == -3 :
      if c < i : print("fail c -3")
      a,b,c = a,b+i,c-i
    else:
      print("fail ???",e)
  #print(a,b,c)
  
  return a==b==c==len(sol)

Bonsoir,

Bravo lg124 : Votre solution est plus élégante que la mienne et la remplace...
Dans votre vérification il conviendrait de vérifier aussi les dépassements (3N) quand vous ajoutez
et bien sûr il faudrait une vérification en calcul symbolique (formel) pour avoir valeur de démonstration.
encore bravo

Quel est votre éditeur de Python ?
qui a l'air de faire un code "normalisé"

Bonsoir
Bravo à vous deux pour ce problème et cette résolution (même si je ne comprends pas tout de ce code).

Bonsoir,

Quelle était votre solution vham?

Il semble y avoir pas mal de possibilités dans le genre n->an+b mais celles avec a=2 étaient moins 'symétriques' (ou alors il faut regarder pour des plus grands n) et c'est la symétrie qui simplifie la preuve.

La preuve en explicitant simplement toutes les transitions est assez simple mais très lourde  à écrire ..

L'éditeur est Pyzo.

Bonsoir,

Ma solution décompose N-3=7q+r pour une séquence qui va de 5q+f(r) à N.
La séquence résultante comporte toujours soit B=0 soit C=0.
Votre solution avec r(0,1,2) est plus simple que la mienne avec r(0,1,2,3,4,5,6)

Bonsoir,

Démonstration formelle pour les séquences de n à 3n


il est évident qu'il n'y a pas de dépassement  <0 ou >9n

faire de même pour les séquences de n à 3n+1 et n à 3n+2

Bonjour,

Démonstration formelle pour les séquences de n à 3n+1

il est évident qu'il n'y a pas de dépassement  <0 ou >9n+3

Démonstration formelle pour les séquences de n à 3n+2