在\(5\times 5\)的方格表里，往若干个小方格中各画一条对角线（“/”或“\”），要求任意两条对角线都不相遇——既不共用格点，也不在方格内部相交。问：最多能在多少个小方格中画上对角线？
把方格的顶点称为格点，共有\(6\times6=36\)个。题目等价于：每个格点至多被一条对角线经过，且每个小方格至多放一条对角线。
答案：16条。 下面先给出一个能放满16条的摆法，再证明17条不可能。
用“/”“\”表示对角线、“·”表示空格，一种摆法如下（见图1）：
/ / / · \
· · / · \
\ \ · \ \
\ · / · ·
\ · / / /数一数恰有16条，且任意两条都不相遇（可对着图逐一核验），所以至少能放16条。
顺带一提：这个摆法用掉了36个格点中的32个，空出来的4个正好是大正方形的四个角。
一共有36个格点，每条对角线用掉2个互不相同的格点，而不同的对角线不共格点，所以对角线数不超过\(\lfloor 36/2\rfloor=18\)。
要从18降到16，还得用上“每个小方格至多放一条对角线”这条限制——这正是下面引理的用处。
引理. 在任意相邻两行（或相邻两列）组成的\(2\times5\)矩形内，最多能放6条对角线。
证明. 相邻两行之间有一条由6个格点组成的公共边界线（图2中的红点）。矩形内的每条对角线——无论它在上面一行还是下面一行——都恰好以这条线上的一个格点为端点：上一行的对角线，其下端点在这条线上；下一行的对角线，其上端点也在这条线上。又因为不同的对角线不共格点，这些端点两两不同，所以矩形内的对角线数不超过这条线上的格点数，即6。∎
反设能放17条。
第一步：中间的行与列都是满的。 第1、2行合起来是一个\(2\times5\)矩形，由引理至多6条；第4、5行同理至多6条。于是第3行至少有\(17-6-6=5\)条，而第3行只有5个格子，所以第3行满（5格全有对角线）。把“行”换成“列”同理可得：第3列也满。
第二步：中间这一行（列）的5条方向全都相同。 看同一行里相邻的两个格子，它们共有一条边的两个格点\(u\)（上）、\(v\)（下）。左格的对角线占\(u,v\)中的一个，右格的对角线也占\(u,v\)中的一个；要互不相遇，两者必须占不同的那个。而只有两格方向相同时才会占不同：
- 左“/”占\(u\)、右“/”占\(v\)：不冲突；
- 左“\”占\(v\)、右“\”占\(u\)：不冲突；
- 左“/”占\(u\)、右“\”占\(u\)：冲突；
- 左“\”占\(v\)、右“/”占\(v\)：冲突。
所以同一行里相邻两格方向必须相同，第3行的5条方向便全同。同理，第3列的5条方向也全同。
第三步：两种方向各自都会“撞车”。
先把这一步用到的两件事说清楚（都来自第一步）：
- 中间列（第3列）是满的，所以第2行第3列的格子\(A\)有对角线；由第二步，它作为中间列的一员，方向与中心格相同。
- 中间行（第3行）是满的，所以第3行第2列的格子\(B\)有对角线；方向也与中心格相同。
（要点：\(A\) 被填靠的是“中间列满”，\(B\) 被填靠的是“中间行满”，都与上下那两个\(2\times5\)区块内部怎么摆无关。）
于是 \(A=(2,3)\) 与 \(B=(3,2)\) 都有对角线，且方向一致——要么同为“/”，要么同为“\”。而这两格斜着相邻，恰好只共用一个格点。
再记住一条简单事实：一个格子的对角线，两个端点恰好是它的一组对角顶点——“/”连接左下角与右上角，“\”连接左上角与右下角。下面分两种情形（见图3）。
情形一：同为“/”。
- \(A\) 的“/”连接它的左下角与右上角，而它的左下角正是那个公共格点\(P\)；
- \(B\) 的“/”连接它的左下角与右上角，而它的右上角也正是\(P\)。
两条“/”都经过\(P\)，相遇，矛盾。
情形二：同为“\”。 这时 \(A\) 的“\”连接左上角与右下角；而第3行第4列的格子\((3,4)\)也在中间行上、同为“\”，它连接左上角与右下角，且它与 \(A\) 斜着相邻——共用的格点\(Q\) 既是 \(A\) 的右下角，又是 \((3,4)\) 的左上角。两条“\”都经过\(Q\)，相遇，矛盾。
两种情形都行不通，所以17条不可能。
综上，最多能放16条。
- 一般地，\(n\times n\)方格表的最大值记为\(a(n)\)，就是 OEIS 的 A264041：
\[ 1,\ 3,\ 6,\ 10,\ 16,\ 21,\ 29,\ 36,\ 46,\ 55,\ \dots\]
本题即\(a(5)=16\)。
- 当边长为偶数时有一个干净的公式。设\(n=2k\)，把\(2k+1\)行格点交替染成红、蓝，使蓝行恰有\(k\)行。每条对角线连接一红一蓝两个格点，所以对角线数不超过蓝格点数\(k(2k+1)\)，即\(a(2k)=k(2k+1)\)。例如\(a(4)=2\cdot5=10\)、\(a(6)=3\cdot7=21\)。上面的引理“相邻两行至多6条”正是这个染色界的一个局部特例。
- 本题\(16\)与“\(18\)”之间的差距，完全来自“同一个小方格不能同时放两条对角线”这条限制：若允许两条对角线在格心相交，\(6\times6=36\)个格点恰好能被\(18\)条对角线两两配对。