Maths Olympiad Prep

Library / /130 of 155

Combinatorics Difficulty 6.9 National olympiad Prove it Saudi Arabia

Consider the set X={1,2,3,,2018}X=\{1,2,3, \ldots, 2018\}. How many positive integers kk with 2k20172 \leq k \leq 2017 that satisfy the following conditions:

i) There exists some partition of the set XX into 10091009 disjoint pairs which are (a1,b1),(a2,b2),,(a1009,b1009)(a_{1}, b_{1}), (a_{2}, b_{2}), \ldots, (a_{1009}, b_{1009}) with aibi{1,k}|a_{i}-b_{i}| \in \{1, k\}.

ii) For all partitions satisfy the condition (i), the sum T=i=11009aibiT=\sum_{i=1}^{1009}|a_{i}-b_{i}| has the right most digit is 99.

Solution

First, we notice that for all 2k20172 \leq k \leq 2017, we always can find a partition satisfy i). For example, we can choose ai=2i1a_{i}=2i-1, bi=2ib_{i}=2i with i=1,2,,1009i=1,2, \ldots, 1009.

Denote mm as the number of pairs (ai,bi)(a_{i}, b_{i}) with aibi=k|a_{i}-b_{i}|=k then
T=(1009m)1+mk=1009+(k1)m. T=(1009-m) \cdot 1 + m \cdot k = 1009 + (k-1)m.
Hence, the necessary condition of kk is (k1)m(k-1)m is divisible by 1010. First, we can see that all numbers k1(mod5)k \equiv 1 \pmod{5} satisfy the given condition.

Indeed, we have some cases:

1. If k1(mod10)k \equiv 1 \pmod{10} then 10k110 \mid k-1 and ii) is satisfied.

2. If k6(mod10)k \equiv 6 \pmod{10} then kk is even. Thus, we need to prove mm is even. This is true because we can write m=m1+m2m = m_{1} + m_{2} with m1,m2m_{1}, m_{2} are the number of pairs with the difference is kk that have same parity and different parity. In XX, the number of even and odd numbers are equal and all the pairs (ai,bi)(a_{i}, b_{i}) with aibi=1|a_{i}-b_{i}|=1 also contain exactly 11 number in each type of even/odd. These imply that m1=m2m_{1}=m_{2} or mm is an even number.

Hence, all numbers k1(mod5)k \equiv 1 \pmod{5} satisfy the given condition.

Next, we will prove that all other numbers kk do not satisfy the given condition.

3. If kk is odd then k1k-1 is not divisible by 55. We choose the partition with a1=1a_{1}=1, b1=k+1b_{1}=k+1 and the rest are divided into pairs with ai,bia_{i}, b_{i} being two consecutive numbers. It is easy to check that this partition satisfies i) but not ii) because T=1008+k≢9(mod10)T=1008+k \not\equiv 9 \pmod{10}.

4. If kk is even, k1k-1 is not divisible by 55 then k1k-1 is an odd number that is not divisible by 55. We choose the partition with exactly two pairs (1,k+1),(2,k+2)(1, k+1), (2, k+2) and the rest are divided into pairs with ai,bia_{i}, b_{i} being two consecutive numbers. Similarly with the previous case, we have T=1009+2(k1)≢9(mod10)T=1009+2(k-1) \not\equiv 9 \pmod{10}.

Therefore, the necessary and sufficient condition of kk is k1(mod5)k \equiv 1 \pmod{5}. From 22 to 20172017, we have 403403 numbers in total satisfy it.

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 and solution reproduced as published; topic and difficulty added by this site.