La danse des fourmis

Olympiades mathématiques, énigmes et défis
GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: La danse des fourmis

par GaBuZoMeu » 20 Fév 2021, 18:45

À défaut d'avoir une jolie réponse, je peux proposer un moche programme python qui calcule la période. Je mets l'accent sur les demi-tours (on peut s'intéresser au nombre de temps de demi-tours qu'il faut pour se retrouver dans la même configuration, éventuellement à un demi-tour près).
Ça peut peut-être aider à clarifier les idées, en tout cas ça permet de calculer un stock d'exemples qu'il serait pénible d'obtenir à la main.

Codage :

Pour aller vite, on appelle fourmi droite une fourmi qui va vers la droite et fourmi gauche une fourmi qui va vers la gauche.

Liste D pour les fourmis droites. Fourmis rangées dans l'ordre, avec pour chaque fourmi un couple

dont la première composante est un état : 0 si la fourmi est active, i si la fourmi est zombie après avoir rencontré la fourmi gauche n°i (numérotation commençant à 1 et allant jusqu'à p, nombre de fourmis gauches) et avant de la rencontrer de nouveau.
dont la deuxième composante est le nombre d'épisodes "zombie" vécus par la fourmi.

Liste G pour les fourmis gauches. Fourmis rangées dans l'ordre, avec pour chaque fourmi un couple

dont la première composante est l'indice du trou entre fourmis droites où elle se trouve (indice de la fourmi droite à l'extrémité gauche du trou, les indices de fourmis droites vont de 0 à n-1 où n est leur nombre),
dont la deuxième composante est le caractère "z" (si la fourmi est zombie après avoir rencontré une fourmi droite et avant de la rencontrer de nouveau) ou "a" (si la fourmi est active).

L'état initial est donné par une chaîne de caractères "d" ou "g" (pour fourmi droite ou gauche, respectivement).

Code: Tout sélectionner
# Procédure qui à partir d'une chaîne contituée de "d" et de "g",
# produit les listes intiales D et G

def Initiale(chaine) :
    n = chaine.count("d")
    D=[] ; G=[]; trou=n-1
    for c in chaine :
        if c=="d":
            D.append([0,0])
            trou = (trou+1)%n
        if c=="g":
            G.append([trou,"a"])
    return D,G


Code: Tout sélectionner
# Procédure qui fait sauter de trou chaque fourmi gauche

def PasGauche(D,G) :
    for i in range(len(G)) :
        trou=G[i][0] ; etat=G[i][1]
        if (etat=="z" and D[trou][0]==i+1) :
            D[trou][0]=0
            D[trou][1]+=1
            G[i][1]="a"
        if (etat=="a" and D[trou][0]==0) :
            D[trou][0]=i+1
            G[i][1]="z"
        G[i][0]=(trou-1)%(len(D))
    return D,G


Code: Tout sélectionner
# Procédure qui fait un demi-tour

def DemiTour(D,G) :
    for i in range(len(D)):
        D,G=PasGauche(D,G)
    return D,G


Code: Tout sélectionner
# Procédure qui prend en entrée une chaîne de "d" et "g",
# calcule la période en nombre de demi-tours,
# le nombre d'épisodes' "zombie" pour chaque fourmi droite,
# imprime la période en tours

def Periode(chaine) :
    D,G=Initiale(chaine)
    D,G=DemiTour(D,G)
    nb=1
    while not(all(d[0]==0 for d in D)):
        D,G=DemiTour(D,G)
        nb+=1
    per=nb//((nb+1)%2+1)
    print("Période en tours :",per )
    return nb, [d[1] for d in D]


Quelques exemples d'utilisation, d'abord correspondant aux dessins de Vassilia plus haut :

Code: Tout sélectionner
Periode("ddg")
Période en tours : 3
(3, [1, 1])

Code: Tout sélectionner
Periode("dddg")
Période en tours : 2
(4, [1, 1, 1])

Code: Tout sélectionner
Periode("ddgg")
Période en tours : 1
(2, [1, 1])

Code: Tout sélectionner
Periode("dgdg")
Période en tours : 3
(3, [2, 2])

D'autres exemples plus méchants qui montrent qu'un petit changement peut faire une grande différence.

Code: Tout sélectionner
Periode("dgdggdgdggdg")
Période en tours : 4
(8, [7, 7, 7, 7, 7])

Code: Tout sélectionner
Periode("ddgggdgdggdg")
Période en tours : 81
(162, [133, 133, 133, 133, 133])

On voit sur les exemples que le nombre d'épisodes "zombie" est le même pour toutes les fourmis droites. Ce n'est pas évident a priori, montrer ce fait pourrait être une étape dans la compréhension.



Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

Re: La danse des fourmis

par Imod » 20 Fév 2021, 21:54

Je vais essayer de taper le programme en Python ( ce sera une première ) car j'ai aussi plein de questions sans réponse .

1°) Pour d et g donnés quels sont les T extrêmes et les possibles ?

2°) Que se passe t-il si on insère ( ou supprime ) une fourmi dans un système donné ?

3°) Et si remplace un d par un g ?

4°) Et pour d+g constant ?

Mais il faut d'abord chercher des invariants . Il y en a un qui est établi , c'est la position des fourmis pour un ordre donné . Pour la période zombie ?

Imod

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: La danse des fourmis

par GaBuZoMeu » 21 Fév 2021, 00:32

Je vais essayer de taper le programme en Python ( ce sera une première ) car j'ai aussi plein de questions sans réponse .


Copier coller, ça existe ! ;)
J'ai mis mon code entre balises "code", ce qui fait que les indentations indispensables en python sont préservées.

Vassillia

Re: La danse des fourmis

par Vassillia » 21 Fév 2021, 03:10

Bonjour,
Juste pour vérifier que j'ai bien compris ce que fait le programme, on est d'accord que lorsque nb est impair, le nombre d'épisodes "zombie" par fourmis droites doit juste être doublé ? (C'est justement parceque je calculais nb et pas per que je me suis fais avoir pour la solution au problème initial donc je me méfie maintenant)

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: La danse des fourmis

par GaBuZoMeu » 21 Fév 2021, 09:32

Oui, ici j'ai trouvé plus commode de compter le nombre de demi-tours à l'issue duquel on se retrouve dans la configuration relative initiale des fourmis. Le nombre d'épisodes "zombie" s'y rattache. La proportion de temps passé par chaque fourmi en mode "zombie" est donc ce nombre d'épisodes divisé par la période en demi-tours.

Pour la période en tours, où on demande un retour aux places de départ (et pas aux places diamétralement opposées qui donnent la même configuration relative), c'est bien sûr la moitié de la période en demi-tours si celle-ci est paire et la période en demi-tours si celle-ci est impaire.

Cette histoire de tours/demi-tours porte facilement à confusion.

Au cours d'un demi-tour, chaque fourmi gauche croise exactement une fois chaque fourmi droite (sur la représentation graphique où les fourmis droites vont toujours vers le droite et les fourmis gauches toujours vers la gauche), soit en mode "actif" soit en mode "zombie". C'est pour ça que j'ai trouvé plus facile de travailler en demi-tours pour mon code.

Dans le problème précédent, pour l'histoire de l'observateur fixe, c'était plus commode de travailler en tours.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: La danse des fourmis

par GaBuZoMeu » 21 Fév 2021, 18:10

Quelques expériences. J'ai réécrit une procédure qui renvoie juste la période en demi-tours :
Code: Tout sélectionner
def PeriodeSimple(chaine) :
    D,G=Initiale(chaine)
    D,G=DemiTour(D,G)
    nb=1
    while not(all(d[0]==0 for d in D)):
        D,G=DemiTour(D,G)
        nb+=1
    return nb

Explorons :
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"g") for n in range(20)])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"gg") for n in range(20)])
[1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8, 17, 9, 19, 10, 21]
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"gdg") for n in range(20)])
[3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"gddg") for n in range(20)])
[2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"ggg") for n in range(20)])
[1, 4, 5, 2, 7, 8, 3, 10, 11, 4, 13, 14, 5, 16, 17, 6, 19, 20, 7, 22]
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"gdgg") for n in range(20)])
[4, 4, 8, 23, 74, 18, 148, 97, 82, 152, 368, 73, 514, 298, 228, 389, 878, 164, 1096, 607]
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"ggdg") for n in range(20)])
[4, 4, 8, 23, 74, 18, 148, 97, 82, 152, 368, 73, 514, 298, 228, 389, 878, 164, 1096, 607]
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"gddgg") for n in range(20)])
[5, 8, 23, 74, 18, 148, 97, 82, 152, 368, 73, 514, 298, 228, 389, 878, 164, 1096, 607, 446]
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"gdgdg") for n in range(20)])
[4, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+"ggddg") for n in range(20)])
[5, 8, 23, 74, 18, 148, 97, 82, 152, 368, 73, 514, 298, 228, 389, 878, 164, 1096, 607, 446]

Il y a des suites faciles à comprendre, d'autres qui le sont moins ...

Vassillia

Re: La danse des fourmis

par Vassillia » 22 Fév 2021, 00:09

Il y a quand même des observations intéressantes je trouve, appelons i le nombre de d et j le nombre de g :
- lorsque chaque fourmi g est encadré par des fourmis d alors la période en demi-tour semble valoir i+1 si i>j (accessoirement c'est vrai sur le tout premier exemple "méchant" en échangeant g et d)
- lorsque toutes les fourmis g sont regroupés cote à cote alors la période en demi-tour semble valoir i+j si j ne divise pas i et i/j +1 si j divise i (enfin si j nombre premier sinon à voir s'il faut introduire du pgcd ou pas)
- lorsque c'est le bazar mais que cela reste comparable du genre j=3 avec 1 fourmi g d'un côté et 2 fourmis g de l'autre coté séparés par des fourmis d alors il semble qu'à partir de 6 fourmis, on retombe sur la suite 8 ; 23 ; 74 ; 18 ; 148 ; 97...

Certes, je ne fais pas vraiment avancer le schmilblick car je ne sais même pas si ce que je raconte est vrai en dehors des exemples. J'avoue que je compte un peu sur le programme de GaBuZoMeu pour me dire si mes observations sont juste des coïncidences ou pas avant de réfléchir s'il y a moyen de le démontrer. Le 3eme cas est hors de ma portée vu que je ne sais même pas d'où vient la suite mais en la découpant en séquence de 6, cela me semble un peu moins bizarre puisqu'au moins c'est systématiquement croissant. A voir quelles formules se cachent derrière, pas trouvé.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: La danse des fourmis

par GaBuZoMeu » 22 Fév 2021, 12:04

Vassillia a écrit:- lorsque toutes les fourmis g sont regroupés cote à cote alors la période en demi-tour semble valoir i+j si j ne divise pas i et i/j +1 si j divise i (enfin si j nombre premier sinon à voir s'il faut introduire du pgcd ou pas)

Il est facile de répondre à cette question :
Code: Tout sélectionner
print([PeriodeSimple(n*"d"+6*"g") for n in range(40)])

[1, 7, 4, 3, 5, 11, 2, 13, 7, 5, 8, 17, 3, 19, 10, 7, 11, 23, 4, 25, 13, 9, 14, 29, 5, 31, 16, 11, 17, 35, 6, 37, 19, 13, 20, 41, 7, 43, 22, 15]

Ne peux-tu pas faire tourner le code python ?

Pour ce qui est de la suite bizarre qui apparaît avec 8,23,... aucune tentative pour la retrouver ou en retrouver des extraits sur OEIS n'a abouti.

On peut prolonger, mais ça prend du temps :
Code: Tout sélectionner
%time print([PeriodeSimple(n*"d"+"ggddg") for n in range(100)])
[5, 8, 23, 74, 18, 148, 97, 82, 152, 368, 73, 514, 298, 228, 389, 878, 164, 1096, 607, 446, 734, 1604, 291, 1894, 1024, 736, 1187, 2546, 454, 2908, 1549, 1098, 1748, 3704, 653, 4138, 2182, 1532, 2417, 5078, 888, 5584, 2923, 2038, 3194, 6668, 1159, 7246, 3772, 2616, 4079, 8474, 1466, 9124, 4729, 3266, 5072, 10496, 1809, 11218, 5794, 3988, 6173, 12734, 2188, 13528, 6967, 4782, 7382, 15188, 2603, 16054, 8248, 5648, 8699, 17858, 3054, 18796, 9637, 6586, 10124, 20744, 3541, 21754, 11134, 7596, 11657, 23846, 4064, 24928, 12739, 8678, 13298, 27164, 4623, 28318, 14452, 9832, 15047, 30698]
CPU times: user 1min 12s, sys: 0 ns, total: 1min 12s
Wall time: 1min 12s

Parmi les régularités remarquables, on peut noter ce qui se passe pour la parité.

Vassillia

Re: La danse des fourmis

par Vassillia » 22 Fév 2021, 13:02

Je ne me sers que de mon PC portable pro sur lequel je n'ai pas python (et pas les droits admin pour l'installer) mais c'est une mauvaise excuse, je te l'accorde, j'aurai pu ressortir un vieux PC fixe perso du grenier.

Merci pour ta réponse, il faut bel et bien introduire le pgcd, si les fourmis g sont regroupés, il semble que la période en demi-tour soit alors. Pour une fois que j'avais vu venir quelque chose, je profite .
Modifié en dernier par Vassillia le 22 Fév 2021, 15:43, modifié 1 fois.

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

Re: La danse des fourmis

par Imod » 22 Fév 2021, 14:39

Je confirme la formule quand les "d" et les "g" sont séparées . Ce n'est pas le cas le plus difficile mais il permet d'asseoir enfin quelque chose . Il serait pas mal aussi de comprendre pourquoi chaque fourmi "d" disparaît pendant le même temps durant un cycle , d'autant qu'il se produit la même chose pour les "g" .

Imod

Vassillia

Re: La danse des fourmis

par Vassillia » 22 Fév 2021, 15:38

Je crois que je l'ai la suite bizarre et je reste sur mon séquençage en 6 parceque je suis têtue et surtout parceque je n'ai pas trouvé mieux :

et pour tout entier alors
et pour tout entier alors
et pour tout entier alors
et pour tout entier alors
et pour tout entier alors
et pour tout entier alors

Voilà, voilà, je ne suis pas plus avancée car cela ne m'évoque rien de particulier à première vue mais je participe quand même.

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

Re: La danse des fourmis

par Imod » 22 Fév 2021, 20:22

C'est bien vu le modulo 6 et il y a sûrement moyen d'uniformiser tout ça .

Déjà , il me semble qu'il est plus simple de regarder , ... plutôt que ... alors le premier terme de chaque suite a exactement la forme de la récurrence et je pense qu'elles peuvent alors être regroupées en une seule .

Par exemple si alors et . On a exactement la même forme pour les 5 autres suites . Par exemple pour défini à partir de , et .

Par contre , le curieux enchaînement : 2 ; 3 ; 6 ; 1 ; 6 ; 3 laisse penser qu'il faut peut-être choisir un modulo multiple de 6 .

A suivre donc ...

Imod

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: La danse des fourmis

par GaBuZoMeu » 22 Fév 2021, 21:20

Pas si curieux que ça l'enchaînement 2,3,6,1,6,3.
C'est 6/pgcd(6,6k+i) pour i=3,4,5,6,7,8.

Vassillia

Re: La danse des fourmis

par Vassillia » 23 Fév 2021, 02:37

En fait c'est justement en regardant les différences successives que j'ai trouvé la récurrence mais ensuite je voulais donner la période en demi-tour comme c'est l'objectif désormais.

Bien vu, comme 6k+i est justement le nombre de fourmis droite en place, cela prend tout son sens. Il reste éventuellement l'initialisation à expliciter mais finalement cette suite commence à être moins bizarre.

J'ai lancé le programme de GaBuZoMeu pour 4 fourmis g dans les configurations non encore identifiées, pour ceux qui veulent un compilateur en ligne https://repl.it/languages/python
- groupe de 1g + groupe de 3g : on retombe exactement sur la même suite pas si bizarre que précédemment avec un séquençage de 4
- groupe de 2g + groupe de 2g : s'il y a une seule fourmi d entre eux idem par contre s'il y a 2 ou plus fourmis d entre les groupes alors on retombe presque sur la formule où toutes les fourmis sont regroupés ce qui pourrait être une bonne nouvelle si la généralisation est valable (pas testé encore mais au feeling si les groupes de fourmis g sont de même taille et séparés par au moins autant de fourmis d, je pense que cela peut le faire) car du coup quand les j fourmis g sont bel et bien séparés par 1 fourmi d alors on a qui semble cohérent avec les résultats précédents.

Je renonce pour ce soir, la victoire est encore loin mais on se rapproche ;)

Vassillia

Re: La danse des fourmis

par Vassillia » 25 Fév 2021, 04:39

Je vais quand même au moins essayer de démontrer « les cas faciles » car je crois que mon feeling tient debout. On va dire que les fourmis gauches sont particulièrement sympathiques et organisées. Elles se sont réparties en groupes de exactement fourmis avec au moins fourmis droites entre chaque groupe. On a le nombre de fourmi droites.

Lançons virtuellement le programme dans notre configuration

Le premier croisement des fourmis les font passer zombis et attribuent des numéros 1 aux premières fourmis droites croisées puis elles peuvent faire tous les croisements du demi-tour sans impact.

Les premiers croisements des fourmis n’ont pas d’importance car elles rencontrent des fourmis numérotées donc zombies. Le kème croisement des fourmis les font passer zombis et attribuent des numéros aux fourmis droites croisées puis elles peuvent faire tous les croisements du demi-tour sans impact.

On connait la numérotation puisqu’on s’est assuré d’avoir suffisamment de fourmis droites entre chaque groupe donc on sait par qui elles ont été numérotées, cela donne
Au bout d’un demi-tour, tout le monde est bien revenu sa place, les fourmis numérotées sont zombis et les fourmis pas numérotées sont actives

Le premier croisement des fourmis va les faire redevenir actives et effacer les numéros , puis les croisements suivants n’auront pas d’impact car elles rencontrent les fourmis droites zombies numérotées de à .

Les premiers croisements des fourmis n’ont pas d’importance tant qu’elles ne rencontrent pas leur alter ego : une fourmi droite numérotée . Lorsque c’est le cas, elles redeviennent actives et effacent les numéros .

On en est où ? Les groupes de fourmis gauches ont été décalés de fourmis droites vers la gauche en effaçant leur numéro ce qui donne

Plus aucune fourmi droite n’est numérotée donc tout le monde est actif et on retrouve une configuration comparable à celle d’origine. Attention, le second demi-tour n’est pas fini, il n’y a eu que croisements au lieu de croisements donc cela représente une portion de demi-tour. En pratique, je ne sais même pas si cette configuration est possible à cause des distances mais peu importe, on peut dire que les fourmis ralentissent le temps nécessaire et qu’elles vont accélérer par la suite, elles sont contraintes de respecter cet ordre de croisement de toute manière.

Comment revenir à notre configuration initiale, on va répéter l’opération en décalant les fourmis gauches de fourmis droites autant de fois que nécessaire pour les remettre comme à l’origine. Il faut répéter l’opération fois. Ce qui donnera vrais demi-tour et demi-tour en cumulant les morceaux de demi-tour donc au final . On n'oubliera pas une petite division par 2 si ce résultat est pair pour avoir la période en nombre de tours.

Je crois que c'est valable mais n’hésitez pas à me dire si ce n'est pas clair ou pire, j'imagine qu'on pourrait essayer d'écrire des suites pour le cas général mais je laisse cela à des plus courageux que moi.

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

Re: La danse des fourmis

par Imod » 25 Fév 2021, 14:01

J'avais aussi regardé ce cas particulier qui permet de résoudre la version que j'avais proposé le 15/02 dans le cas ou le nombre de fourmis de chaque sorte est premier entre eux . Il resterait bien sûr à voir pour cette version ce qui se passe en cas de chocs aux pôles .

On ( ou plutôt "tu" ) progresse :mrgreen:

Imod

Vassillia

Re: La danse des fourmis

par Vassillia » 26 Fév 2021, 20:45

Mouais, les chocs aux poles ne me semblent pas une si bonne idée à ce stade. Déjà, il faudrait préciser où les fourmis partent car ce ne sera plus un face à face.
Quelque soit la décision qu'on prenne : demi-tour, quart de tour, dépendant de l'angle de rencontre... elles risquent de finir au beau milieu de l'organisation d'au moins k fourmis droites ce qui peut mettre un joyeux bazar. Je ne dis pas que c'est infaisable, peut-être que tout se simplifie miraculeusement mais j'ai comme un doute.

Petite expérience amusante :
La suite 49;176;341;854;87;1252;739;574;124;2264;427;2878;803;1188;1967;4322;197;5152;2797;2018 est obtenue à partir de :
print([PeriodeSimple(n*"d"+"ddgddgddggddgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"ddggddgddgddgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"dddgdgddggddgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"dddgddgdggddgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"dddggdgddgddgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"dddggddgdgddgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"dddggddgddgdgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"ddddgdgdggddgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"ddddggdgdgddgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"ddddggddgdgdgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"ddddggdgddgdgg") for n in range(20)])


La suite 41;71;134;329;33;469;274;211;181;821;154;1033;287;423;698;1529;139;1813;982;707 est obtenue à partir de :
print([PeriodeSimple(n*"d"+"dddgddgddggdgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"ddddgdgddggdgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"ddddgddgdggdgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"dddddgdgdggdgg") for n in range(20)])
print([PeriodeSimple(n*"d"+"dddddggdgdgdgg") for n in range(20)])


Comment justifier mathématiquement les invariants ?
Peut-on trouver le pire cas en fonction du nombre total de fourmis ? On peut le programmer mais cela risque de devenir couteux en temps de calcul, le compilateur en ligne va m'envoyer promener donc autant limiter les cas à tester avant.
A votre avis pourquoi j'ai fais "les cas faciles" ? C'est stratégique, je compte sur vous pour le reste qui me parait nettement plus compliqué ::d

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

Re: La danse des fourmis

par Imod » 26 Fév 2021, 21:41

Bonsoir

Le passage aux pôles n'était qu'une froide remarque de peu d'intérêt ( j'y reviendrai dans des jours meilleurs ) , si le problème a une clé simple elle est liée au groupe des permutations . Personnellement les i et j des g et d me fatiguent assez vite ( ce n'est pas une critique ) , je préfère raisonner sur un cercle de fourmis noires tournant sur un cercle immobile de fourmis rouges . Un exemple intéressant : "ddgdgg" .

Je commence à reprendre goût au truc , merci :mrgreen:

Imod

Vassillia

Re: La danse des fourmis

par Vassillia » 26 Fév 2021, 22:00

Je te rassure, cela me fatigue aussi mais sans indicer les fourmis, je ne sais pas comment m'en sortir pour l'écrire proprement mais si tu as mieux que ma version, n’hésite pas, je ne le prendrai pas mal, au contraire.
Le cas "ddgdgg", on le connait par l’expérimentation (merci GaBuZoMeu), il me parait vraisemblable que la suite continue à vérifier la même règle mais pour le démontrer sachant que je ne sais ni initialiser la suite, ni visualiser ce qui se passe quand je rajoute 6 fourmis de même type, je ne pars pas gagnante :cry:

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

Re: La danse des fourmis

par Imod » 28 Fév 2021, 20:19

Je ne cherche certainement pas à jouer au plus malin , le problème est loin d’avoir révélé tous ses secrets et je ne suis pas plus avancé que tout un chacun . Le suivi de chacune des fourmis me donne le tournis et il me semble qu’on y voit plus clair si on fixe les fourmis rouges ( les moins nombreuses ) et qu’on fait tourner les noires . On peut alors modéliser le problème en distribuant uniformément les fourmis rouges sur le cercle et en partageant chaque portion crée en un nombre de parts égal au nombre maximum de fourmis noires cernées par deux rouges voisines . Par exemple RNRRNNRN deviendrait RNNRNNRNNRNN de façon à introduire deux fourmis noires entre chaque paire de fourmis rouges . Le déplacement des fourmis se résume alors à celui d’un arc de cercle dont les points caractéristiques sont fixes mais dont la nature peut varier ( libre ou fantôme attachée à un point rouge donné ) . Il me semble en particulier intéressant de repérer à quels moments les fourmis sont toutes visibles et comment ce moment se propage .

En toute humilité car c'est sans doute une voie sans issue :mrgreen:

Imod

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 16 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite