[問題]遊戲問題2

[問題]遊戲問題2

tangpakchiu 於 星期四 七月 26, 2007 8:17 am


  Let n >2 be an integer.On a blackboard, 1,2,3.....,n are written. James and jack take turns to cross out one integer at a time,with james going first,until only two integers remain.James wins if the two remaining integers are relatively prime,and Jack wins otherwise. The integer is said to be 'good' if James has a winning strategy and 'bad' if jack has a winning strategy. For each n>2,determine whether it is 'good' or 'bad'.

tangpakchiu
大 師
大 師
 
文章: 364
註冊時間: 2006-01-23

Re: [問題]遊戲問題2

G@ry 於 星期四 七月 26, 2007 11:36 am


tangpakchiu 寫到:
  Let n >2 be an integer.On a blackboard, 1,2,3.....,n are written. James and jack take turns to cross out one integer at a time,with james going first,until only two integers remain.James wins if the two remaining integers are relatively prime,and Jack wins otherwise. The integer is said to be 'good' if James has a winning strategy and 'bad' if jack has a winning strategy. For each n>2,determine whether it is 'good' or 'bad'.

The integer must be 'good' for all odd n. And must be 'bad' for all even n.

For an odd n:
As it is know that all 2 continous integer are relatively prime. So the strategy is to:
1. Corss out integer 1. [All integers are not relatively prime with integer 1.]
2. Put integers into a set of 2 -- {2k, 2k+1}. And when Jack cross any integer, cross out the remaining one of same set. [So, all integers are removed set by set. At last, only one set of {2k, 2k+1} is left and they are relatively prime.]

For an even n:
Let n = 2m, there are m+1 elements in the set S: {1}U{2,4,6,...,2m} and all of them are not relatively prime. But before the last 2 integers are left,  James is only able to remove m-1 integers. So, if John doesn't remove any integers that are elements of set S (i.e. only removes odd integers which are >1), the last 2 integers left must be 2 elements inside set S. => integers left must be NOT relatively prime.
☆子 是也

G@ry
版 主
版 主
 
文章: 597
註冊時間: 2007-03-01
來自: 香港




數論