Determine if there exist pairwise distinct positive integers $a_1,a_2,\ldots,a_{101}$, $b_1$, $b_2$, \ldots, $b_{101}$ satisfying the following property: for each non-empty subset $S$ of $\{1,2,\ldots,101\}$ the sum $\sum\limits_{i\in S}a_i$ divides $\left( 100!+\sum\limits_{i\in S}b_i \right)$.
Problem
Source: IV Caucasus Mathematic Olympiad
Tags: number theory
07.04.2019 23:33
See also https://artofproblemsolving.com/community/c6h1817803_divisible_condition_for_every_subset
17.04.2019 17:00
Yes there are such integers. We first construct the sequence $a_1,a_2,...,a_{101}$ such that it satisfies the following condition : There are no two differnt sets $S_1,S_2$ and prime $p\ge101$ such that $ p|\sum\limits_{i\in S_1}a_i$ , $\sum\limits_{i\in S_2}a_i$. Impose $a_i=1(mod (100!)!)$ and no sum $\sum\limits_{i\in S}a_i$ is divisible by $p,(101\le p\le(100!)!)$ except for $101|a_1+a_2+...+a_{101}$. Now we construct $a_i$ inductively . Suppose $a_1,...,a_k$ satisfies the condition . We need to choose $a_{k+1} $ such that no prime $p>(100!)!$ divides two different sums at least one of which contains $a_{k+1}$. In this case $p$ would divide some sum of the form $ p|\sum\limits_{i\in S_1}a_i-\sum\limits_{i\in S_2}a_i$. For $S_1,S_2 \in \{ 1,2,...,k\}$(call $p$ a bad prime). However the set of bad primes $p$ is finite and due to the large number of possible residues $a_{k+1}(mod p)$ we can choose by CRT $a_{k+1}$ such that no sum containing $a_{k+1}$ is divisible by a bad prime. Thus we can choose by CRT a suitable $a_{k+1}$ and then induct. After we have constructed $a_1,a_2,...,a_{101} $ we can construct $b_1,...,b_{101}$ using CRT as every $p>100$ divides at most one sum $\sum\limits_{i\in S_1}a_i$ and primes $p<100$ are no problem (assume that $100!|b_i$).