小小和小正在玩卡片游戏,小小是防御者,小是攻击者,游戏的规则如下。
有一些卡片,按5×5的方式摆放,每张卡片的正面,写着一个数组,数组的表达形式为(a,b),a表示这张卡片是a类颜色,b为零或者为一,表示这张卡片是否被传染(题目后续有讲道)。
同样为a类颜色的卡片,一定是相通并且相邻摆放的,也可以理解为在五乘五的矩阵中,从一张a类颜色的卡片,不用通过不是a类颜色的卡片,可以到达任意一张a类颜色的卡片。
例如下图,5×5矩阵中的数组中的a
1 1 1 2 2
1 2 1 2 2
1 2 2 2 2
1 1 1 1 2
1 2 2 2 2
1类颜色的卡片都是相邻并且相通的,2类的也是
在游戏还没有开始时,小小会从这25张卡片中随机选择一张卡片,把它的b设为一(代表已经被感染了),而其余的卡片b是零,代表还未被感染,卡片的感染机制如下,如果若干张卡片被感染,小小会随机从相邻这若干张被感染的卡片并且和这若干张卡片是同一类型颜色的卡片中选出一张卡片,进行感染,将这张卡b的数值调整为一,并且小并不知道小小调整了哪张卡片的数值,如果小小,把同一类型颜色的所有卡片都感染了(例如,上面例图中颜色为1类型的卡片都感染了,或者颜色为2类型的卡片都感染了),小小就会输了这场比赛。
由于比赛对小来说过于不公平,所以他有自己的应对办法。
每一次游戏循环,小有机会从中随机选取一张卡片,将他的值b改为0,阻止小小感染。
开始游戏是,已知a的取值为1至5,每类颜色的卡片有5张,按如上规则随即摆放(小与小小都不知道),有A,B,C,D,E,F六位先生,你可以随机挑选n位先生并询问5*5矩阵中随机一张卡的颜色种类,随后小小选一张卡片感染,两人开始博弈。
当小选完n位先生后,小小只能从剩下几位先生中获取信息,但作为高质量好朋友小想尽可能多的让小小多获取信息并保证不输(不一定要赢,只求不输),问n的最小值为几?
珠宝店失窃事件
2014年7月14日,X市的警局一大早就接到报案,Z珠宝店的大量名贵首饰不翼而飞了。警察根据珠宝店的监控录像回放发现,窃贼是昨晚22:30左右进入珠宝店行窃的。由于窃贼是蒙面的,警察只能大致推断窃贼身高是180CM左右,并且断定是男性。
通过大量搜集嫌犯的资料,警察最终找出四个符合条件的嫌犯。
警察开始审问四个嫌疑犯:“昨晚10点半左右,你们都在做什么?”
嫌犯A:“昨天整晚我都在和女朋友约会,半夜12点以后我才回来,我的女朋友可以为我证明。”
嫌犯B:“昨晚我用心经营的饭店突然着火了,那时候正好是10点左右。我明明记得我离开的时候,电闸也拉了,明火也熄了,不可能着火!我想肯定是有人故意纵火!然后我就去那看看到底是谁放的火!竟然让这个兔崽子跑了!MD别让我抓到他,我非打死这个鳖孙!”
嫌犯C:“昨晚我没出门,一直在家里看世界杯比赛,看到快天亮才睡觉。儿子是陪我一起看的,他可以为我证明!真是气死我了!决赛巴西竟然输给德国了!我所有赌注都压在巴西身上了,这下全TMD打水漂了!”
嫌犯D:“昨晚10点以后,我就和老婆关灯睡觉了,所以后来发生了什么事我也不知道。我的老婆可以为我证明。”
听完四个嫌犯的供词,警察开始思考:“A有不在场证明。B说的也没错,昨晚确实有个地方着火了,而且火势很大,23:00左右才扑灭。C说一直在家里看球,也有人给他证明。D在睡觉,似乎也合乎情理,并且也有人给他证明。这样看来,只有B没有人证明……”
“原来如此,有人在说谎!”警察突然茅塞顿开,指着一个人喊道:“别装了,窃贼就是你!”
你知道窃贼是谁吗?