狗爺語錄

This question is taken from Mathematical Excalibur Volume 9 Number 2, with the real source coming from XVI Asian Pacific Mathematical Olympiad which took place on March 2004.

Problem 1. Determine all finite nonempty sets S of positive integers satisfying is an element of S for all i, j in S, where is the greatest common divisor of i and j.

Seems a significant word is missing from the question: …… is an element of S for all distinct i, j in S; otherwise it would degenerate into a simple solution. Here is the reason:

1. 2 must belong to S, since for any number i ∈ S, must also belong to S.
2. If any odd number a belongs to S, then pick the largest one and denote it as a. Since both a and 2 belong to S, also belongs to S, conflicting with the condition that a is the largest odd number belonging to S. Thus the conclusion is: there should be no odd integer in S.
3. If there exists any even number other than 2 that belongs to S, there must be a smallest one among them. Denote it as 2b where b is a positive integer. Then ∈ S. However, for any , one has , leading to a dilemma:
   • b+1 is odd number, violating 2^nd deduction that S must contain no odd number.
   • b+1 is even number, violating the presumption that 2b is the smallest even number in S with .

With the reasoning above, the only possible solution degenerates into . If i, j were required to be distinct, then there are many more solutions — at least all 2-element sets with x≥3 also satisfy the question, which looks like the original intention of this question.