Let m1,m2,...,m2013>1 be 2013 pairwise relatively prime positive integers and A1,A2,...,A2013 be 2013 (possibly empty) sets with Ai⊆{1,2,...,mi−1} for i=1,2,...,2013. Prove that there is a positive integer N such that N≤(2|A1|+1)(2|A2|+1)⋯(2|A2013|+1) and for each i=1,2,...,2013, there does not exist a∈Ai such that mi divides N−a. Proposed by Victor Wang
Problem
Source: ELMO 2013/3, by Victor Wang; also Shortlist N5
Tags: blogs, modular arithmetic, number theory, relatively prime, number theory unsolved, Chinese Remainder Theorem, Elmo
20.06.2013 01:06
First we note that all these numbers are primes
20.06.2013 01:30
rahman wrote: First we note that all these numbers are primes then W,L,O,G we asume that m2013>m2012>...>m1 note that |Ai|=mi−1 Already in your first three statements there are two errors...
23.07.2013 05:05
This is a nice problem, and it's been a while, so I guess:
22.08.2013 09:01
This ended up being slightly easier than I expected. That may be due to the fact though that I just solved this China TST prob (on my blog) (here's the actual problem page) a few days ago. It would be interesting if Victor could mention how he thought up this problem; I would be somewhat surprised if it wasn't from that problem. Anyways, here's the solution. Work \pmod{P}, where P = m_1m_2\cdots m_n. (n = 2013) Denote the set S_i = \{0, 1, 2, \cdots , m_i-1\}. So let t_i be the solution for x to the set of congruences x \equiv 0 \pmod{m_j} for j \not = i and x \equiv 1 \pmod{m_i}. Now the "Lagrange Interpolation CRT" is to note that the solution for x to the congruence system x \equiv x_i \pmod{m_i} is actually just \sum_{i=1}^n{x_it_i}. Now we construct sets B_i \pmod {m_i}, so that the set \{B_i- B_i\} \subset S_i/A_i (the set of all differences of elements in B_i), and \vert{B_i}\vert \ge \frac{m_i}{2\vert{A_i}\vert +1}. This is equivalent to B_i, A_i being disjoint. The construction is simple. Assume that the best value of \vert{B_i}\vert that we can achieve is less than \frac{m_i}{2\vert{A_i}\vert +1}. Now we consider whether we can add another element. Note that at most 2\vert{A_i}\vert \cdot \vert {B_i}\vert +\vert {B_i} \vert < (2\vert{A_i}\vert+1) \cdot \frac{m_i}{2\vert{A_i}\vert +1} = m_i elements are not allowed to be picked. So we can pick some element to add to our set. Now consider the set S of all the (distinct) numbers \pmod{P} \sum_{i=1}^n{b_it_i}, where b_i \in B_i for all i. Since we have \frac{m_1m_2\cdots m_n}{\left( 2\left\lvert A_1\right\rvert+1\right)\left( 2\left\lvert A_2\right\rvert+1\right)\cdots\left( 2\left\lvert A_{n}\right\rvert+1\right)} in our set S, two differ by at most {\left( 2\left\lvert A_1\right\rvert+1\right)\left( 2\left\lvert A_2\right\rvert+1\right)\cdots\left( 2\left\lvert A_{n}\right\rvert+1\right)}, so if we can finish by taking their difference.
22.08.2013 09:47
mathocean97 wrote: It would be interesting if Victor could mention how he thought up this problem; I would be somewhat surprised if it wasn't from that problem. I roughly used the |A_i| = 2 case as a lemma for the following problem: Quote: Given c>0, prove that n^2+1 infinitely often has all prime divisors at least c\log{n}. I think I wrote more about this in the official solutions (in some of the comments), but I was indeed influenced at least a bit by that China TST problem---otherwise I probably wouldn't have forgotten about Solutions 2 and 3 the first time around.
16.08.2018 06:16
Here is a solution for the bound (|A_1| + 1) \cdots (|A_{2013}| + 1). The idea is the same as one in a solution in PftB. Quote: Let m_1, \dots, m_{2013} > 1 be 2013 pairwise relatively prime positive integers and A_1, \dots, A_{2013} be 2013 sets with A_i \subseteq \{1, \dots, m_i-1\} for all i. Prove that there is a positive integer N such that N \le (|A_1| + 1) \cdots (|A_{2013}| + 1)and for each i, there does not exist a \in A_i such that m_i divides N-a. For convenience define s_k = |A_k|. For each n, define x_n = \prod_{k = 1}^{2013} \prod_{a \in A_k} (1 - e^{2\pi i(n - a)/m_k}).Then x_n \neq 0 iff n is valid. When expanded, the product \prod_{a \in A_k} (1 - e^{2\pi i(n - a)/m_k}) takes the form c_0 + c_1 \varepsilon_k^n + \dots + c_{s_k} (\varepsilon_k^{s_k})^n,where c_0, \dots, c_{s_k} are constants and \varepsilon_k = e^{2\pi i/m_k}. In particular, it has s_k + 1 terms. Thus, upon expansion, x_n is the sum of s \stackrel{\text{def}}{=} (s_1 + 1) \cdots (s_{2013} + 1) terms of the form \lambda (\varepsilon_1^{f_1} \cdots \varepsilon_{2013}^{f_{2013}})^n,where \lambda is a constant and f_1, \dots, f_{2013} are nonnegative integers. This means \{x_n\} is a linear recurrence of order s. If none of 1, \dots, s are valid then x_1 = \dots = x_s = 0, which forces all x_k = 0; i.e. all k invalid. But this is a contradiction since any multiple of m_1 \cdots m_{2013} is valid.
26.06.2020 00:00
For each i, define t_i to be the unique residue modulo \displaystyle\prod_{i=1}^{2013}m_i such that t_i\equiv 1\pmod{m_i},t_i\equiv 0\pmod{m_j}\forall j\ne i. Let B_i be the largest subset of \mathbb{Z}/m_i such that (B_i-B_i)\cap A_i=\emptyset. Then, consider the numbers \sum_{i=1}^{2013}b_it_iwhere b_i\in B_i for all i. It is clear that the difference of any two of these numbers' residue modulo m_i is not in A_i for any i, hence it suffices to show that there are at least \frac{\prod_{i=1}^{2013}m_i}{\prod_{i=1}^{2013}(2|A_i|+1)}of these numbers by the Pigeonhole Principle. Thus, it suffices to show the inequality |B_i| \ge \frac{m_i}{2|A_i|+1}for any i. Now, we use a greedy algorithm to construct such a set B_i. We start with the set B_i = \{0\}. Suppose that at some point B_i has k nonzero elements, r_1,\dots , r_k. Any new element x added to B_i must satisfy the following constraints x,-x\not\in A_i, \forall 1\le j\le k, x-r_k,-x+r_k\not\in A_i.This constitutes 2k+2 constraints. Thus, any random choice of x chosen from the remaining m_i-k-1 choices will have an expected \frac{(2k+2)\cdot |A_i|}{m_i-1}violations. Thus, there will exist some working choice of x as long as |B_i|\cdot 2|A_i| = (k+1)\cdot 2|A_i| < m_i-1. Hence, we have that |B_i| \ge \frac{m_i-1}{2|A_i|} = \frac{m_i}{2|A_i|} \cdot \frac{m_i-1}{m_i}.Note that as long as \frac{2|A_i|}{2|A_i|+1} \le \frac{m_i-1}{m_i},that is, 2|A_i| \le m-1, this implies the desired result. Otherwise, we have 2|A_i| > m_i-1, so the result trivially holds because we have |B_i| \ge 1. Thus, we have shown the desired inequality and thus proven the full result.
29.10.2020 05:44
. We will prove a slightly stronger statement: if n is a positive integer, and m_1, \ldots, m_n, m are pairwise relatively prime, and A_i is a proper subset of the residues mod m_i for all 1 \le i \le n, then any arithmetic progression with common difference m and at least N = \prod_{i=1}^{n} (2|A_i|+1) terms contains a term x such that for all 1 \le i \le n, there does not exist a \in A_i such that x \equiv a \pmod{m_i}. We prove this by induction on n, base case n=1 trivial. Suppose the hypothesis holds for n-1, we will prove it for n. Case 1: There exists i such that 2|A_i| + 1 \ge m_i, WLOG i = n by reordering. Pick some mod-m_n residue y not in A_n. Because \gcd(m_n, m) = 1, the given arithmetic progression contains a subprogression where every term is congruent to y \pmod{m_n} and with at least \left\lfloor\frac{\prod_{i=1}^{n}(2|A_i|+1)}{m_n}\right\rfloor \ge \left\lfloor\frac{\prod_{i=1}^{n}(2|A_i|+1)}{2|A_n|+1}\right\rfloor = \prod_{i=1}^{n-1}(2|A_i|+1) terms. Now simply apply the induction hypothesis on m_1, \ldots, m_{n-1}, and m replaced with mm_n. Case 2: For all i, m_i > 2|A_i| + 1. Take any S \subseteq \{1, 2, \ldots, n\}, and for every i \in S, pick some y_i \in A_i. Clearly the number of terms in the arithmetic progression which are congruent to y_i mod m_i for all i \in S deviates from the quantity \frac{N}{\prod_{i \in S} m_i} by less than 1. Then using PIE, the number of terms x in the arithmetic progression satisfying x \not \equiv a \pmod{m_i} for any i, a \in A_i deviates from N - \frac{N|A_1|}{m_1} - \ldots - \frac{N|A_n|}{m_n} + \frac{N|A_1||A_2|}{m_1m_2} + \ldots - \ldots \ldots \pm \frac{N|A_1||A_2|\cdots |A_n|}{m_1m_2\cdots m_n} = N\prod_{i=1}^{n}\left(1 - \frac{|A_i|}{m_i}\right) by less than 1 + |A_1| + \ldots + |A_n| + |A_1||A_2| + \ldots + \ldots + |A_1||A_2|\cdots|A_n|= \prod_{i=1}^{n}(|A_i|+1) But we have N \prod_{i=1}^{n}\left(1 - \frac{|A_i|}{m_i}\right) > N \prod_{i=1}^{n}\left(1 - \frac{|A_i|}{2|A_i|+1}\right) = \prod_{i=1}^{n}(|A_i|+1) so the number of such terms is positive, and we are done. Remark: This solution is motivated by first attempting the bounds in case 2 and noting that they solve the problem if m_i > 2|A_i|+1 for all i. Then if 2|A_i|+1 \ge m_i for some i, noting the occurence of 2|A_i|+1 in the upper bound of N in the problem statement, one might hope that somehow we can induct downward on n. This gives rise to the generalization.
26.02.2021 04:36
Inspired by that China TST problem, we want a way to create differences in Z_{m_i}\backslash A_i that have enough elements. Claim: For each i, there exist a set with at least \frac{m_i}{2|A_i|+1} elements such that no difference between two elements of this set is in A_i. Proof. Consider a graph of the residues modulo m_i. Link an edge between x, x+t for all t\in A_i. Then note \deg(v_i)\le 2|A_i|. By Erdos', there exists an independent set of size at least \sum\limits_{i=1}^{m_i} \frac{1}{2|A_i|+1}, so done. Now, let x_i be the solution to x_i\equiv 1(\bmod\; m_i), x_i\equiv 0(\bmod\; m_j) \forall j\ne i. We consider B: \{ \sum b_ix_i : b_i\in B_i\}. Then |B|\ge \prod_{i=1}^n \frac{m_i}{2|A_i|+1}. We can sort the elements of B=b_1<b_2<\cdots<b_k, and one of \prod m_i + b_1 - b_k, b_i-b_{i-1} would work by pigeonhole.
16.03.2022 01:54
Let n=2013 be odd. Call a number k as i-bad if k is congruent to some value in A_i under \mod m_i. Call N+1 the minimum number that is neither 1-bad, nor 2-bad, ..., nor n-bad. That means each of 1,2,\ldots,N are at least one of 1-bad, or 2-bad, ... or n-bad. Let S_i be the set of numbers in 1,\ldots,N that are i-bad. So we know \begin{align*} N &= |S_1 \cup \cdots \cup S_n| \\ &= \sum |S_i| - \sum |S_i\cap S_j| + \sum |S_i\cap S_j\cap S_k| - \cdots \end{align*}by PIE. We want to upper bound the above. We'll lower bound and upper bound each term: Claim: For any indices i_1,\ldots,i_c, we have |S_{i_1}\cap \cdots \cap S_{i_c}| \in |A_{i_1}|\cdot \ldots \cdot |A_{i_c}|\cdot \left[ \frac{N}{m_{i_1}\cdots m_{i_c}}-1, \quad \frac{N}{m_{i_1}\cdots m_{i_c}} + 1 \right]. (We abuse interval notation above: c\cdot [x,y] means the interval [cx,cy].) Proof: We will show the stronger fact that |S_{i_1}\cap \cdots \cap S_{i_c}| \in |A_{i_1}|\cdot \ldots \cdot |A_{i_c}|\cdot \left[ \left \lfloor \frac{N}{m_{i_1}\cdots m_{i_c}}\right \rfloor, \quad \left \lfloor \frac{N}{m_{i_1}\cdots m_{i_c}}\right \rfloor + 1 \right]which implies the Claim. This is basically just CRT. Examples: Consider just |S_i|. Every m_i numbers, there will be exactly |A_i| bad numbers. The set 1,\ldots,N splits into \lfloor N/m_i\rfloor blocks of m_i, and then a leftover block. So the number of i-bad numbers in 1,\ldots,N is at least \lfloor N/m_i \rfloor \cdot |A_i| (equality when the leftover block is all good), and at most (\lfloor N/m_i \rfloor+1) \cdot |A_i| (equality when the leftover block is all bad). Consider now |S_i\cap S_j|. We want to find the number of values in 1,\ldots,N that are i-bad and j-bad. A number k is i-bad means it is congruent to some unique value in A_i under \mod m_i, and j-bad means its congruent to some unique value in A_j under \mod m_j. By CRT, there are hence |A_i|\cdot |A_j| values in \mod m_i m_j that are i-bad and j-bad. Now similar to the first bullet, we get the claimed bound. Continuing in this logic gives the upper and lower bounds generally. \blacksquare We will alternate using the upper and lower bounds in the Claim now to upper bound N: \begin{align*} N &= \sum |S_i| - \sum |S_i\cap S_j| + \sum |S_i\cap S_j \cap S_k| - \cdots \\ &\le \sum \left(\frac{N}{m_i}+1\right) |A_i| - \sum \left(\frac{N}{m_i m_j}-1\right)|A_i|\cdot |A_j| + \cdots \\ &= \left[ \sum \left( \frac{N}{m_i} \right)|A_i| - \sum \left(\frac{N}{m_i m_j}\right) |A_i|\cdot |A_j| + \cdots \right] \\ &\qquad + \left[ \sum |A_i| + \sum |A_i|\cdot |A_j| + \sum |A_i|\cdot |A_j| \cdot |A_k| + \cdots \right] \\ &= N\left[1+\left(\frac{|A_1|}{m_1}-1\right)\cdots \left(\frac{|A_n|}{m_n}-1\right)\right] + (|A_1|+1)\cdots (|A_n|+1)-1. \end{align*}Note that the second big sum has all +'s since the alternating +/- from PIE cancels with the alternating +/- from the lower/upper bounds of the Claim. Now subtracting N from both sides and using the fact that n is odd, we rearrange the above to: N\le \frac{(|A_1|+1)\cdots (|A_n|+1)-1}{\left(1-\frac{|A_1|}{m_1}\right)\cdots \left(1-\frac{|A_n|}{m_n}\right)}. \qquad (\clubsuit)Note that each term of the denominator is positive since |A_i|<m_i for all i. Case 1: 2|A_i| +1 \le m_i for all i. Then \frac{|A_i|+1}{1-\frac{|A_i|}{m_i}} \le \frac{|A_i|+1}{1-\frac{|A_i|}{2|A_i|+1}} = 2|A_i|+1,so from (\clubsuit), \begin{align*} N &\le (2|A_1|+1)\cdots (2|A_n|+1) - \frac{1}{\left(1-\frac{|A_1|}{m_1}\right)\cdots \left(1-\frac{|A_n|}{m_n}\right)} \\ &\le (2|A_1|+1)\cdots (2|A_n|+1) - 1, \end{align*}so N+1 \le \prod (2|A_i|+1), done! Case 2: 2|A_i| +1 > m_i for some i. Simply remove this i and induct down! (This argument is independent of all the solution above.) Indeed, we can basically pretend that the \mod m_i didn't even exist ever, and just take the N' case which has all the indices but i and then use CRT to just add the restriction that they are all some non-i-bad value \mod m_i. Then we will get that N \le N'm_i < N(2|A_i|+1), as needed.
11.03.2023 00:31
Solved with a few hints. The induction solution is more motivated than this one. We first prove the following independent lemma. Lemma: Let m be a positive integer and A \subseteq \{1,\ldots,m-1\}. Then there exists some B \subseteq \{0,\ldots,m-1\} such that |B| \geq \frac{m}{2|A|+1} and B-B \cap A = \emptyset in \mathbb{Z}/m\mathbb{Z}. Proof: Start with B empty and throw in elements arbitrarily as long as they don't cause things to break. Each new element k invalidates 2|A|+1 others (possibly already invalidated), namely k, k-a, and k+a, where a \in A is some element. \blacksquare By our lemma, create sets B_1,\ldots,B_{2013} such that B_i-B_i \cap A_i=\emptyset in \mathbb{Z}/m_i\mathbb{Z} with |B_i| \geq \frac{m}{2|A_i|+1}. Also let P_i be an integer such that P_i \equiv 1 \pmod{m_i} and P_i \equiv 0 \pmod{m_j} for all j \neq i. Now the linear combination \sum_{i=1}^{2013} b_iP_i \pmod{m_1\ldots m_{2013}},where b_i \in B_i for all i. Since there are \prod_{i=1}^{2013} |B_i| such combinations, counting multiplicity, there must be some pair of residues r_1 and r_2 such that the the mod-m_1\ldots m_{2013} residue of r_1-r_2 is at most \frac{\prod_{i=1}^{2013} m_i}{\prod_{i=1}^{2013} |B_i|}\leq \prod_{i=1}^{2013} (2|A_i|+1).Pick N equal to r_1-r_2, so N \leq \prod_{i=1}^{2013} (2|A_i|+1). We can check that, modulo m_i, N is in B_i-B_i, which is not in A_i, hence m_i \nmid N-a for any a \in A_i, so we are done. \blacksquare
25.12.2023 21:48
I wouldn't consider the CRT solution completely unmotivated, but it's quite tricky to get. Let M = m_1m_2 \cdots m_{2013}. Per the algorithm associated with CRT, let \varepsilon_i \equiv 1 \pmod m_i and \varepsilon_i \equiv 0 \pmod m_j for j \neq i. We will construct sets B_i with |B_i| \geq \frac{m_i}{2|A_i| + 1} for each i such that for any x, y \in B_i, x-y \not \in A_i. To do this, just use a greedy algorithm: upon adding some element k to B_i, every element k \pm a with a \in A_i is eliminated from consideration; this eliminates at most 2|A_i| + 1 elements at each step, hence the result. To finish, consider all such sums \sum_{i=1}^{2013} \varepsilon_i b_i where b_i \in B_i. There are \frac{M}{\prod_{i=1}^{2013} (2|A_i|+1)} such sums, which each correspond to residues modulo M by nature of the \varepsilon_i. Thus follows there exist two such sums S_1 and S_2 that differ by at most \prod_{i=1}^{2013} (2|A_i|+1). Taking N = |S_1-S_2| works.