|
我查了一下，31届预选题没有这道题。这题正好和我解的一道题类似，现解答如下： 1）我们只要讨论(a,b)=1的情况，由于机器人只会走到(a,b)的倍数的位置，所以只要先做a/(a,b)和b/(a,b)的情况，然后乘以(a,b)即可。以下都假设(a,b)=1。 2）我们证n≥a+b-1。若不然，假设n≤a+b-2。则对于集合A={0,1,2,...n}中的每个数X，机器人从0开始，当机器人到达X时，他的下一步只能是X+a或者是X-b，而两者最多只有一个属于A，因此机器人每一步都只有唯一的选择；另外X的前一步只能是X-a或者是X+b，而两者也最多只有一个属于A，因此X的前一步也是唯一的。由于A是有限集合，所以机器人的路线必然会出现无路可走或重复，由已知机器人不会无路可走。由于每一位置的前一步是唯一的，所以第一个出现重复的只能是0，假设机器人第一次在0重复时已经走了k次向前，t次后退，由于A其他元素还没有被重复，所以总的步数k+t≤n+1≤a+b-1。另外ka-tb=0，所以只能有k大于等于b,t大于等于a矛盾。 3)我们证n=a+b-1是可以的，还是设A={0,1,2,...n}，机器人从0开始，同样每一个X属于A，当机器人到达X时，他的下一步只能是X+a或者是X-b，而两者有且只有一个属于A，所以机器人每一步都只有唯一的选择，而且不会无路可走，所以必然会出现重复！同样0肯定是第一个重复的点，假设机器人第一次在0重复时已经走了k次向前，t次后退，由于A其他元素还没有被重复，所以总的步数k+t≤n+1≤a+b。另外ka-tb=0，所以只能有k≥b,t≥a，所以只能等号都成立，所以机器人第一次重复的时候，已经走遍了A的所有元素，当然肯定到过n=a+b-1。[em01] 4）(a,b)不等于1时，答案是(a,b)[a/(a,b)+b/(a,b)-1]=a+b-(a,b)。
[此贴子已经被作者于2006-12-20 13:00:01编辑过]
| 
发表于 2006-8-12 19:43:00
楼主