CombinatoricsDifficulty 6.7National olympiadFind the answer
For each integer 1≤j≤2017, let Sj denote the set of integers 0≤i≤22017−1 such that ⌊2j−1i⌋ is an odd integer. Let P be a polynomial such that P(x0,x1,…,x22017−1)=1≤j≤2017∏1−i∈Sj∏xi. Compute the remainder when (x0,…,x22017−1)∈{0,1}22017∑P(x0,…,x22017−1) is divided by 2017.
[i]Proposed by Ashwin Sah[/i]
A number or a short expression. Spacing and $ signs are ignored.
Solution
1. **Define the sets Sj:** For each integer 1≤j≤2017, the set Sj consists of integers 0≤i≤22017−1 such that ⌊2j−1i⌋ is an odd integer. This can be written as: Sj={i∣0≤i≤22017−1,⌊2j−1i⌋ is odd}
2. **Express the polynomial P:** The polynomial P is given by: P(x0,x1,…,x22017−1)=1≤j≤2017∏1−i∈Sj∏xi Let Tj=∏i∈Sjxi. Then: P(x0,x1,…,x22017−1)=1≤j≤2017∏(1−Tj)
3. **Evaluate the polynomial P:** The polynomial P evaluates to 1 if all Tj are 0, and 0 if at least one Tj is 1. We need to count the number of tuples (x0,x1,…,x22017−1)∈{0,1}22017 such that all Tj are 0.
4. Use complementary counting and the Principle of Inclusion-Exclusion (PIE): Let Aj denote the set of tuples where Tj=1. We want to compute: X=∣P∣−∑∣Aj∣+∑∣Ai∩Aj∣−∑∣Ai∩Aj∩Ak∣+⋯ where ∣P∣=222017.
5. Calculate the sizes of intersections: - ∣Aj∣=222016 because ∣Sj∣=22016. - For ∣Ai∩Aj∣ with i<j, Sj fills half of the gaps in Si, so ∣Ai∩Aj∣=222015. - Generally, ∣Aa1∩Aa2∩⋯∩Aak∣=222017−k.
6. Sum using PIE: X=k=0∑2017(−1)k(k2017)222017−k Simplifying modulo 2017: X≡222017−2(mod2017)
7. **Compute 222017mod2017:** Using Fermat's Little Theorem, 22016≡1(mod2017). We need to find 22017mod2016: 22017≡2(mod2016) Thus: 222017≡22=4(mod2017)
8. Final calculation: X≡4−2=2(mod2017)
The final answer is 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.