In Mathcity, there are infinitely many buses and infinitely many stations. The stations are indexed by the powers of $2: 1, 2, 4, 8, 16, ...$ Each bus goes by finitely many stations, and the bus number is the sum of all the stations it goes by. For simplifications, the mayor of Mathcity wishes that the bus numbers form an arithmetic progression with common difference $r$ and whose first term is the favourite number of the mayor. For which positive integers $r$ is it always possible that, no matter the favourite number of the mayor, given any $m$ stations, there is a bus going by all of them? Proposed by Savinien Kreczman and Martin Rakovsky, France
Problem
Source: JBMO Shortlist 2021
Tags: Junior, Balkan, shortlist, 2021, combinatorics
Rukevwe
07.01.2023 11:46
Only $r=1$?
Rukevwe
07.01.2023 11:54
Not sure if this is correct or if I'm misinterpreting the problem.
Let the mayor's favourite number be $a$ and let the sum of the numbers of the $m$ stations be $t$. We wish to find all $r$ such that there exists $k$ that satisfies $a+kr=t$.
Now, we have that $r \mid (t-a)$ and in particular, for $a = t-1$, we get $r \mid 1$ and so $r = 1$
S_2
07.01.2023 23:21
I think this is wrong as its not necessary for the bus to go only to the m stations, but it can also visit other stations so the sum doesn't have to be exactly t.
Rukevwe
07.01.2023 23:53
Ohhh I see. Any solutions then?
S_2
08.01.2023 01:13
Sorry, i don't know how to use Latex but i appreciate any help. My solution might be wrong. I claim that the answer is all odd r. a is the mayors favourite number. Case 1: r is even If r is even then we just pick a=2 and it is obvious that we wont be able to include station 1. Case 2: r is odd Suppose that the sum of the m stations is S, we just need to prove that for any a, there exists a positive integer k and t(a sum of powers of two not in the m stations), which satisfy the equasion: a+ r(k)= S+t, or that S+t-a = 0(mod r) In the case that S-a is already 0(mod r), we just take t=0, then there exist c,c1,...cn such that 2^c, 2^c2,...2^cn are all 1 modulo r, and none of which are in the m stations, because (2,r)=1. ( ck are multiples of the order of 2 mod r) We just pick however many we need so that t=a-S(mod r), and we are done. Also might be worth mentioning that S+t is the binary representation of the number and is unique.
Rukevwe
08.01.2023 01:48
S_2 wrote: I claim that the answer is all odd $r$. $a$ is the mayor's favourite number. Case 1: $r$ is even. If $r$ is even then we just pick $a=2$ and it is obvious that we wont be able to include station $1$. Case 2: $r$ is odd. Suppose that the sum of the $m$ stations is $S$, we just need to prove that for any $a$, there exist positive integers $k$ and $t$ (a sum of powers of two not in the $m$ stations), which satisfy the equation: $a+ rk = S+t$, or that $S+t-a = 0 \pmod r$ In the case that $S-a$ is already $0 \pmod r$, we just take $t=0$, then there exist $c, 2c, \dots ,nc$ such that $2^c, 2^{2c}, \dots, 2^{nc}$ are all $1$ modulo $r$, and none of which are in the $m$ stations, because $(2,r)=1$. We just pick however many we need so that $t=a-S \pmod r$, and we are done.
john0512
10.04.2023 20:09
The answer is all odd $r$. When $r$ is even, just take the favorite number to be any even number, and no bus will visit station 1. When $r$ is odd, by Chinese Remainder Theorem, there exists a term in the arithmetic progression that is congruent to $-1\pmod {2^b}$ for any positive integer $b$. Therefore, we can pick a $b$ and then we know that some bus goes through all of the last $b$ stations. Since $b$ can be arbitrarily large, we are done.