来考验坛友们的数学水平了（答案已公布在52楼，71楼补充了图）

今井莉莎 · 发表于 2024-7-20 20:30

本帖最后由今井莉莎于 2024-7-20 23:28 编辑

刚刚结束的国际中学生数学奥林匹克竞赛（IMO）第5题，中韩两个东亚国家在这题上得分非常惨烈，但这题其实小学生都能做，看看坛友们能不能做出来

买码！注册！ · 发表于 2024-7-20 20:37

Problem 12.5.憨豆特工在一个 2024行 2083列的方格表上做游戏，方格表中恰有 2022 个方格各藏有一个坏人，初始时，憨豆不知道坏人的位置，但是他知道除了第一行和最后一行之外，每行恰有一个坏人，且每列至多有一个坏人，憨豆想从第一行移动到最后一行，并进行若干轮尝试，在每一轮尝试中，憨豆可以在第一行中任意选取一个方格出发并不断移动，他每次可以移动到与当前所在方格有公共边的方格内，（他允许移动到之前已经到达过的方格.)若悠豆移动到一个有坏人的方格，则此轮尝试结束，并且他被传送回第一行开始新的一轮尝试，坏人在整个游戏过程中不移动，并且憨豆可以记住每个他经过的方格内是否有坏人，若悠豆到达最后一行的任意一个方格，则游戏结束，求最小的正整数n，使得不论坏人的位置如何分布，愁豆总有策略可以确保他能够经过不超过n轮尝试到达最后一行.

天下何人 · 发表于 2024-7-20 20:38

本帖最后由天下何人于 2024-7-20 20:43 编辑

搞错了，再来

schneehertz · 发表于 2024-7-20 20:45

本帖最后由 schneehertz 于 2024-7-20 21:10 编辑

~~3次，只要遇到过两个敌人就可以构筑出一条完全没有敌人的路径~~

幻想风靡_ · 发表于 2024-7-20 20:46

本帖最后由幻想风靡_ 于 2024-7-20 20:49 编辑

想了一些算法都通过不了自己的样本测试，只能穷举最多2023次找到没坏人的那列了，承认自己是笨比

不对，思考了一下，可以二分法。那应该是2+log2(2021) = 13次

schneehertz · 发表于 2024-7-20 20:50

本帖最后由 schneehertz 于 2024-7-20 21:09 编辑

编辑。。

哈尔摩尼亚N · 发表于 2024-7-20 20:54

障眼法啊

每列最多1人，那不是探出一个之后一路直走就行

—— 来自鹅球 v3.0.0.82-alpha

ganxin225 · 发表于 2024-7-20 20:56

坏人如果倾斜式对角格子一线分布的话，你就一定得找到空的那列才能过去。

----发送自 HUAWEI MRR-W29,Android 10

骷髅兵 · 发表于 2024-7-20 21:00

假如坏人排的是条只有一个缝的斜线，那不是只能试到2023次才能绝对保证通过率？

幻想风靡_ · 发表于 2024-7-20 21:01

幻想风靡_ 发表于 2024-7-20 20:46
想了一些算法都通过不了自己的样本测试，只能穷举最多2023次找到没坏人的那列了，承认自己是笨比

不对，思 ...

整个写出来太麻烦了，整理一下大概思路给看得懂的人看吧
最麻烦的是阶梯式，需要找到空的那一列，然后阶梯式的必要非充分条件是对于r1行的坏人c1，和r2行的坏人c2，需要满足有|r1-r2|=|c1-c2|。
先走1列，1012列，和2023列，那么在1-1012列和1012-2023列之间肯定有一个区间不满足上述条件，然后对那个区间继续二分就可以。
至于非阶梯式很容易找到类似楼下那位schneehertz的方法进行绕过，但是不想写具体证明（也不太会写

yeo · 发表于 2024-7-20 21:01

本帖最后由 yeo 于 2024-7-20 21:13 编辑

第一次竖着走到坏人在的那一行
第二次竖着走到前一行，横着找到坏人在的那一列
第三次竖着走到前一行，走到这一行的坏人旁边，向下，走到前一行的坏人列，竖着抵达终点？

不太对，感觉不管你什么策略，总能找到让你试完所有2022个坏人的坏人排列方法...

坏人斜着排的话，就只能靠试了？我猜n是2023

天下何人 · 发表于 2024-7-20 21:03

ganxin225 发表于 2024-7-20 20:56
坏人如果倾斜式对角格子一线分布的话，你就一定得找到空的那列才能过去。

----发送自 HUAWEI MRR-W29,Andr ...

我也是想到了这个，所以这题就是怎么找到空白列或者6楼这种错位排列

schneehertz · 发表于 2024-7-20 21:05

本帖最后由 schneehertz 于 2024-7-20 21:07 编辑

天下何人发表于 2024-7-20 21:03
我也是想到了这个，所以这题就是怎么找到空白列或者6楼这种错位排列

编辑
想简单了，还得再想想

天下何人 · 发表于 2024-7-20 21:09

本帖最后由天下何人于 2024-7-20 21:24 编辑

骷髅兵发表于 2024-7-20 21:00
假如坏人排的是条只有一个缝的斜线，那不是只能试到2023次才能绝对保证通过率？ ...

肯定可以算的，比如第一次走第一列发现敌人在第1行，第二次最后一列发现在最后最后一列，第三次走中间的第1012列，发现敌人在1012行，那1013到2022列就肯定不是斜线排列，2-1011就不用试了。
其实就是先探一头一尾，再探中间，看两边有哪一边肯定不是斜线，一直重复

骷髅兵 · 发表于 2024-7-20 21:13

天下何人发表于 2024-7-20 21:09
肯定可以算的，比如第一行敌人在第一列，最后一行敌人在最后一列，然后马上走中间的1012列，根据这列敌人 ...

怎么算，不就是个穿小孔的概率问题？脸黑就得试到最后一次

克克克克 · 发表于 2024-7-20 21:18

直觉上要3次尝试才能平分4份，4^6=4096>2024，盲猜答案在3*6=18次以内

wyqjlol · 发表于 2024-7-20 21:19

3次吧吧吧吧吧吧吧吧

幻想风靡_ · 发表于 2024-7-20 21:20

骷髅兵发表于 2024-7-20 21:13
怎么算，不就是个穿小孔的概率问题？脸黑就得试到最后一次

二分。
阶梯式的话，行之差一定等于列之差，中间一共2022行，2023列，取1，1012和2023后肯定有个区间不满足上面条件。然后对不满足的继续二分

schneehertz · 发表于 2024-7-20 21:22

确实要用2分法，排除掉连续的阶梯部分，需要13次

ackroyd2 · 发表于 2024-7-20 21:23

提示: 作者被禁止或删除内容自动屏蔽

INDIASH · 发表于 2024-7-20 21:29

本帖最后由 INDIASH 于 2024-7-20 21:37 编辑

可能一开始两边不需要走？直接二分走中按遇到坏人时的当前格行列数的大小，找个斜率绝对值大于1的一半应该就行了吧

ywj321 · 发表于 2024-7-20 21:35

本帖最后由 ywj321 于 2024-7-20 21:43 编辑

一看答案就是2023。
简化问题，第二行就必须要2023种可能。
第二行你能穿过去，就是直线到达终点。
至于到底是一共2024行，还是只有3行，结果一样。

还不明白的话，可以把题目改成：坏人可能出现在第二行任意一个位置（减一），但是第二行有一个位置肯定是生门。你最多要尝试几次？

天下何人 · 发表于 2024-7-20 21:40

本帖最后由天下何人于 2024-7-20 21:45 编辑

每次探可疑部分的最中间一列，可以排除一半(单数的话向下去整)
第一次，还剩1011列可疑。
第二次，还剩505列可疑
第三次，还剩252列可疑
第四次，还剩126列可疑
第五次，还剩63列可疑
第六次，还剩31列可疑
第七次，还剩15列可疑
第八次，还剩7列可疑
第九次，还剩3列可疑
最后3列不一定有空列，可能是错位排列，需要走3次

所以是12次

ryanghj · 发表于 2024-7-20 21:43

本帖最后由 ryanghj 于 2024-7-20 22:06 编辑

3次

这个问题和二分法无关，因为你知道某行坏人所在的列位置后是无法一步到达下一行该列的，需要尝试找到第二行没有坏人的列才行，所以最坏的情况是（第一次向下走找到第一个有坏人的列）+（第二次向下走找到第二个有坏人的列）+（第三次根据前两次的结果走到尽头）

走到尽头的方法是，假设两次分别探得a行i列和b行j列有坏人，其中a<b，那么就从第一行j列开始走到a+1行，然后从a+1行i列开始走到结尾（也可以走到a-1行，b-1行，都不影响）

补充：有个特例就是b=a+1，这种情况下需要先沿着j列走到a行，然后在a行除i之外的任意一列走到b行，然后在b行i列走到底

ywj321 · 发表于 2024-7-20 21:48

天下何人发表于 2024-7-20 21:40
每次探可疑部分的最中间一列，可以排除一半(单数的话向下去整)
第一次，还剩1011列可疑。
第二次，还剩505 ...

你再想想，这个题目不适用二分法。。。

你第二行确保通过就需要最多2023次测试

天下何人 · 发表于 2024-7-20 21:59

ryanghj 发表于 2024-7-20 21:43
3次

这个问题和二分法无关，因为你知道某行坏人所在的列位置后是无法一步到达下一行该列的，需要尝试找到 ...

就是二分法。
因为列数比敌人数多1，二分后肯定有一边是无法排成斜列的

通过的方法有两种，一是找到空白列，二是相邻的三列不成斜线，两个特点都是无法排成斜线，所以只要不断二分，缩小无法排成斜线的敌人的范围就行了。

ryanghj · 发表于 2024-7-20 22:01

本帖最后由 ryanghj 于 2024-7-20 22:04 编辑

天下何人发表于 2024-7-20 21:59
就是二分法。
因为列数比敌人数多1，二分后肯定有一边是无法排成斜列的

和二分无关，最坏情况只需要两步探得两个坏人就行

骷髅兵 · 发表于 2024-7-20 22:04

幻想风靡_ 发表于 2024-7-20 21:20
二分。
阶梯式的话，行之差一定等于列之差，中间一共2022行，2023列，取1，1012和2023后肯定有个区间不满 ...

这又不是什么称重问题，二分有什么用？你如何知道那个孔在斜线的哪一边？

VMDL · 发表于 2024-7-20 22:07

对第 1 行探测第 2 到第 n-1 个格子，对第 2 行探测第 3 到第 n-2 个格子，以此类推

在这些格子上如果有坏人说明格子上方三个位置和左右两个位置都是安全的，接下来只需要用两次探测出下侧左右方的坏人

这样探到第 n/2 行还没问题的话再左右探一遍，会剩下一个 n/2 行 n/2+1 列的子矩形，如果正确的话或许可以在 log 次内解决

鸳鸳相抱 · 发表于 2024-7-20 22:10

ryanghj 发表于 2024-7-20 22:01
和二分无关，最坏情况只需要两步探得两个坏人就行

最坏情况是每次去新的一行都碰到坏人

cjtk · 发表于 2024-7-20 22:11

那个，是可以左右移动的，不是说每一次只能一条路走到底，最坏情况是坏人斜着站，那第二排我左右移动探索2-2022，然后下到第三排探索3-2021，以此类推。碰到敌人时就是知道缺口在哪了

天下何人 · 发表于 2024-7-20 22:15

本帖最后由天下何人于 2024-7-20 22:18 编辑

骷髅兵发表于 2024-7-20 22:04
这又不是什么称重问题，二分有什么用？你如何知道那个孔在斜线的哪一边？ ...

因为列数比敌人数多1，二分后肯定有一边是无法排成斜线

比如第一步探中间1012，(1012，1013)是敌人，所以左边可以,(1，2)、(2，3)……排成斜线(第一行安全行所以纵坐标从2开始)，但右边(1013,11014)、(1014，1015)……排下去最多到第2022列，肯定会出现缺口

isengrin · 发表于 2024-7-20 22:15

ryanghj 发表于 2024-7-20 21:43
3次

这个问题和二分法无关，因为你知道某行坏人所在的列位置后是无法一步到达下一行该列的，需要尝试找到 ...

走到尽头的方法是，假设两次分别探得a行i列和b行j列有坏人，其中a<b，那么就从第一行j列开始走到a+1行，然后从a+1行i列开始走到结尾（也可以走到a-1行，b-1行，都不影响）

（a+1，j+1）可能是坏人哦（假设i>j）

秋月孝三 · 发表于 2024-7-20 22:17

本帖最后由秋月孝三于 2024-7-20 23:01 编辑

3次。花一次机会找到第二行的坏人然后用剩下k次机会绕到他下面，易得k=2(包括坏人刚好在边缘的情况。最坏情况是探出一条阶梯)

Hydro · 发表于 2024-7-20 22:17

本帖最后由 Hydro 于 2024-7-20 22:28 编辑

格子无非两种状态，一是之前已经确认此列有坏人的，二是还没确认的
憨豆的最佳策略可能比较复杂（吗？），但是他问的是保证一定能通过的尝试数...即最差情况需要多少次尝试
无论憨豆怎么做，确认此列有坏人需要尝试1，而撞上去把坏人撞出来也需要尝试1
那最差情况不就是把坏人全撞出来吗，2083列2022个坏人，撞到最后（2021列已确认，62列未确认，已发现坏人2021，剩余坏人1）也还有62选1撞到坏人的可能性啊，这给的条件能排除什么了？
那不就是2023全撞出来吗
啊？

--------------------
哦可以横着走批量测，打扰了

--------------------
....嗯？能横着走影响了什么吗，每行的坏人可能/不可能出现的位置不是只与此列之前有没有出现坏人有关吗
上一行批量测的方格又不会影响下一行，算最短路径之类的可能受到影响，但这个抽象出来不需要保留位置信息吧
2083个盒子，其中2022个里有鬼，我看不到有什么能快速确认出哪2022个盒子里有鬼的方法？

ryanghj · 发表于 2024-7-20 22:18

isengrin 发表于 2024-7-20 22:15
走到尽头的方法是，假设两次分别探得a行i列和b行j列有坏人，其中aj）

我补充了b=a+1时的情况，另外不是j+1，是沿着j走

ryanghj · 发表于 2024-7-20 22:24

本帖最后由 ryanghj 于 2024-7-20 22:25 编辑

在最坏情况下，走了两步遇到了两个坏人，第三步的走法：

一般情况：

特殊情况（第二步其实走除了两个坏人列之外的任意列都行，目的是达到下面的行）：

isengrin · 发表于 2024-7-20 22:37

ryanghj 发表于 2024-7-20 22:18
我补充了b=a+1时的情况，另外不是j+1，是沿着j走

那么就从第一行j列开始走到a+1行，然后从a+1行i列开始走到结尾

你必须在a+1行横着走，但你不能保证从(a+1,j)走到（a+1，i）的路上遇不到坏人

Hydro · 发表于 2024-7-20 22:38

想象一个罐子，里面有2083张纸条，其中2022张上显示"-1s"
任何一个下行（e.g. 第2行->第3行）的操作都是从罐子里抽出一张纸条
问在你抽完2022次（走完2024-2行）后，你至少需要多少life才能保证存活

如果这个模型没有忽略原题中的什么条件（它与原题等价），就应该是2023？吗？

isengrin · 发表于 2024-7-20 22:40

ryanghj 发表于 2024-7-20 22:24
在最坏情况下，走了两步遇到了两个坏人，第三步的走法：

一般情况：

比如这样

		自动登录	找回密码
密码			立即注册

[读书] 来考验坛友们的数学水平了（答案已公布在52楼，71楼补充了图）

本帖子中包含更多资源

评分

评分

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

ackroyd2 ackroyd2 当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2016-11-29 头像被屏蔽	发表于 2024-7-20 21:23 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报