Combinatorics
Counting moves in knight's tours
[Décompte des mouvements dans les tours de cavalier]

Présenté par : Jean-Michel Bony

Dehornoy, Pierre1
1 11, impasse du Vivier, 27180 Arnières sur Iton, France
Comptes Rendus. Mathématique, Tome 336 (2003) no. 7, pp. 543-548.

Un tour de cavalier contient huit types de mouvements élémentaires. Nous montrons que les seules restrictions sur le nombre asymptotique de ces mouvements sont les bornes triviales existant pour toute boucle : pour tout choix de proportions compatible avec ces bornes, il existe une suite de tours réalisant asymptotiquement ce choix. On déduit l'existence de tours d'indice arbitrairement grand, ce qui répond positivement à la question de A. Grigis, C. R. Acad. Sci. Paris, Ser. I 335 989–992.

A knight's tour contains eight types of elementary moves. We prove that the only asymptotic constraints on the numbers of moves of each type are the trivial ones: for all proportions compatible with these constraints, there exists a sequence of tours asymptotically achieving these proportions. We deduce a positive answer to the question asked by A. Grigis in C. R. Acad. Sci. Paris, Ser. I 335 989–992 about the existence of tours with an arbitrarily large index.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/S1631-073X(03)00121-3
Dehornoy, Pierre 1

1 11, impasse du Vivier, 27180 Arnières sur Iton, France 
@article{CRMATH_2003__336_7_543_0,
     author = {Dehornoy, Pierre},
     title = {Counting moves in knight's tours},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {543--548},
     publisher = {Elsevier},
     volume = {336},
     number = {7},
     year = {2003},
     doi = {10.1016/S1631-073X(03)00121-3},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/S1631-073X(03)00121-3/}
}
TY  - JOUR
AU  - Dehornoy, Pierre
TI  - Counting moves in knight's tours
JO  - Comptes Rendus. Mathématique
PY  - 2003
SP  - 543
EP  - 548
VL  - 336
IS  - 7
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/S1631-073X(03)00121-3/
DO  - 10.1016/S1631-073X(03)00121-3
LA  - en
ID  - CRMATH_2003__336_7_543_0
ER  - 
%0 Journal Article
%A Dehornoy, Pierre
%T Counting moves in knight's tours
%J Comptes Rendus. Mathématique
%D 2003
%P 543-548
%V 336
%N 7
%I Elsevier
%U http://www.numdam.org/articles/10.1016/S1631-073X(03)00121-3/
%R 10.1016/S1631-073X(03)00121-3
%G en
%F CRMATH_2003__336_7_543_0
Dehornoy, Pierre. Counting moves in knight's tours. Comptes Rendus. Mathématique, Tome 336 (2003) no. 7, pp. 543-548. doi : 10.1016/S1631-073X(03)00121-3. http://www.numdam.org/articles/10.1016/S1631-073X(03)00121-3/

[1] Fukuda, K. http://www.cs.mcgill.ca/fukuda/download/cdd/README.cdd+

[2] A. Grigis, L'indice d'un tour de cavalier, C. R. Acad. Sci. Paris, Ser. I 335 (12) 989–992

[3] Jelliss, G. Knight's tour notes http://www.ktn.freeuk.com

[4] Rouse, W.W.; Coxeter, H.S.M. Mathematical Recreations and Essays, Dover, New York, 1987

[5] Vandermonde, A.T. Remarques sur les problèmes de situation, Mém. Acad. Sci. Paris (1774), pp. 566-574

Cité par Sources :