๐Ÿงฎ Brain Teaser

A Polynomial That Takes the Value 1 Too Often

Let p(x)p(x) be a polynomial with integer coefficients. Suppose that p(a1)=p(a2)=p(a3)=p(a4)=1p(a_1) = p(a_2) = p(a_3) = p(a_4) = 1 for four distinct integers a1,a2,a3,a4a_1, a_2, a_3, a_4. Prove that there is no integer bb with p(b)=โˆ’1p(b) = -1.

polynomialsinteger coefficientsdivisibilitypigeonholefactoring

Answer: A Polynomial That Takes the Value 1 Too Often

Key Idea / Intuition

If a polynomial takes the value 11 at four distinct integer points, we can factor out those roots explicitly. The leftover polynomial has integer coefficients, so when we evaluate at any integer bb, the product of four distinct integer factors must multiply to โˆ’2-2. But a product of four distinct integers cannot equal โˆ’2-2, since โˆ’2-2 cannot be written as a product of four distinct integers โ€” there simply aren't enough small integers to make this work.


Formal Proof / Solution

Setup. Since p(ai)=1p(a_i) = 1 for i=1,2,3,4i = 1, 2, 3, 4, the polynomial q(x)=p(x)โˆ’1q(x) = p(x) - 1 has roots at a1,a2,a3,a4a_1, a_2, a_3, a_4. Therefore:

q(x)=p(x)โˆ’1=(xโˆ’a1)(xโˆ’a2)(xโˆ’a3)(xโˆ’a4)โ‹…r(x)q(x) = p(x) - 1 = (x - a_1)(x - a_2)(x - a_3)(x - a_4) \cdot r(x)

for some polynomial r(x)r(x) with integer coefficients (since pp has integer coefficients).

Evaluate at bb. Suppose for contradiction that p(b)=โˆ’1p(b) = -1 for some integer bb. Then q(b)=โˆ’2q(b) = -2, so:

(bโˆ’a1)(bโˆ’a2)(bโˆ’a3)(bโˆ’a4)โ‹…r(b)=โˆ’2.(b - a_1)(b - a_2)(b - a_3)(b - a_4) \cdot r(b) = -2.

Since all quantities here are integers, we need:

(bโˆ’a1)(bโˆ’a2)(bโˆ’a3)(bโˆ’a4)โˆฃโˆ’2.(b - a_1)(b - a_2)(b - a_3)(b - a_4) \mid -2.

Key observation. The four values bโˆ’a1,โ€‰bโˆ’a2,โ€‰bโˆ’a3,โ€‰bโˆ’a4b - a_1,\, b - a_2,\, b - a_3,\, b - a_4 are four distinct integers (since a1,a2,a3,a4a_1, a_2, a_3, a_4 are distinct). Their product must divide โˆ’2-2, so their product is one of ยฑ1,ยฑ2\pm 1, \pm 2.

But a product of four distinct integers must have absolute value at least โˆฃโˆ’3โ‹…โˆ’1โ‹…1โ‹…2โˆฃ=6|{-3} \cdot {-1} \cdot 1 \cdot 2| = 6 if we try to make them small โ€” or more carefully: four distinct integers include at least two with โˆฃnโˆฃโ‰ฅ1|n| \geq 1 and โˆฃnโˆฃโ‰ฅ2|n| \geq 2, and in fact the minimum absolute product of four distinct integers occurs at {โˆ’1,0,1,2}\{-1, 0, 1, 2\} (or similar), giving product 00. But the product cannot be 00 (that would give p(b)=1p(b) = 1, not โˆ’1-1).

Let's be precise. Suppose the four distinct integers c1<c2<c3<c4c_1 < c_2 < c_3 < c_4 satisfy โˆฃc1c2c3c4โˆฃโ‰ค2|c_1 c_2 c_3 c_4| \leq 2. Since they are distinct, at least two of them are nonzero. If all four are nonzero, then โˆฃc1c2c3c4โˆฃโ‰ฅ1โ‹…1โ‹…2โ‹…3=6>2|c_1 c_2 c_3 c_4| \geq 1 \cdot 1 \cdot 2 \cdot 3 = 6 > 2, contradiction. So at least one is zero, but then the product is 00, not ยฑ2\pm 2.

Wait โ€” if one is zero: then product = 0 โ‰  ยฑ2. If none is zero: four distinct nonzero integers have โˆฃ|productโˆฃโ‰ฅ1โ‹…2โ‹…3โ‹…โ€ฆ| \geq 1 \cdot 2 \cdot 3 \cdot \ldots? No, they can be negative. The smallest absolute product of four distinct nonzero integers is achieved by {โˆ’2,โˆ’1,1,2}\{-2, -1, 1, 2\}:

(โˆ’2)(โˆ’1)(1)(2)=4>2.(-2)(-1)(1)(2) = 4 > 2.

Any other set of four distinct nonzero integers has an even larger absolute product. So in every case, either the product is 00 (impossible, since we need ยฑ2\pm 2), or the absolute value is at least 4>24 > 2 (impossible).

Conclusion. In all cases, the product (bโˆ’a1)(bโˆ’a2)(bโˆ’a3)(bโˆ’a4)(b-a_1)(b-a_2)(b-a_3)(b-a_4) cannot equal ยฑ1\pm 1 or ยฑ2\pm 2, so the equation cannot hold. This contradicts the assumption that p(b)=โˆ’1p(b) = -1, completing the proof. โ– \blacksquare


Summary of the key bound:

  • Four distinct integers, all zero โ†’ product 0 โœ—
  • One zero among them โ†’ product 0 โœ—
  • All nonzero, four distinct integers โ†’ โˆฃproductโˆฃโ‰ฅ4|\text{product}| \geq 4 โœ—

None of these can equal ยฑ2\pm 2, so p(b)=โˆ’1p(b) = -1 is impossible.

Source: Putnam Mathematical Competition folklore / 1988 Putnam B-2

Type: PutnamSource: Putnam Mathematical Competition folklore / 1988 Putnam B-2Edit on GitHub โ†—