2021第二届伊朗组合奥林匹克 第二试 中文翻译

第二试

1.湖中有块石头,排成一个圆圈. 只编号分别为的青蛙在这些石头上做游戏. 初始时, 每只青蛙随机选一个石头坐上去. (不同的青蛙可能坐在同一个石头上), 随后, 在每一步中, 编号为的青蛙沿顺时针方向跳个石头. 求证: 一定存在某个时刻, 至少六个石头上没有青蛙.

2.在一个大型停车场里停有 辆卡车. 我们可以将停车场看成一个 的网格表, 卡车看成若干的骨牌. 有些卡车水平放置, 有些卡车垂直放置. 垂直放置的卡车可以在他们所在的列上下移动, 水平放置的卡车可以在他们所在的行左右移动. 现在有一辆新的卡车要停进这个停车场. 当然, 它只能从边界进入.
(1)求证: 当时, 可以通过移动已有的卡车, 留出一个通道让新进卡车可以停进这个停车场.
(2)求证: 当时, 上述结论不成立.

3.正方体的每个顶点处各有一只蚂蚁. 在初始时, 每只蚂蚁任意选一条边, 沿着这条边以单位长度/分钟的速度爬行. 若某只蚂蚁爬到下一个顶点, 则他左转或者右转, 继续爬行. 第一次转弯时, 蚂蚁任意选一个方向. 此后每次转弯的方向与第一次转弯的方向相同. 若两只蚂蚁相遇, 则它们当场死亡! 若一只蚂蚁爬了三分钟仍不死, 则这只蚂蚁存活. 求证: 至少有一只蚂蚁可以存活.

4.对连通图, 他的路径数 指分隔这个图的顶点所需要的路的个数的最小值. 给定一个独立数为的连通图, 求其路径数可能的最大值, 用表示.
注: 对图, 其独立数指中两两互不相邻的点所组成的子图中顶点个数可能的最大值.

译者注：因为译者在图论上造诣太低，可能出线误译的情况。为避免误导读者，特附原文如下：

The of a graph is the minimum number of paths we need to partition the vertices of a graph. Given a connected graph with the independence number , what is the maximum possible value for the path number in this graph? Find the answer in terms of .

The independence number of a graph is the maximum possible number , such that there exist pairwise non-adjacent vertices in .

5.俄罗斯方块, 指无限大网格表中, 有限个以边相连的单元格组成的方格块. 我们可以有若干种方式将一个俄罗斯方块布置到网格表中, 可以旋转, 但不能翻转.
对一个俄罗斯方块 , 如果存在一种方式, 将所有正整数填入无限大网格表的单元格中, 使得对其中每个正整数, 至多只有一种布置方式, 满足它是 所覆盖的所有单元格中的最大数, 就称 是特殊的俄罗斯方块.
(1)证明正方形是特殊的俄罗斯方块.
(2)证明非正方形的矩形不是特殊的俄罗斯方块.
(3)证明: 一个俄罗斯方块是特殊的俄罗斯方块的充分必要条件是, 将其选择 后, 其形状不变.

6.对凸多边形, 设 为其中三个顶点构成的三角形. 将从中移除后, 可能还剩下是或个多边形, 我们称这些多边形对的"影响".
对多边形, 我们通过若干互相不交叉的对角线, 将其切割为若干个三角形, 称为对的一种三角剖分. 如果的一种三角剖分满足, 其中每个三角形的"影响"中, 恰有一个多边形的顶点个数为奇数, 就称这个三角剖分是美丽的.
求证: 对的一种三角剖分, 当且仅当我们可以移除一些对角线, 使得所有的区域都是四边形时, 该三角剖分是美丽的.

7.一群人有位, 其中位是破坏者. 夏洛克想要找出至少一位破坏者. 他将这些人派去执行任务, 已知每次任务需要派出人完成. 如果这人中有至少一个是破坏者, 则任务失败.那么, 夏洛克要找出至少一位破坏者, 至少需要执行多少次任务?