Maths Olympiad Prep

Library / /98 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

Determine if there exist pairwise distinct positive integers a1,a2,,a101a_1,a_2,\ldots,a_{101}, b1b_1, b2b_2, \ldots, b101b_{101} satisfying the following property: for each non-empty subset SS of {1,2,,101}\{1,2,\ldots,101\} the sum iSai\sum\limits_{i\in S}a_i divides (100!+iSbi)\left( 100!+\sum\limits_{i\in S}b_i \right).

Solution

1. **Constructing the sequence a1,a2,,a101a_1, a_2, \ldots, a_{101}:**
- We need to ensure that for any non-empty subset SS of {1,2,,101}\{1, 2, \ldots, 101\}, the sum iSai\sum_{i \in S} a_i divides 100!+iSbi100! + \sum_{i \in S} b_i.
- We impose the condition ai1(mod(100!)!)a_i \equiv 1 \pmod{(100!)!} for all ii. This ensures that aia_i are congruent to 1 modulo (100!)!(100!)!.

2. **Ensuring distinct sums modulo primes p101p \geq 101:**
- We need to ensure that no two different sets S1S_1 and S2S_2 have sums iS1ai\sum_{i \in S_1} a_i and iS2ai\sum_{i \in S_2} a_i that are divisible by the same prime p101p \geq 101.
- This can be achieved by choosing aia_i such that no sum iSai\sum_{i \in S} a_i is divisible by any prime pp in the range 101p(100!)!101 \leq p \leq (100!)!, except for the sum of all aia_i, which is divisible by 101.

3. **Inductive construction of aia_i:**
- Suppose a1,a2,,aka_1, a_2, \ldots, a_k have been chosen to satisfy the condition.
- We need to choose ak+1a_{k+1} such that no prime p>(100!)!p > (100!)! divides two different sums, at least one of which contains ak+1a_{k+1}.
- If pp divides iS1aiiS2ai\sum_{i \in S_1} a_i - \sum_{i \in S_2} a_i for some S1,S2{1,2,,k}S_1, S_2 \subseteq \{1, 2, \ldots, k\}, we call pp a bad prime.
- The set of bad primes is finite, and by the Chinese Remainder Theorem (CRT), we can choose ak+1a_{k+1} such that no sum containing ak+1a_{k+1} is divisible by a bad prime.

4. **Using CRT to choose ak+1a_{k+1}:**
- By the CRT, we can find ak+1a_{k+1} such that it satisfies the required conditions modulo all bad primes.
- This process can be repeated inductively to construct a1,a2,,a101a_1, a_2, \ldots, a_{101}.

5. **Constructing b1,b2,,b101b_1, b_2, \ldots, b_{101}:**
- After constructing a1,a2,,a101a_1, a_2, \ldots, a_{101}, we can construct b1,b2,,b101b_1, b_2, \ldots, b_{101} using the CRT.
- We ensure that 100!bi100! \mid b_i for all ii, and for each prime p>100p > 100, pp divides at most one sum iSai\sum_{i \in S} a_i.

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.