Maths Olympiad Prep

Library / /176 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

For each integer 1j20171\le j\le 2017, let SjS_j denote the set of integers 0i2201710\le i\le 2^{2017} - 1 such that i2j1\left\lfloor \frac{i}{2^{j-1}} \right\rfloor is an odd integer. Let PP be a polynomial such that
P(x0,x1,,x220171)=1j2017(1iSjxi).P\left(x_0, x_1, \ldots, x_{2^{2017} - 1}\right) = \prod_{1\le j\le 2017} \left(1 - \prod_{i\in S_j} x_i\right).
Compute the remainder when
(x0,,x220171){0,1}22017P(x0,,x220171) \sum_{\left(x_0, \ldots, x_{2^{2017} - 1}\right)\in\{0, 1\}^{2^{2017}}} P\left(x_0, \ldots, x_{2^{2017} - 1}\right)
is divided by 20172017.

[i]Proposed by Ashwin Sah[/i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. **Define the sets Sj S_j :**
For each integer 1j2017 1 \le j \le 2017 , the set Sj S_j consists of integers 0i220171 0 \le i \le 2^{2017} - 1 such that i2j1 \left\lfloor \frac{i}{2^{j-1}} \right\rfloor is an odd integer. This can be written as:
Sj={i0i220171,i2j1 is odd} S_j = \{ i \mid 0 \le i \le 2^{2017} - 1, \left\lfloor \frac{i}{2^{j-1}} \right\rfloor \text{ is odd} \}

2. **Express the polynomial P P :**
The polynomial P P is given by:
P(x0,x1,,x220171)=1j2017(1iSjxi) P(x_0, x_1, \ldots, x_{2^{2017} - 1}) = \prod_{1 \le j \le 2017} \left(1 - \prod_{i \in S_j} x_i \right)
Let Tj=iSjxi T_j = \prod_{i \in S_j} x_i . Then:
P(x0,x1,,x220171)=1j2017(1Tj) P(x_0, x_1, \ldots, x_{2^{2017} - 1}) = \prod_{1 \le j \le 2017} (1 - T_j)

3. **Evaluate the polynomial P P :**
The polynomial P P evaluates to 1 if all Tj T_j are 0, and 0 if at least one Tj T_j is 1. We need to count the number of tuples (x0,x1,,x220171){0,1}22017 (x_0, x_1, \ldots, x_{2^{2017} - 1}) \in \{0, 1\}^{2^{2017}} such that all Tj T_j are 0.

4. Use complementary counting and the Principle of Inclusion-Exclusion (PIE):
Let Aj A_j denote the set of tuples where Tj=1 T_j = 1 . We want to compute:
X=PAj+AiAjAiAjAk+ X = |P| - \sum |A_j| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + \cdots
where P=222017 |P| = 2^{2^{2017}} .

5. Calculate the sizes of intersections:
- Aj=222016 |A_j| = 2^{2^{2016}} because Sj=22016 |S_j| = 2^{2016} .
- For AiAj |A_i \cap A_j| with i<j i < j , Sj S_j fills half of the gaps in Si S_i , so AiAj=222015 |A_i \cap A_j| = 2^{2^{2015}} .
- Generally, Aa1Aa2Aak=222017k |A_{a_1} \cap A_{a_2} \cap \cdots \cap A_{a_k}| = 2^{2^{2017 - k}} .

6. Sum using PIE:
X=k=02017(1)k(2017k)222017k X = \sum_{k=0}^{2017} (-1)^k \binom{2017}{k} 2^{2^{2017 - k}}
Simplifying modulo 2017:
X2220172(mod2017) X \equiv 2^{2^{2017}} - 2 \pmod{2017}

7. **Compute 222017mod2017 2^{2^{2017}} \mod 2017 :**
Using Fermat's Little Theorem, 220161(mod2017) 2^{2016} \equiv 1 \pmod{2017} . We need to find 22017mod2016 2^{2017} \mod 2016 :
220172(mod2016) 2^{2017} \equiv 2 \pmod{2016}
Thus:
22201722=4(mod2017) 2^{2^{2017}} \equiv 2^2 = 4 \pmod{2017}

8. Final calculation:
X42=2(mod2017) X \equiv 4 - 2 = 2 \pmod{2017}

The final answer is 2\boxed{2}

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.