Question

【題目】若整數(shù)、既不互素，又不存在整除關(guān)系，則稱、為一個(gè)“聯(lián)盟”數(shù)對(duì).設(shè)為集的元子集，且中任兩數(shù)均為聯(lián)盟數(shù)對(duì).求的最大值

Answer 1

【答案】504

【解析】

稱這種子集為“聯(lián)盟子集”.

首先構(gòu)造一個(gè)聯(lián)盟子集，其中具504有個(gè)元素.為此，取

.

接下來(lái)證明，504就是的最大值。

設(shè)為元素個(gè)數(shù)最多的一個(gè)聯(lián)盟子集.

若為集合中的最小數(shù)，顯然，.若，則，即，

顯然，，（這是因?yàn)?/span>與有整除關(guān)系）.

考慮在集合中用，替代，其他元素不變，成為子集，則仍為聯(lián)盟子集，這是因?yàn)閷?duì)于集合中異于的任一元素，由與，不互素，故與也不互素；再說(shuō)明與沒(méi)有整除關(guān)系，這是因?yàn)?/span>，所以，.

又若，設(shè)，(顯然，否則，、有整除關(guān)系），則.于是，，這與的最小性矛盾.

故仍為聯(lián)盟子集，且仍為元集.

重復(fù)以上作法，直至子集中的元素均大于1007為止。

于是，得到元聯(lián)盟子集

，

即.

因?yàn)槿蝺蓚�(gè)相鄰整數(shù)必互素，所以，在這1007個(gè)連續(xù)正整數(shù)中至多能取到504個(gè)互不相鄰的數(shù)，即.

又據(jù)前面所述的構(gòu)造，知的最大值即為504.