Olympiad Maths Prep

Track / Stage 7 / 83 of 300 #1483 of 2000

Problem 1483

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.1 Find the answer

The numbers from 51 51 to 150 150 are arranged in a 10×10 10\times 10 array. Can this be done in such a way that, for any two horizontally or vertically adjacent numbers a a and b b, at least one of the equations x2\minusax\plusb\equal0 x^2 \minus{} ax \plus{} b \equal{} 0 and x2\minusbx\plusa\equal0 x^2 \minus{} bx \plus{} a \equal{} 0 has two integral roots?

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Assume the contrary: Suppose it is possible to arrange the numbers from 51 to 150 in a 10×1010 \times 10 array such that for any two horizontally or vertically adjacent numbers aa and bb, at least one of the equations x2ax+b=0x^2 - ax + b = 0 or x2bx+a=0x^2 - bx + a = 0 has two integral roots.

2. Consider the number 149:
- The cell containing 149 must have at least two adjacent cells. Let aa be one of the numbers in these adjacent cells.
- For the equation x2149x+a=0x^2 - 149x + a = 0 to have two integral roots, the discriminant must be a perfect square:
14924a=d2 149^2 - 4a = d^2
where dd is an integer.

3. **Solve for aa**:
- Rearrange the equation:
1492d2=4a 149^2 - d^2 = 4a
(149d)(149+d)=4a (149 - d)(149 + d) = 4a
- Since aa must be an integer between 51 and 150, we need to find integer solutions for dd such that 4a4a is an integer in this range.

4. **Check possible values of dd**:
- The range for dd is determined by:
14924150d1492451 \sqrt{149^2 - 4 \cdot 150} \leq d \leq \sqrt{149^2 - 4 \cdot 51}
22001d21801 \sqrt{22001} \leq d \leq \sqrt{21801}
146<d<148 146 < d < 148
- The only integer value for dd in this range is d=147d = 147.

5. **Find corresponding aa**:
- Substitute d=147d = 147 into the equation:
14921472=4a 149^2 - 147^2 = 4a
(149147)(149+147)=4a (149 - 147)(149 + 147) = 4a
2296=4a 2 \cdot 296 = 4a
592=4a 592 = 4a
a=148 a = 148

6. Consider the number 148:
- The cell containing 148 must also have at least two adjacent cells. Let bb be one of the numbers in these adjacent cells.
- For the equation x2148x+b=0x^2 - 148x + b = 0 to have two integral roots, the discriminant must be a perfect square:
14824b=d2 148^2 - 4b = d^2
where dd is an integer.

7. **Solve for bb**:
- Rearrange the equation:
1482d2=4b 148^2 - d^2 = 4b
(148d)(148+d)=4b (148 - d)(148 + d) = 4b
- Since bb must be an integer between 51 and 150, we need to find integer solutions for dd such that 4b4b is an integer in this range.

8. **Check possible values of dd**:
- The range for dd is determined by:
14824150d1482451 \sqrt{148^2 - 4 \cdot 150} \leq d \leq \sqrt{148^2 - 4 \cdot 51}
21704d21504 \sqrt{21704} \leq d \leq \sqrt{21504}
146<d<148 146 < d < 148
- The only integer value for dd in this range is d=147d = 147.

9. **Find corresponding bb**:
- Substitute d=147d = 147 into the equation:
14821472=4b 148^2 - 147^2 = 4b
(148147)(148+147)=4b (148 - 147)(148 + 147) = 4b
1295=4b 1 \cdot 295 = 4b
295=4b 295 = 4b
b=73.75 b = 73.75
- Since bb is not an integer, this contradicts our assumption.

10. Conclusion: Since we have reached a contradiction, it is not possible to arrange the numbers from 51 to 150 in a 10×1010 \times 10 array such that for any two horizontally or vertically adjacent numbers aa and bb, at least one of the equations x2ax+b=0x^2 - ax + b = 0 or x2bx+a=0x^2 - bx + a = 0 has two integral roots.

\blacksquare

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