Maths Olympiad Prep

Library / /63 of 63

Algebra Difficulty 8.7 Shortlist Find the answer

Find the number of ordered 6464-tuples (x0,x1,,x63)(x_0,x_1,\dots,x_{63}) such that x0,x1,,x63x_0,x_1,\dots,x_{63} are distinct elements of {1,2,,2017}\{1,2,\dots,2017\} and x0+x1+2x2+3x3++63x63 x_0 + x_1 + 2x_2 + 3x_3 + \cdots + 63 x_{63} is divisible by 2017.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The desired count is 2016!1953!63!2016\frac{2016!}{1953!}- 63! \cdot 2016, which we compute using the principle of inclusion-exclusion. As in A2, we use the fact that 2017 is prime; this means that we can do linear algebra over the field F2017.\mathbb{F}_{2017}. In particular, every nonzero homogeneous linear equation in nn variables over F2017\mathbb{F}_{2017}hasexactly has exactly 2017^{n-1}solutions.For solutions. For π\piapartitionof a partition of {0,,63}\{0,\dots,63\},let, let π|\pi| denote the number of distinct parts of π\pi,Let, Let π0\pi_0denotethepartitionof denote the partition of {0,,63}\{0,\dots,63\}into64singletonparts.Let into 64 singleton parts. Let π1\pi_1denotethepartitionof denote the partition of {0,,63}\{0,\dots,63\} into one 64-element part. For π,σ\pi, \sigmatwopartitionsof two partitions of {0,,63}\{0,\dots,63\},write, write πσ\pi | \sigmaif if π\piisarefinementof is a refinement of σ\sigma(thatis,everypartin (that is, every part in σ\sigmaisaunionofpartsin is a union of parts in π\pi).Byinductionon). By induction on π|\pi|,wemayconstructacollectionofintegers, we may construct a collection of integers μπ\mu_\pi,oneforeach, one for each π\pi, with the properties that [ | = 1 = 0 0 0 . ] Define the sequence\text{, with the properties that [ | = 1 = 0 0 0 . ] Define the sequence}c_0, ,c63\dots, c_{63}bysetting by setting c_0 = 1and and c_i = ifor for i>1.Let. Let NπN_\pibethenumberofordered64tuples be the number of ordered 64-tuples (x0,,x63)(x_0,\dots,x_{63})ofelementsofF2017 of elements of \mathbb{F}_{2017} such that xi=xjx_i = x_j whenever ii and jj belong to the same part and i=063cixi\sum_{i=0}^{63} c_i x_i is divisible by 2017. Then NπN_\pi equals 2017π12017^{|\pi|-1} unless for each part SS of π\pi, the sum iSci\sum_{i \in S} c_i vanishes; in that case, NπN_\pi instead equals 2017π2017^{|\pi|}. Since c0,,c63c_0, \dots, c_{63} are positive integers which sum to 1+63642=20171 + \frac{63 \cdot 64}{2} = 2017, the second outcome only occurs for π=π1\pi = \pi_1. By inclusion-exclusion, the desired count may be written as πμπNπ=2016μπ1+πμπ2017π1. \sum_{\pi} \mu_\pi N_\pi = 2016 \cdot \mu_{\pi_1} + \sum_{\pi} \mu_\pi 2017^{|\pi|-1}. Similarly, the number of ordered 64-tuples with no repeated elements may be written as 64!(201764)=πμπ2017π. 64! \binom{2017}{64} = \sum_{\pi} \mu_\pi 2017^{|\pi|}. The desired quantity may thus be written as 2016!1953!+2016μπ1\frac{2016!}{1953!} + 2016 \mu_{\pi_1}. It remains to compute μπ1\mu_{\pi_1}. We adopt an approach suggested by David Savitt: apply inclusion-exclusion to count distinct 64-tuples in an arbitrary\emph{arbitrary} set AA. As above, this yields A(A1)(A63)=πμπAπ. |A|(|A|-1) \cdots (|A|-63) = \sum_{\pi} \mu_\pi |A|^{|\pi|}. Viewing both sides as polynomials in A|A| and comparing coefficients in degree 1 yields μπ=63!\mu_\pi = -63! and thus the claimed answer.

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: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.