Maths Olympiad Prep

Library / /5 of 11

Combinatorics Difficulty 8.2 Shortlist Prove it Switzerland

Problem:

Let nn be a positive integer. Prove that there exists a finite sequence SS consisting of only zeros and ones, satisfying the following property: For any positive integer d2d \geq 2, when SS is interpreted as a number in base dd, the resulting number is non-zero and divisible by nn.

Remark: The sequence S=sksk1s1s0S=s_{k} s_{k-1} \cdots s_{1} s_{0} interpreted in base dd is the number i=0ksidi\sum_{i=0}^{k} s_{i} d^{i}.

Solutions — 2

Solution 1

Solution:

Working in any base d2d \geq 2, by pigeonhole, two of the numbers
1,11,111,,1111n+1 1, 11, 111, \ldots, \overbrace{11 \cdots 11}^{n+1}
have the same residue modn\bmod n. Therefore their difference
D=1111t0000k with k,tn D = \overbrace{11 \cdots 11}^{t} \overbrace{00 \cdots 00}^{k} \text{ with } k, t \leq n
is divisible by nn in base dd. But then also
nDdnk(1+dt+d2t++dn!t)=1111n!0000n n \mid D \cdot d^{n-k} \cdot \left(1 + d^{t} + d^{2t} + \cdots + d^{n!-t}\right) = \overbrace{11 \cdots 11}^{n!} \overbrace{00 \cdots 00}^{n}
in base dd. But the representation of this number is independent of dd, hence we have found our sequence of zeros and ones.

Solution 2

Solution:

It suffices to find a non-empty, finite set σN\sigma \in \mathbb{N} such that
nsσds n \mid \sum_{s \in \sigma} d^{s}
for all d2d \geq 2. Consider the set σ={φ(n),2φ(n),,nφ(n)}\sigma = \{\varphi(n), 2\varphi(n), \ldots, n\varphi(n)\}. For d2d \geq 2, if (d,n)=1(d, n) = 1:
sσds=k=1n(dφ(n))k=n \sum_{s \in \sigma} d^{s} = \sum_{k=1}^{n} \left(d^{\varphi(n)}\right)^{k} = n
Else, if g=(d,n)1g = (d, n) \neq 1, let n=xyn = x y with (x,y)=(y,d)=1(x, y) = (y, d) = 1 and yy maximal:
sσds=k=1n(dφ(n))kdφ(n)(dnφ(n)1)dφ(n)10modx \sum_{s \in \sigma} d^{s} = \sum_{k=1}^{n} \left(d^{\varphi(n)}\right)^{k} \equiv \frac{d^{\varphi(n)}\left(d^{n\varphi(n)}-1\right)}{d^{\varphi(n)}-1} \equiv 0 \quad \bmod x
which makes sense, as dφ(n)1d^{\varphi(n)}-1 is coprime to xx, and true since vp(x)vp(n)φ(n)v_{p}(x) \leq v_{p}(n) \leq \varphi(n) (ask raphi for an elaborate explanation). And yy divides this sum by the first argument as above. Now n=xyn = x y divides the sum since (x,y)=1(x, y) = 1.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.