Comme il a été suggéré que la rédaction précédente était trop succinte
, en voici une plus détaillée...
Démonstration du cas impair:
solution proposée par Lucien Xu:
> n est supposé impair<
> Lemme : Pour qu'un entier k appartenant à {1...2n-1} soit présent dans
> tous les ensembles constitués de la réunion des ieme ligne et ieme
> colonne, alors il doit apparaître au moins (n+1)/2 fois.<
D'après le Lemme, chacun des 2n-1 entiers à placer sur la matrice doit
apparaître au moins (n+1)/2 fois.
Or (2n-1)(n+1)/2 = (2n²+n-1)/2 = n²+n/2-1/2 >n² pour n>2
Le nombre d'entiers à placer serait supérieur au nb de cases dans le tableau
d'ou la contradiction.
Si n est impair, le problème n'admet donc pas de solution.
démonstration du lemme
Soit q un entier appartenant à {1....2n-1}
On cherche ici à trouver le nombre minimal de q pour que q appartienne à
tous les ensembles constitués de la réunion de ieme ligne et de la ieme
colonne.
Par soucis de clarté, notons A(i) = la réunion de la ieme ligne et de la
ieme colonne.
on suppose i différent de j
soit a(i,j) l'entier présent sur la case repérée par i l'indice de ligne et
j l'indice de colonne. On vérifie sans peine que a(i,j) appartient à 2
ensembles:
- la réunion de la ieme ligne et de la ieme colonne
-la réunion de la jeme ligne et de la jeme colonne
si on note q = a(i,j), alors tous les autres éléments de A(i)unionA(j) sont
différents de q. On dira alors que cet entier q "couvre" 2 lignes d'indice i
et j et 2colonnes d'indice i et j.
Mais si on place un nouveau q, ce qui est nécessaire pour satisfaire au
problème, ce nouveau q couvrira lui aussi 2 lignes et 2 colonnes telles
qu'elles seront différentes de celles considérées précédemment.
Et ainsi de suite. Finalement, si le côté du damier( = n) est pair, alors il
faudra d'après les remarques précedentes, que l'entier q apparaisse au moins
n/2 fois.
Avec n impair, il restera 1 ligne et 1 colonne non couvertes. il faudra
donc au minimum (n-1)/2 +1 = (n+1)/2 entiers q pour que chaque A(i)
contienne q.
Si i=j, le nb d'entiers q nécessaires sera plus grand puisqu'un q couvrira
alors uniquement 1 ligne et 1colonne. Si on note m le nb minimum de q dans
ce cas, on a alors m> (n+1)/2 et l'inégalité de la première partie devient :
m > (n+1)/2 donc m(2n-1) >(n+1)/2(2n-1)
or (n+1)(2n-1)/2>n² pour n>2
donc m(2n-1)>n² pour n>2 ce qui achève le raisonement.
Accueil 
Rechercher 
S'enregistrer 
Connexion 
Sujet: Carré magique 
)
