每日一题[3535]不变量

2024年清华大学强基计划数学试题（回忆版）#15

某无限大的城市内的所有街道都是正东西或南北向的直线，街道的交叉点称为格点，某人从某个格点出发，每个格点至多经过一次，最终回到出发点．已知向左转了 $100$ 次，则向右转的次数可以是（       ）

A．$97$

B．$98$

C．$102$

D．$104$

答案    AD．

解析    给出一个更强的命题：

引理    存在可行路径的充分必要条件是左转和右转次数之差的绝对值是 $3$ 或 $4$．

引理的证明    通过以下两种保持左转和右转次数之差不变的变换可以将任何可行路径转化为其凸包格点矩形，如图．

类似的，取一个足够大的矩形，可以通过改造它的某条边增加任意对 $LR$．因此当出发点在路径的顶点处时，左转和右转次数之差的绝对值为 $3$；当出发点在路径的边上时，左转和右转次数之差的绝对值为 $4$．

回到原题    向右转的次数可以为 $96,97,103,104$，选项 $\boxed{A}$ $\boxed{D}$ 正确．