Issu de la 14ème finale internationale FFJM - 1ère séance

Solution 1

Notons G[m,n] la valeur de la case (ligne m, colonne n).
G[1,1] = 1 , les autres éléments se calculant par récurrence selon le procédé indiqué.
Considérons la représentation binaires des nombres :
n = SOMME(k=0,1,...){B[n,k]*(2^k)}, B[n,k] étant binaire (0 ou 1).
et le "ou exclusif" vectoriel :
VEOR(m,n) = SOMME(k=0,1,...){beor(B[m,k],B[m,k])*(2^k)} avec {beor(Mk,Nk)=0 si Mk==Nk} et {beor(Mk,Nk)=1 si Mk!=Nk}
Après tout ça on obtient par induction :
G[m,n] = 1 + VEOR(m-1,n-1)
G[100,200] = 1 + VEOR(99,199) = 1 + VEOR['01100011','11000111')= 1 + '10100100'= 1+164 = 165

GENERALISATION :

Comme Mathias a vraiment du temps à perdre, il est maintenant avec une grille à N dimensions.
On note G[i[1],i[2],...,i[N]] les valeurs des cases.
G[1,1,...,1] = 1 , les autres cases se calculant de façon analogue au cas bidimensionnel :
- chaque case contient le plus petit entier strictement positif différent de tous ceux déjà écrits dans les portions de dimensions aboutissant à la case. Comme ça fait penser au jargon des juristes, définissons formellement les éléments de G :
G[1,..,1,..,1] = 1
et par récurrence :
G[i[1],..,i[k],..,i[N]] = = MIN{entiers positifs différents de UNION(k=1,..,N){UNION(0<=t<i[k]){G[i[1],..,i[k-1],t,i[k+1],..,i[N]}}}
Si tout ce formalisme ne nous a pas détourné de notre but, quelle est la formule de calcul de G[...] ?
D'après moi on devrait trouver : G[i[1],..,i[k],..,i[N]] = 1 + VEOR(i[1]-1,..,i[k]-1,..,i[N]-1)

Solution 2

Si l'on regarde ce qui se passe sur les premières rangées, on peut faire plusieurs remarques :
- la grille est symétrique par rapport à la première diagonale
- la grille présente une structure répétitive à des échelles plus grandes.
En particulier, si l'on appelle f(l,c) la valeur de la ligne l et la colonne c, on a :
- f(1,1)=1
- f(l,c)=f(c,l)
- à l'aide de cette dernière relation, on se ramène au cas où c <= l pour l,r > 1, on pose s = max { r \ 2^r < l}
si 2^s < r <= 2^(s+1), alors f(l,r)=f(l-2^s,r-2^s)
si r <= 2^s, alors f(l,r)=f(l-2^s,r)+2^s
Ainsi cherchant f(200,100), on a f(200,100)
=f(200-128,100)+128=128+f(72,100)
=128+f(100,72)=128+f(100-64,72-64)=128+f(36,8)
=128+f(36-32,8)+32=160+f(4,8)
=160+f(8,4)=160+f(8-4,4)+4
=164+f(4,4)=164+f(2,2)=164+f(1,1)
=165

Cliquez pour agrandir