欢迎光临散文网 会员登陆 & 注册

『数学竞赛』格点问题,但是Minecraft

2023-08-20 08:00 作者:げいしも_芸  | 我要投稿

问题:

设T是平面中所有整点的集合,对于整点(x,y)和(u,v),当且仅当|x-u|+|y-v|=1时,称为相邻的点.

求证:

∃S⊆T,∀P∈T,在P及其相邻的点中恰有一个属于S.

标准解答:

设P(x,y)为整点,则与其相邻的四点为(x,y±1),(x±1,y),构造函数:

f(x%2Cy)%3D2x%2By

则P与其相邻的点对应5个不同的值:

2x%2By%2C2x%2By%5Cpm%201%2C2x%2By%5Cpm%202

这是5个相邻的整数,故其中有且仅有一个能够被5整除.  于是,令:

S%3D%5C%7B(x%2Cy)%5Cvert%20x%2Cy%5Cin%20%5Cmathbb%7BZ%7D%EF%BC%8C%E4%B8%945%5Cvert(2x%2By)%5C%7D

满足题意,则S即为题目所求

有关Minecraft的联想:

通过分析我们不难发现,对于S中的每一个整点,其上下左右的四个整点必定不属于S,这样便形成了一个十字形结构.

由于题目是证明S的存在性,因此我们只需要给出一个合适的S即可.

熟悉Minecraft的读者们可以发现:这与甘蔗的种植似乎有些许关联.

对于Minecraft的甘蔗,其能够种植的其中一个条件为:甘蔗下的方块与水相邻.

于是,我们可以将S中的元素看作水,P看作甘蔗.

那么,题目所给的条件便是在原游戏机制上加上了每株甘蔗与且仅与一格水相邻.

那么对甘蔗种植比较了解的读者一定就能想到下图所示方案:

图源:BV1cL411e7ia

那么,我们要如何用数学语言去描述集合S呢?

对S中的集合进行分析,不难发现:

对于集合S中的元素s_1和s_2,总有以下等式成立:

s_1%2Bp(1%2C2)%2Bq(2%2C-1)%3Ds_2%2C%5C%20%5C%20p%2Cq%5Cin%5Cmathbb%7BZ%7D

不妨以S中的某一元素为原点,即可得到:

S%3D%5C%7B(x%2Cy)%5Cvert%20%5C%20x%3Dp%2B2q%2Cy%3D2p-q%2C%5C%20%5C%20p%2Cq%5Cin%5Cmathbb%7BZ%5C%7D%7D

注意到:

(p%2B2q)%2B2(2p-q)%3D5p%5Cequiv%200(%5Cbmod%205%20%5C%20)

于是S等价于:

S%3D%5C%7B%20(x%2Cy)%5Cvert%20%5C%20x%2Cy%5Cin%20%5Cmathbb%7BZ%7D%EF%BC%8C%E4%B8%945%5Cvert%20(x%2B2y)%5C%7D

这与标准答案给出的S也是等价的,二者只需做一个反射变换即可得到彼此.

注意:这部分仅供做题时的思考,不可当作标准答案(应该不会有人这么干吧...)


『数学竞赛』格点问题,但是Minecraft的评论 (共 条)

分享到微博请遵守国家法律