Question

请教一道小学数学（奥数）题，求解题思路和答案，谢谢！

题目：小明把15把钥匙弄混了，问：小明需要试多少次才能准确无误的把这15把钥匙全部配到15把锁上？

题目看似简单，但却是道奥数题，实在算不出来。求解题思路和答案，谢谢！

Answer 1

题目问的应该是最多试多少次才能准确无误的把这15把钥匙全部配到15把锁上，即不考虑第一次就全部试对了这样的极端情况。

那么很简单对于第一把锁来说最多试14次肯定能试对，因为试了14次之后剩下的那把肯定是正确的钥匙，这时剩下14把钥匙，14把锁，同理第二把锁最多试13次也能试对。。。。一直到最后一把锁，因为只剩下一把钥匙，所以不需要再试，所以
最多需要试14+13+。。。。。+3+2=（14+2）*13/2=104次无误的把这15把钥匙全部配到15把锁上。

Answer 2

第一把钥匙最多试14次，如果前面14次都不对，第15次不用试肯定就是第15把锁
以此类推，13+12+。。。
同理最后一把锁也不用试，
14+13+12+...+2= (1+14)X14/2-1=104

Answer 3

　有15把钥匙和15把锁，并且每把钥匙只能开一把锁，则最多要试（　）次才能配好全部的钥匙和锁。

　　分析与解答
　　根据题中条件，15把钥匙与15把锁是一一对应的，即一把钥匙只能开一把锁。若要使每把钥匙都能打开对应的锁，在解答时，应从“最不凑巧”的方面出发去思考。
　　例如，假设2把钥匙各对应一把锁，则最多只需试开1次；3把钥匙各对应一把锁时，则最多要试开2＋1＝3（次）；……，依此类推，故本题可采用如下解法：
　　先用一把钥匙去试开15把锁，最多要试14次（最不凑巧）；再在剩下的钥匙中任选1把去试开其余的14把锁，最多要试13次；……，最后在仅剩的2把钥匙中任选一把去试开其余的2把锁，最多要试1次。所以15把钥匙和15把锁都配好，最多要试：
　　　　　14＋13＋…＋2＋1＝105（次）
　　推广：有n把钥匙和n把锁，每把钥匙只能开一把锁，则要配好所有的钥匙和锁，最多要试开：
　　　　　(n－1)＋(n-2)＋…＋2＋1＝n(n-1)÷2(次)

Answer 4

有两种策略，一种保守策略，保证N次之后肯定能全部配到：
最差情况：15+14+13+12+....+1=120次，即拿出一把钥匙挨个去尝试，每次都是悲催的最后一个找到；
另一种是概率算法，计算期望的次数
第一把钥匙拿出来的时候，
1次猜对的概率1/15, 尝试次数1，总次数1/15*1;
2次猜对的概率14/15*1/14=1/15(第一次猜不对，外加第二次猜对)，总尝试次数2，总次数1/15*2;
n次猜对的概率1/15,尝试次数n，总次数1/15*n;
所以
第一把钥匙尝试次数的期望值为1/15*(1+2+3+...+15)=8;
第二把钥匙尝试次数的期望值为1/14*(1+2+3+...+14)=7.5;
...
第十四把钥匙尝试次数的期望值为1/2*(1+2)=1.5;
第十五把钥匙尝试次数的期望值为1/1*(1)=1;（只剩下一把，错不了了- -）
所以总的次数（8+....+1）=(8+1)*15/2=67.5(这个只是一个期望值吧...所以会有小数)

Answer 5

结果为O(n^2);最大的运算时间当然是从1加到15，也就是1到n

Answer 6

15+14+13+....+3+2=(15+1)x15/2-1=119
原理，第一把钥匙要试15次。第二把钥匙要试14次，以此类推，最后一把就不用试了因为只剩了一个了，所以是2+3+4一直加到15.从1+到n的公式是1+2+3+。。。+n=（1+n）*n/2