Énigmes de gebrane et Namiswan
Bonjour,
Énigme1 de gebrane
Trois Parcs de voitures A, B et C.
Dans le premier parc A se trouvent 3N voitures , les deux autres parcs sont vides.
Peut-on démontrer qu'il existe pour tout N>4 une stratégie qui permet en N étapes, d'avoir N voitures dans chaque parc avec la règle de gestion suivante : à chaque étape p, on déplace exactement p voitures d'un parc vers un autre.
( Pour p=1, on déplace une seule voiture, pour p=2 on déplace exactement 2 voitures.... )
Qui va résoudre l’énigme un matheux ou un informaticien programmeur ?
Énigme2 de gebrane
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2024196#msg-2024196
Énigme3de gebrane
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2026680#msg-2026680
Variantes de l'énigme 3 de gebrane
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2027062#msg-2027062
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2027900#msg-2027900
Énigme1 de Namiswan
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2029288#msg-2029288
Énigme1 de gebrane
Trois Parcs de voitures A, B et C.
Dans le premier parc A se trouvent 3N voitures , les deux autres parcs sont vides.
Peut-on démontrer qu'il existe pour tout N>4 une stratégie qui permet en N étapes, d'avoir N voitures dans chaque parc avec la règle de gestion suivante : à chaque étape p, on déplace exactement p voitures d'un parc vers un autre.
( Pour p=1, on déplace une seule voiture, pour p=2 on déplace exactement 2 voitures.... )
Qui va résoudre l’énigme un matheux ou un informaticien programmeur ?
Énigme2 de gebrane
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2024196#msg-2024196
Énigme3de gebrane
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2026680#msg-2026680
Variantes de l'énigme 3 de gebrane
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2027062#msg-2027062
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2027900#msg-2027900
Énigme1 de Namiswan
http://www.les-mathematiques.net/phorum/read.php?4,2006748,2029288#msg-2029288
Le 😄 Farceur
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
peux tu préciser :
en N étapes exactement, ou au maximum ?
Merci.
je m'excuse pour ce retard oui exactement en N étapes.
Autre question : à chaque étape , les voitures déplacées sont prélevées dans le même parc et aboutissent aussi dans le même ou a-t-on toute liberté pour déplacer les p véhicules ?
Domi
l’énigme est délicieuse mais ça n’intéresse pas la foule
Pour intéresser les gens et faire comprendre, donner (à qui intéresse) une solution à la main pour N=3, N=5, ..., N=10
Le N=4 est impossible !?
p=2 on déplace 2 voiture de A vers B
p=3 on déplace 3 voiture de A vers C
Je donne aussi la cas N=10 et je note les étapes par p
p=2 on déplace 2 voiture de A vers B
p=3 on déplace 3 voiture de A vers B
p=4 on déplace 4 voiture de A vers B
p=5 on déplace 5 voiture de A vers C
p=6 on déplace 6 voiture de A vers C
p=7 on déplace 7 voiture de A vers B
p=8 on déplace 8 voiture de B vers A
p=9 on déplace 9 voiture de B vers C
p=10 on déplace 10 voiture de C vers B
Bien sûr les façons ne sont pas unique
Flora ;-) peux-tu me faire le cas N=6 et 7 ( tu vois je te tutoies)
Mais je n'arrive pas à voir de récursion
A défaut, je vais implémenter un algorithme Bruteforce de backtrack (en faite c'est bine bruteforce, le backtrack aurait été pour pas refaire les mêmes tests) et miser sur le fait qu'il y a une petite valeur qui ne marche pas X:-(
Parcontre, est-ce qu'un déplacement de A vers B puis de B vers A compte comme un déplcameent?
Sinon, il faut aussi que je modifie cela.
@Gebrane
J'ai le 4 je crois:
Je note 0, 1,2 les parkings.
Pour gagner du temps: je pars de 11 voitures dans 0,1 dans 1 et 0 dans 2
Mon algo me donne ca:
Etape 2 : / 1 de 1 vers 0/ 1 de 2 vers 1
Etape 3 : / 1 de 2 vers 0/ 1 de 1 vers 2/ 1 de 0 vers 1
Etape 4 : / 1 de 2 vers 0/ 1 de 0 vers 1/ 2 de 0 vers 2
Etape 5 : / 2 de 2 vers 0/ 3 de 1 vers 0
Etape 6 : / 5 de 0 vers 2/ 1 de 0 vers 1
Etape 7 : / 5 de 0 vers 2/ 1 de 0 vers 1/ 1 de 1 vers 0
Etape 8 : / 8 de 2 vers 1
Etape 9 : / 3 de 1 vers 2/ 1 de 2 vers 1/ 2 de 2 vers 1/ 1 de 0 vers 1/ 1 de 2 vers 0/ 1 de 0 vers 2
Etape 10 : / 4 de 1 vers 0/ 2 de 2 vers 0/ 4 de 0 vers 2
Etape 11 : / 4 de 1 vers 2/ 6 de 2 vers 1/ 1 de 2 vers 1
Etape 12 : / 2 de 0 vers 1/ 1 de 2 vers 0/ 1 de 0 vers 1/ 3 de 1 vers 0/ 1 de 1 vers 0/ 4 de 1 vers 2
Il comporte peut-être une faute, mais si c'est le cas, c'est très simple de la modifier.
J'ai utilisé le fait que le problème, qu'on choisisse au début de déplacement une voiture du premier parking sur le premier ou le deuxième reviens au même.
Je n'ai pas optimiser l'algorithme, pas étudier les symétries du problème ou autre, car je l'avait fait au cas où une valeur très petite posait défaut (@Gebrane posait la question pour N=4 par exemple).
import random for n in range (5,100): parking = [3*n -1,1,0] test=False compteur = 0 #nombre d'itérations log = '' while test == False: log = '' pp+=1 for i in range (2,n +1): log+= ' Etape ' + str(i) + ' : ' nb_deplacement = 0 while nb_deplacement < i: #tant que les i déplacements ne sont pas fait, on continue count=0 while count ==0: deplace = random.randint(0,2) count= parking[deplace] #count est le nombre de voitures sur le parking n° deplace, vers= deplace #il faut qu'il soit non nul pour faire un déplacement de cet endroit vers un autre while vers == deplace: #on choisit aléatoirement un des deux autres parking pour savoir où l'on va déplacer la/les voitures vers = random.randint(0,2) max_d = min(parking[deplace],i-nb_deplacement) #le maximum de voitures que l'on peut déplacer transfert = random.randint(1,max_d) # en ayant choisi le parking N°déplacement nb_deplacement+= transfert parking[deplace] -= transfert parking[vers]+= transfert log+= '/ ' + str(transfert) + ' de '+str(deplace) +' vers ' + str(vers) #On indique le déplcement effectué test = (parking[0]==n and parking[1]==n and parking[0]==n) if (pp%1000 == 0):, ### Pour voir grosso modo où en est l'algorithme si il boucle print(pp) print("Succes! For N = ",n)Je pense m'arrêter là, le problème étant dans la section analyse, ma façon de traiter l'énigme semble hors sujet. (non?)
Edit: Plus valable car testé avec 3N étapes J'ai quand même testé jusqu'à 26 rapidement et cela marchait (toujours sous réserve qu'il n'y est pas de coquille dans mon algo).
Edit2: Algo corrigé pour faire en N étapes et non 3N.
Domi
Oui j'ai corrigé, je l'avais fait en 3N étapes.
J'attends de savoir si un déplacement de A vers B puis de B vers A compte comme un déplacement.
Si c'est le cas, j'ai modifié l'algorithme pour qu'il résolve le problème en N étapes.
Dans le cas contraire, il faudrait rajouter deux-trois lignes.
Pour N=4, tu pars de 12 voitures dans le Park A, 0 dans B et 0 dans C et en 4 étapes exactement tu dois avoir 4 voitures en A , 4 voitures en B , 4 voitures en C ,
Je défie quiconque qui peut me donner une solution pour N=4, même celui à qui je pense :-P
La question est a mi-chemin entre l'analyse et la programmation et c'est exactement l'esprit du défit qui va gagner un esprit purement matheux ou un matheux programmeur.
Sinon, on avait:
Etape 1: /1 de 0 vers 1
Etape 2 : / 1 de 0 vers 1/ 1 de 0 vers 2
Etape 3 : / 1 de 1 vers 2/ 1 de 1 vers 2/ 1 de 0 vers 2
Etape 4 : / 3 de 0 vers 1/ 1 de 0 vers 1'
:-D
Dans ton cas, c'est un peu triviale en programmation car le contre exemple est trop facile à trouver.
Il y a moins de 27 combinaisons possibles pour le cas N = 4 en considérant la symétrie dont j'ai déjà parlé avant.
D'ailleurs, das mon cas aussi c'est triviale de prouver la terminaison de l'algorithme, je viens de me rendre compte. :-D
à chaque étape p, on déplace exactement p voitures d'un parc vers un autre
regarde bien mes exemples pour N=3 et N=10 , je te donne le cas N=6 et tu me donnes le cas N=7 pour voir si tu as bien compris
p=1 on déplace 1 voiture de A vers B
p=2 on déplace 2 voitures de A vers B
p=3 on déplace 3 voitures de B vers C
p=4 on déplace 4 voitures de A vers C
p=5 on déplace 5 voitures de A vers C
p=6 on déplace 6 voitures de C vers B
edit Pour N=4, si t' en ai capable donne moi un algorithme comme suit:
p=1 on déplace 1 voiture de ? vers ?
p=2 on déplace 2 voitures de ? vers ?
p=3 on déplace 3 voitures de ? vers ?
p=4 on déplace 4 voitures de ? vers ?
Ah d'accord, il y a unicité du parking ou l'on choisit le déplacement...
Appelons ab l'opération consistant à transférer des voitures de A vers B.
La situation initiale est $(3N,0,0)$.
On applique ab environ $2\sqrt{N}$ fois pour arriver à un résultat proche de $(N,2N,0)$.
On remarque qu'appliquer ab suivi de ba revient à transférer une seule voiture de B vers A, et qu'appliquer ba suivi de ab revient à transférer une seule voiture de A vers B. On transfère ainsi unité par unité dans un sens ou dans un autre jusqu'à ce qu'à l'étape $N-1$ on arrive exactement à $(N,2N,0)$. A l'étape $N$ on applique l'opération $bc$.
Exemple pour $N=20$ :
(60,0,0)
(59,1,0)
(57,3,0)
(54,6,0)
(50,10,0)
(45,15,0)
(39,21,0)
(32,28,0)
(24,36,0)
(15,45,0)
(5, 55,0), (16,44,0)
(4,56,0), (17,43,0)
(3,57,0), (18,42,0)
(2,58,0), (19,41,0),
(1,59,0), (20,40,0),
(20,20,20).
Donc:
-Par un algorithme simpliste "greedy" en $O(\sqrt{n})$ étapes on met $n+O(\sqrt{n})$ voitures dans chaque parking. Quitte à rajouter une étape on s'arrange pour que le nombre d'étapes restantes soit pair.
-En faisant des déplacements de 1 en 1 par paire d'etapes, on se ramene à exactement (n,n,n) en $O(\sqrt{n})$ étapes supplémentaires.
-Avec les étapes restantes on fait la stratégie du "sur place"
Il reste plus qu a expliciter mes O pour voir à partir de quel n ça marche (éventuellement en optimisant un peu), et faire à la main les cas restants.
Edit
Si $N$ est congru à 2 ou 3 modulo 4 il faut commencer par les opérations ac, ac, cb, puis faire $k$ fois l'opération ab avec $k$ de même parité que $N$ et proche de $2\sqrt{N}$.
Exemple pour $N=22$ :
(66,0,0)
(65,0,1)
(63,0,3)
(63,3,0)
(59,7,0)
(54,12,0)
(48,18,0)
(41,25,0)
(33,33,0)
(24,42,0)
(34,32,0), (23,43,0)
(35,31,0), (22,44,0)
(36,30,0), (21,45,0)
(5,61,0), (22,44,0)
(40,26,0), (21,45,0)
(1,65,0), (22,44,0)
(22,22,22).
Exemple pour $N=27$
(81,0,0)
(80,0,1)
(78,0,3)
(78,3,0)
(74,7,0)
(69,12,0)
(63,18,0)
(56,25,0)
(48,33,0)
(39,42,0)
p=10 : (29,52,0)
p=12 : (28,53,0)
p=14 : (27,54,0)
p=18 : (27,54,0)
p=22 : (27,54,0)
p=26 : (27,54,0)
p=27 : (27,27,27)
Par exemple si $N$ est congru à $0$ modulo $4$ et $N\geqslant 124$, alors l'algorithme marche. En effet, soit $m$ la partie entière de $\sqrt{\frac{N}{4}}+\frac{1}{2}$. On a $m\geqslant 6$. Soit $k=4m-1$.
On effectue $k$ fois l'opération ab. On arrive alors à $(\ast,8m^2-2m,0)$.
Il faut encore faire $2N-8m^2+2m$ transferts d'une unité, ce qui nécessite $4N-16m^2+4m$ opérations.
Le nombre d'opérations disponibles est $N-1-k=N-4m$, donc il suffit que $4N-16m^2+4m\leqslant N-4m$, ou encore $3N\leqslant 16m^2-8m$.
Or, $3N\leqslant 12(m+\frac{1}{2})^2\leqslant 16m^2-8m$ puisque $m\geqslant 6$.
Donc dans le cas $N\equiv 0\pmod{4}$ il faut vérifier à la main les cas $N=8,12,16,\ldots,120$.
En prenant $k=2m+1$ on traite les cas $N=20,32,44,76$.
Donc dans le cas particulier où $N$ est divisible par $4$, les seules valeurs de $N$ qui ne sont pas couvertes par mon algorithme sont N=12 et N=28.
Pour N=12 la méthode de Namiswan marche mieux.
p=1 : (35,1,0)
p=2 : (33,3,0)
p=3 : (30,6,0)
p=4 : (26,10,0)
p=5 : (21,10,5)
p=6 : (15,10,11)
p=8 : (14,11,11)
p=10 : (13,12,11)
p=12: (12,12,12).
De même pour N=28 :
p=1 : (*,1,0)
...
p=7 : (56,28,0)
p=11,15,19,23,27 : (56,28,0)
p=28 : (28,28,28).
import random test = False n=27 compteur = 0 while test == False: log = '/Etape 1 : 1 voiture de 0 vers 1' compteur+=1 parking = [3*n-1,1,0] for i in range(2,n+1): log += ' /Etape '+str(i)+ ' : ' if(parking[0] <i and parking[1]<i and parking[2]<i): continue else: chosen= -1 while chosen == -1: deplacement = random.randint(0,2) if parking[deplacement]>=i: chosen = 0 vers = deplacement while vers == deplacement: vers= random.randint(0,2) parking[deplacement] = parking[deplacement] -i parking[vers] = parking[vers] +i log+= str(i) +' voitures de '+str(deplacement)+' vers ' + str(vers) test= (parking[0]==n and parking[1]==n and parking[2] == n) if compteur%1000 == 0: print(compteur) print(parking) print(log)Exemples:
Pour n=6:
/Etape 1 : 1 voiture de 0 vers 1 /Etape 2 : 2 voitures de 0 vers 2 /Etape 3 : 3 voitures de 0 vers 2 /Etape 4 : 4 voitures de 2 vers 1 /Etape 5 : 5 voitures de 1 vers 2 /Etape 6 : 6 voitures de 0 vers 1
Pour n= 27: (Un test effectué, 600 essais)
/Etape 1 : 1 voiture de 0 vers 1 /Etape 2 : 2 voitures de 0 vers 1 /Etape 3 : 3 voitures de 1 vers 2 /Etape 4 : 4 voitures de 0 vers 2 /Etape 5 : 5 voitures de 0 vers 2 /Etape 6 : 6 voitures de 2 vers 0 /Etape 7 : 7 voitures de 0 vers 1 /Etape 8 : 8 voitures de 0 vers 1 /Etape 9 : 9 voitures de 0 vers 2 /Etape 10 : 10 voitures de 2 vers 1 /Etape 11 : 11 voitures de 1 vers 0 /Etape 12 : 12 voitures de 0 vers 1 /Etape 13 : 13 voitures de 0 vers 1 /Etape 14 : 14 voitures de 1 vers 0 /Etape 15 : 15 voitures de 1 vers 0 /Etape 16 : 16 voitures de 0 vers 1 /Etape 17 : 17 voitures de 1 vers 2 /Etape 18 : 18 voitures de 0 vers 1 /Etape 19 : 19 voitures de 2 vers 1 /Etape 20 : 20 voitures de 1 vers 0 /Etape 21 : 21 voitures de 1 vers 2 /Etape 22 : 22 voitures de 2 vers 1 /Etape 23 : 23 voitures de 0 vers 2 /Etape 24 : 24 voitures de 2 vers 1 /Etape 25 : 25 voitures de 1 vers 0 /Etape 26 : 26 voitures de 1 vers 2 /Etape 27 : 27 voitures de 0 vers 1
Je l'ai fait pour n=150 aussi, 28 000 étapes en moyenne, sur 10 test
C'es sur que ce n'est pas un algorithme en temps polynomiale, mais cela suffisait pour l'énigme de départ, si cette fois je l'ai enfin comprise !!
Source de l’énigme http://www.bibmath.net/forums/viewtopic.php?id=4567
solution proposée http://www.bibmath.net/forums/post.php?tid=4567&qid=30465
EDIT: il y a des erreurs. Je reprend plus proprement dans un post ultérieur
Première parite. Soit K la partie entière inférieure ou supérieure de $2\sqrt{N}$, de sorte que K ait même parité que N. On a donc $K\leq 2\sqrt{N}+1$.
Jusqu'à l'étape K, on distribue équitablement $1+\cdots+K=\frac{K(K+1)}{2} $ ($\approx 2N$) voitures de A vers B et C ( on répéte le processus "1 vers B 1 vers C, 1 vers C, 1 vers B", en mettant de côté la première voiture si K est impair): on obtient, à 1 près,$\frac{K(K+1)}{4}$ voitures dans B et dans C. On arrive à une configuration de voitures $(N+R_1,N+R_2,N+R_3)$ avec $|R_i|<\sqrt{N}$.
Deuxième partie: on fait les mouvements de 1 en 1 pour se ramener à (N,N,N). Il faut pour cela un nombre de paires d'étapes égal à $\max(|R_1|,|R_2|,|R_3|)$. Le nombre d'étapes de cette partie est donc inférieur à $2\sqrt{N}$, et on arrive à la fin donc à une étape $K'\leq 4\sqrt{N}+1$. Pour que l'on puisse faire le processus, il suffit qu'à tout moment le nombre de voitures dans chaque parking soit supérieur au nombre de voitures déplacées (=numéro de l'étape). Il suffit donc que $N-R_i\geq K'$. En optimisant un tout petit peu pour simplifier les calculs, il suffit en fait que $N-R_i\geq K'-1$ (car au début de la partie, le numéro de l'étape est plus petit que K' et à la fin, les restes ont diminués), et donc (puisque $K'\leq 4\sqrt{N}+1$ et $|R_i|\leq \sqrt{N}$) il suffit finalement que $N\geq 5\sqrt{N}$, donc $N\geq 25$.
Troisième partie: on fait la stratégie du sur place. La stratégie est possible si le nombre d'étapes restantes $N-K'$ est pair >2. Le nombre est automatique ment pair car on a choisi K pair dans la première partie et que l'on fait les étapes par 2 dans la deuxième partie, et l'inégalité $N-K'>2$ est plus faible que celle à vérifier pour la deuxième partie, donc automatiquement vérifiée aussi.
Conclusion: si pas d'erreurs de calculs, l'algorithme marche pour $N\geq 25$ (et probablement pour quelques valeurs avant)
Première partie. On choisit un nombre K d'étapes de même parité que N et de sorte que le nombre de voitures déplacées $1+\cdots+K=\frac{K(K+1)}{2} $ soit $\approx 2N$: précisément, K est tel que $\frac{K(K+1)}{2}$ soit l'entier le plus proche de 2N juste au dessus ou juste au dessous.
Pendant ces K étapes on fait partir les voitures de A pour les distribuer distribue équitablement vers B et C ( on répéte le processus "1 vers B 1 vers C, 1 vers C, 1 vers B", en mettant de côté la première voiture si K est impair): on obtient, à 1 près,$\frac{K(K+1)}{4}$ voitures dans B et dans C, pour arriver ainsi à une configuration $(N+R_1,N+R_2,N+R_3)$ avec $R_i$ "petit".
Les estimées pour cette partie: Je pose $M=2\sqrt{N}+1$. Puisque $ K \in \{p-1,p\}$ où p est le plus petit entier tel que $\frac{p(p+1)}{2}\geq 2N$, et que $\frac{x(x+1)}{2}>2N$ pour $x=2\sqrt{N}$, on déduit que $p\leq[2\sqrt{N}]+1\leq M$ et donc $K\leq M$.
De plus, $|\frac{K(K+1)}{2}-2N|<\frac{p(p+1)}{2}-\frac{(p-1)p}{2}=p\leq M$ d'où on déduit $|R_i|\leq M$.
Deuxième partie: on fait les mouvements de 1 en 1 pour se ramener à $(N,N,N)$. Il faut pour cela un nombre de paires d'étapes égal à $\max(|R_1|,|R_2|,|R_3|)$. Le nombre d'étapes de cette partie est donc inférieur à $2M$, et on arrive à la fin donc à une étape $K'\leq 3M$. Pour que l'on puisse faire le processus, il suffit qu'à tout moment le nombre de voitures dans chaque parking soit supérieur au nombre de voitures déplacées (=numéro de l'étape). Il suffit donc que $N-R_i\geq K'$. Puisque $K'\leq 3M$ et $|R_i|\leq M$, il suffit donc finalement que $N\geq 4M$.
Troisième partie: on fait la stratégie du sur place. La stratégie est possible si le nombre d'étapes restantes $N-K'$ est pair >2. Le nombre est automatique ment pair car on a choisi K pair dans la première partie et que l'on fait les étapes par 2 dans la deuxième partie, et l'inégalité $N-K'>2$ est automatique si $N\geq 4M$.
Finalement, j'obtiens que mon algo marche si $N\geq 4M$, c'est à dire $N\geq 8\sqrt{N}+4$, ce qui donne $N\geq 70$. Comme prévu, j'ai perdu pas mal en cours de route, mais j'espére au moins que cette fois c'est juste
Config initiale:(210,0,0)
(Première partie, distribution à la louche, K=16)
1:(209,1,0)
2:(207,1,2)
3:(204,1,5)
4:(200,5,5)
5:(195,10,5)
6:(189,10,11)
7:(182,10,18)
8:(174,18,18)
9:(165,27,18)
10:(155,27,28)
11:(144,27,39)
12:(132,39,39)
13:(119,52,39)
14:(105,52,53)
15:(90,52,68)
16:(74,68,68)
(deuxième partie,équilibrage)
17:(91,51,68)
18:(73,69,68)
19:(92,50,68)
20:(72,70,68)
21:(93,70,47)
22:(71,70,69)
23:(94,70,46)
24:(70,70,70):
(troisième partie, tours en rond)
25:(95,45,70)
26:(69,71,70)
27:(69,98,97)
28:(69,70,71)
29:(40,70,100)
30:(70,70,70)
31:(101,39,70)
32:(69,71,70)
33:(36,104,70)
34:(70,70,70)
...
etc (cycle tous les 4 temps)
...
66:(70,70,70)
67:(137,3,70)
68:(69,71,70)
69:(0,140,70)
70:(70,70,70)
-Un triple mouvement "A vers B, B vers C, C vers A" fait un changement élémentaire (+2,-1,-1) ( et dans l'autre sens ça fait bien sûr (-2,+1,1))
Autrement dit on peut faire deux déplacements de 1 en 3 étapes, c'est donc plus rentable que un déplacement de 1 en 2 étapes
-On peut faire du sur place en 7 mouvements: par ex on fait (+2,-1,-1) en 3 étapes puis deux déplacements (-1,+1,0) et (-1,0,+1) en 2*2 étapes.
On peut plus généralement faire du sur place pour tout nombre d'étapes supérieur ou égal à 6. On peut ainsi oublier les contraintes de parités dont j'avais besoin.
Je pense qu'en modifiant légèrement mon algo au vu de ces constats, on peut le faire fonctionner pour tout N>20 et quelques
I On choisit K tel que 1+...+K=K(K+1)/2 soit le plus proche possible de 2N (au dessus ou au dessous). Sur les K premières étapes, on distribue équitablement K(K+1)/2 voitures du parking A entre les parkings B et C, de sorte qu'à la fin il y a au plus une voiture d'écart entre B et C.
II On répète le mouvement "A vers B, B vers C, C vers A" (qui fait un (+2,-1,-1)) si il y a un manque de voitures dans A, ou alors son inverse "C vers A, B vers C, A vers B" (qui fait un (+2,-1,-1)) si il y a un manque de voitures dans A. Au bout d'un certain nombre de répétitions on se retrouve à une config (N,N,N) ou bien (N-1,N,N+1) (à permutation près). Dans le deuxième cas on peut se ramener à (N,N,N) en 2 étapes de plus.
III Sur les mouvements restants on s'arrange pour tourner en rond.
Si je ne dis pas de bétise, la stratégie marche pour N>16. La stratégie marche parfois sur les N plus petits que 16, éventuellement en la modifiant un peu. Pour les N plus petits que 16, les cas restants qui me semblent les plus durs à traiter sont les carrés N=9 et N=16 (N=4 étant impossible). Je pense avoir N=16, je n'ai pas fait N=9.
Remarque: dans la partie III, on peut modifier la stratégie car il est en fait plus facile de tourner en rond sur la config (N-1,N,N+1) que (N,N,N), car la config (N-1,N,N+1) est stable par (+1,-1,0) et également (+2,-1,-1).
Est ce que quelqu'un peut programmer la stratégie de Namiswan , par exemple je pense à @Sere
Je me mets dessus là, à voir si j'arrive bien à m'imprégner de ce qu'à dit @Namiswan.
PS. C'est Cere :-D
I)
Prendre K tel que K(K+1)/2 le plus proche possible de 2N. Jusqu'à l'étape K incluse:
Si K pair, répéter alternativement AB, AC et AC, AB
Si K impair, faire AB à l'étape 1, puis répéter alternativement AB, AC et AC, AB à partir de l'étape 2.
II)
Si le nombre de voitures dans A est < N-1, faire successivement AB, BC, CA
Si le nombre de voitures dans A est >N+1, faire successivement CA, BC, AB
S'arréter quand e nombre de voitures dans A est N à 1 près
Soit on est à N voitures partout, et c'est fini, soit on est à une config (N-1,N,N+1) et on se ramene à N partout en 2 coups (en allant du parking à N-1 vers celui à N+1 puis dans le sens inverse)
III)On regarde le reste modulo 4 du nombre d'étapes restantes.
Cas 1: 0 mod 4
On répète AB, BA, BA, AB jusquà la fin
Cas 2: 2 mod 4
On fait par ex une fois le cycle AB, BC, CA, CA, BC, AB, puis on suit le cas 1
Cas 3: 3 mod 4
On fait une fois le cycle AB, BC, CA, BA, AB, CA, AC, puis on suit le cas 1
Cas 4: 1 mod 4
On fait une fois le cycle AB, BC, CA, BA, AB, BA, AB, CB, BC puis on suit le cas 1
Pour l'étape 1 on fait donc deux fois de suite AC ?
Ca équilibre la distribution des voitures entre les parkings B et C
Pour ton étape 1:
En ayant implémenté et testé, je crois que l'étape k est non incluse et en ayant regardé ton cas n=70: si k est impair on est dans le cas de k pair non?
Edit: Puis j'en profiterais pour rendre le code le plus lisible possible pour autrui.
Je veux dire qu'on aura fait K transfert de voitures à la fin de la partie 1, le dernier transfert étant donc de K voitures. Pour N=70, K=16.
Ma remarque sur la cas impair est donc fausse aussi.
Je corrige.
k = 16
Etape 1 : [209, 1, 0]
Etape 2 : [207, 1, 2]
.
.
.
Etape 16 : [74, 68, 68]
Partie 2
Etape 17 : [91, 68, 51]
Etape 18 : [91, 50, 69]
Etape 19 : [72, 69, 69]
Etape 20 : [92, 69, 49]
Etape 21 : [92, 48, 70]
Etape 22 : [70, 70, 70]
Partie 3
Etape 23 : [47, 93, 70]
Etape 24 : [47, 69, 94]
Etape 25 : [72, 69, 69]
Etape 26 : [98, 43, 69]
Etape 27 : [71, 70, 69]
Etape 28 : [99, 70, 41]
Etape 29 : [70, 70, 70]
Etape 30 : [40, 100, 70]
Etape 31 : [71, 69, 70]
.
.
.
Etape 66 : [4, 136, 70]
Etape 67 : [71, 69, 70]
Etape 68 : [139, 1, 70]
Etape 69 : [70, 70, 70]
On a une différence sur l'étape 2, pourtant j'ai fait comme tu d"écris: la boucle AB BC CA non ?
J4ai enlever l'affichage des étapes pour que cela soit plus lisible.
Pour un code
def test(n,parking): return (parking[0]<=n+1 and parking[0]>=n-1) def test2(n,parking): return(parking[0] <=n+1 and parking[0] >=n-1 and parking[2]<=n+1 and parking[2]>=n-1) def AB(parking,k): parking[0]-=k parking[1]+=k def AC(parking,k): parking[0]-=k parking[2]+=k def BA(parking,k): parking[1]-=k parking[0]+=k def BC(parking,k): parking[1]-=k parking[2]+=k def CB(parking,k): parking[2]-=k parking[1]+=k def CA(parking,k): parking[2]-=k parking[0]+=k def nearest(point, k): #Trouve qui entre k(k+1)=/2 et (k+1)(k+2)/2 est le plus pret de 2n d_bas = abs(2*point-k*(k+1)*0.5) d_haut = abs(2*point -(k+1)*(k+2)*0.5) if d_bas < d_haut: return k else: return (k+1) def choose_k(n): #choisit le k pour l'étape 1 k = 1 s = 1 while s < 2*n: k+=1 s+=k return nearest(n,k-1) n= 70 parking = [3*n,0,0] k = choose_k(n) print("k = ",k) ### First step #### i=1 if k%2 == 1: AB(parking,i) i+=1 while i<k+1: AB(parking,i) i+=1 if(i<k+1): AC(parking,i) i+=1 if(i<k+1): AC(parking,i) i+=1 if(i<k+1): AB(parking,i) i+=1 k+=1 ##### RAJOUT 20H50 ### Second step #### print('Partie 2') if parking[0] <n-1: while (test(n,parking)== False and k<=n): AB(parking,k) k+=1 BC(parking,k) k+=1 CA(parking,k) k+=1 else: while (test(n,parking)== False and k<=n): CA(parking,k) k+=1 BC(parking,k) k+=1 AB(parking,k) k+=1 ### third step #### print("Partie 3") if k%4 ==0: while(k<n-3): AB(parking,k) k+=1 BA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 elif k%4 ==2: AB(parking,k) k+=1 BC(parking,k) k+=1 CA(parking,k) k+=1 CA(parking,k) k+=1 BC(parking,k) k+=1 AB(parking,k) k+=1 while(k<n-3): AB(parking,k) k+=1 BA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 elif k%4 ==3: AB(parking,k) k+=1 BC(parking,k) k+=1 CA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 CA(parking,k) k+=1 AC(parking,k) k+=1 while(k<n-3): AB(parking,k) k+=1 BA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 elif k%4 == 1: AB(parking,k) k+=1 BC(parking,k) k+=1 CA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 CB(parking,k) k+=1 BC(parking,k) k+=1 while(k<n-3): AB(parking,k) k+=1 BA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1Il me restait une erreur, sur le reste modulo 4.
Après vérification l'algo semble marcher pour k pair.
Par contre, pour k impair, l'étape 1 ne marche pas (j'ai fait: AB puis le cycle AB AC AC AB), exemple avec n=73 il faut prendre k = 17 et les étapes donnent:
Etape 1 : [218, 1, 0]
Etape 2 : [216, 3, 0]
Etape 3 : [213, 3, 3]
Etape 4 : [209, 3, 7]
Etape 5 : [204, 8, 7]
Etape 6 : [198, 14, 7]
Etape 7 : [191, 14, 14]
Etape 8 : [183, 14, 22]
Etape 9 : [174, 23, 22]
Etape 10 : [164, 33, 22]
Etape 11 : [153, 33, 33]
Etape 12 : [141, 33, 45]
Etape 13 : [128, 46, 45]
Etape 14 : [114, 60, 45]
Etape 15 : [99, 60, 60]
Etape 16 : [83, 60, 76]
Etape 17 : [66, 77, 76]
Edit: les fichiers pyhon ne sont pas supportés, je vais donc polluer le fil avec des longues lignes de codes, désolé...
J'ai joint les fichiers en modifiant l'extension en .pdf, je pense que si vous les téléchargez et renommez en .py cela doit marcher.
Je ne pense pas que j'aurais le temps de me remettre dessus pour fixer le cas $K$ impair, j'ai quelques problèmes de santé en ce moment (d'ailleurs mes capacités cognitives sont un peu touchées).
Je tiens quand même à saluer la solution proposé par @Namiswan que je trouve très élégante.
Je l'ai par exemple testé avec n= 788822, réglé en moins d'une seconde par son algo et mon implémentation extrêment peu optimiser (bon ca j'ai un peu fait exprès pour que si on lise le code, chaque étape soit compréhensible).
@Gebrane, j'ai fait mon possible avec mes capacités du moment
Version sans affichage
def test(n,parking): return (parking[0]<=n+1 and parking[0]>=n-1) def test2(n,parking): return(parking[0] <=n+1 and parking[0] >=n-1 and parking[2]<=n+1 and parking[2]>=n-1) def AB(parking,k): parking[0]-=k parking[1]+=k k+=1 def AC(parking,k): parking[0]-=k parking[2]+=k def BA(parking,k): parking[1]-=k parking[0]+=k def BC(parking,k): parking[1]-=k parking[2]+=k def CB(parking,k): parking[2]-=k parking[1]+=k def CA(parking,k): parking[2]-=k parking[0]+=k def nearest(point, k): #Trouve qui entre k(k+1)=/2 et (k+1)(k+2)/2 est le plus pret de 2n d_bas = abs(2*point-k*(k+1)*0.5) d_haut = abs(2*point -(k+1)*(k+2)*0.5) if d_bas < d_haut: return k else: return (k+1) def choose_k(n): #choisit le k pour l'étape 1 k = 1 s = 1 while s < 2*n: k+=1 s+=k return nearest(n,k-1) n= 788822 parking = [3*n,0,0] k = choose_k(n) print("k = ",k) ### First step #### i=1 if k%2 == 1: AB(parking,i) i+=1 while i<k+1: AB(parking,i) i+=1 if(i<k+1): AC(parking,i) i+=1 if(i<k+1): AC(parking,i) i+=1 if(i<k+1): AB(parking,i) i+=1 k+=1 ### Second step #### print('Partie 2') if parking[0] <n-1: while (test(n,parking)== False and k<=n): AB(parking,k) k+=1 BC(parking,k) k+=1 CA(parking,k) k+=1 else: while (test(n,parking)== False and k<=n): CA(parking,k) k+=1 BC(parking,k) k+=1 AB(parking,k) k+=1 ### third step #### K=k-1 print("Partie 3") if (n-K)%4 ==0: while(k<n-2): AB(parking,k) k+=1 BA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 elif (n-K)%4 ==2: AB(parking,k) k+=1 BC(parking,k) k+=1 CA(parking,k) k+=1 CA(parking,k) k+=1 BC(parking,k) k+=1 AB(parking,k) k+=1 while(k<n-2): AB(parking,k) k+=1 BA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 elif (n-K)%4 ==3: AB(parking,k) k+=1 BC(parking,k) k+=1 CA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 CA(parking,k) k+=1 AC(parking,k) k+=1 while(k<n-2): AB(parking,k) k+=1 BA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 elif (n-K)%4 == 1: AB(parking,k) k+=1 BC(parking,k) k+=1 CA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 CB(parking,k) k+=1 BC(parking,k) k+=1 while(k<n-2): AB(parking,k) k+=1 BA(parking,k) k+=1 BA(parking,k) k+=1 AB(parking,k) k+=1 print(k-1) print(parking)