这个题目是英国竞赛题,答案理解不了,求教大家!
4.首先证明:要想得到正确的密码,亚历克斯至少需要13次尝试.
假设前六次尝试返回的均为失败.则每个数位至少剩余4种可能,总共64种可能.无论亚历克斯第七次尝试什么,余下的都有超过32种可能
具体情况如下:
(1)三个数位上正确的数字均被之前的尝试排除掉了,余下的64种组合将均会返回失败;
(2)三个数位中恰有两个正确的数字被之前的尝试排除了,则余下的尝试中有48种组合会返回失败;
(3)三个数位中恰有一一个正确的数字被之前的尝试排除了,则余下的尝试中有36种组合会返回失败;
(4)三个数位中正确的数字均没有被之前的尝试排除,则余下的尝试中有37种组合会返回接近.
若总共只有12次尝试的机会,则在余下的五次尝试之中,最多只能验证32种可能.故至少需要13次尝试. |