Maths Olympiad Prep

Library / /52 of 520

Number theory Difficulty 6.4 National olympiad Find the answer

SN S\subset\mathbb N is called a square set, iff for each x,yS x,y\in S, xy 1\text{xy 1} is square of an integer.
a) Is S S finite?
b) Find maximum number of elements of S S.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let's address the problem step by step.

### Part (a): Is S S finite?

1. **Assume S S is infinite:**
Suppose S S is an infinite set. This means there are infinitely many elements x,yS x, y \in S such that xy+1 xy + 1 is a perfect square.

2. **Consider two elements a,bS a, b \in S :**
Let a,bS a, b \in S . Then there exists an integer m m such that ab+1=m2 ab + 1 = m^2 . Rearranging, we get:
ab=m21 ab = m^2 - 1

3. Polynomial construction:
Consider the polynomial P(x)=(ax+1)(bx+1) P(x) = (ax + 1)(bx + 1) . Expanding this, we get:
P(x)=abx2+(a+b)x+1 P(x) = abx^2 + (a + b)x + 1
Since ab=m21 ab = m^2 - 1 , we can rewrite P(x) P(x) as:
P(x)=(m21)x2+(a+b)x+1 P(x) = (m^2 - 1)x^2 + (a + b)x + 1

4. Square of an integer:
For xS x \in S , P(x) P(x) must be a perfect square. Let P(x)=k2 P(x) = k^2 for some integer k k . Then:
(m21)x2+(a+b)x+1=k2 (m^2 - 1)x^2 + (a + b)x + 1 = k^2

5. Contradiction:
If S S were infinite, we would have infinitely many such polynomials P(x) P(x) that are perfect squares. However, this leads to a contradiction because the polynomial P(x) P(x) cannot be a perfect square for infinitely many x x unless it is a constant polynomial, which it is not.

Therefore, S S cannot be infinite.

### Part (b): Find the maximum number of elements of S S .

1. Smallest elements:
Let's consider the smallest elements of S S . Suppose S={a,b,c} S = \{a, b, c\} . Then:
ab+1=m2,bc+1=n2,ca+1=p2 ab + 1 = m^2, \quad bc + 1 = n^2, \quad ca + 1 = p^2

2. Check small values:
Let's check small values to find a set S S with the maximum number of elements. We start with a=1 a = 1 :
1b+1=m2    b=m21 1 \cdot b + 1 = m^2 \implies b = m^2 - 1
For b=3 b = 3 :
13+1=4=22    b=3 1 \cdot 3 + 1 = 4 = 2^2 \implies b = 3
For c=8 c = 8 :
38+1=25=52    c=8 3 \cdot 8 + 1 = 25 = 5^2 \implies c = 8

3. Verify the set:
Verify if {1,3,8} \{1, 3, 8\} is a square set:
13+1=4=22 1 \cdot 3 + 1 = 4 = 2^2
38+1=25=52 3 \cdot 8 + 1 = 25 = 5^2
81+1=9=32 8 \cdot 1 + 1 = 9 = 3^2
All conditions are satisfied.

4. Maximum number of elements:
We have found that {1,3,8} \{1, 3, 8\} is a square set with 3 elements. To check if there can be more elements, we would need to find another element d d such that:
1d+1,3d+1,8d+1 1 \cdot d + 1, \quad 3 \cdot d + 1, \quad 8 \cdot d + 1
are all perfect squares. This is not possible as it leads to contradictions.

Thus, the maximum number of elements in S S is 3.

The final answer is 3 \boxed{3}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.