从一道国际数学竞赛题谈起

第42届普特南数学竞赛题中有这样一道试题:一个8×8的格子棋盘C中,若两个方格有公共顶点或公共边,则称它们是相连的,将数1,2,……,64分别填入每个格子,便得到C的一种标号,若对C的每一种标号,两个相连方格标号数的差至多为g,则称g为一个C-间隙,试定出最小的C-间隙C_g。此题可给出几种不同的解法,但有的方法很繁,本文把该题推广到一般情形n×n的格子棋盘中加以证明,其目的是用图标号的思想给出这类问题一种简捷。