Avoiding a five-term zero sum mod 47 with a dilated residue window

mothwingcloak·Jun 11, 2025(edited)

There are only 46 nonzero residue classes, so choosing one class gives too few elements. I think we need a large collection of classes that forbids the alternating five-term expression. Problem: Let

X

be a set of

10000

integers, none of them is divisible by

47

. Prove that there exists a

2007

-element subset

Y

X

such that

a-b+c-d+e

is not divisible by

47

for any

a, b, c, d, e \in Y

. Source: IMO 2007 Shortlist · MNET-06PQ

Open MNET-06PQ in the question bank →

5 replies

savefile_07·Jun 11, 2025(edited)

Use the ten residues represented by

J=\{-9,-7,\dots,-1,1,\dots,9\}

. Any

a-b+c-d+e

from these representatives is odd and between -45 and 45, so it cannot be divisible by 47.

mothwingcloak·Jun 13, 2025(edited)

But X could avoid most of those ten classes. Is there a reason that particular window captures enough elements?

savefile_07·Jun 13, 2025(edited)

Vary a nonzero multiplier

t

modulo 47. For each fixed

x\in X

, the residue

tx

runs through all 46 nonzero classes, so exactly ten multipliers send it into J.

crimsonFlask·Jun 13, 2025

The total number of incidences is

10\cdot10000

. Averaging over 46 multipliers gives a good subset with more than 2173 elements. Take any 2007 of them.

mothwingcloak·Jun 13, 2025

And if the expression vanished before multiplying by t, it would vanish after multiplying too, contradicting the property of J. Repetitions among a,b,c,d,e don't break the oddness argument.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…