Spring 2017, problem 36

Show that in every sequence of $79$ consecutive positive integers, there is a positive integer whose sum of digits is divisible by $13$.


5 years ago

Let $n$ be a number whose ones digits is zero and whose tens digits is between 0 and 6. Then in the list of 13 numbers below, $$n,n+1,n+2,n+3,\dots,n+9,n+19,n+29,n+39$$ each has a digit sum which is one more than the last. Therefore, one the digit sums is a multiple of 13.

Now, consider the range of $79$ consective numbers $m,m+1,m+2,\dots,m+78$. At least one of the numbers in the sublist $m,m+1,\dots, m+39$ satisfies the constraints in the first sentence; the worst case is when $m\equiv 61$ (mod 100), where $m+39$ is the first number ending in either 00, 10, 20, 30, 40, 50 or 60. Calling that number $n$, so $n\le m+39$, some number in the range $n,n+1,\dots,n+39\le m+78$ has a digit sum divisible by 13, and this falls in the original list.

he minimality of M(a,b) forces 3a2+2b=3b2+2a, say 3a2−2a=3b2−2b.

E.g. solving in a we get a=1±(3b−1)3 say a=b or a=23−b.

The first case bring to minimize 3b2+2b and choosing b=−13 we get the value −13.

The second case asks for the minimum of 3b2−2b+43 and choosing b=13 we get the value 1.

Thus minM(a,b)=1, reached with a=b=13.

SusanBones 1 month ago

This is indeed a very efficient way.

AdamzSendler 1 month ago
1 month ago

Since the set B is a rearrangement of the set A, then A = B by the defintion of sets. Furthermore, S[1] contains all the elements of set A, and S[2] contains all the elements of set B where all m[n] terms are in their rearranged positions. Now suppose the following proposition: if A = B, then the series S[1] and S[2] must have the same parity at one position.

Proof (Contrapostive) Consider when S[1] and S[2] do not have the same parity at any position. That is,

S[1] = o, e, o, e, ... o (Note that "o" and "e" denote odd and even, respectively, for convenience)

S[2] = e, o, e, o, ... e

Notice that the set A does not equal the set B because the series m[n] does not contain the same terms as the series n. Therefore the contrapositive proves that the series m[n] and n must have the same parity at one position.

From this, at least one term ( m[n] - n ) must be even since m[n] and n have the same parity. Knowing this, any integer multiplied by an integer of opposite parity is even, and any even integer multiplied by an even integer is even. Therefore,

( m[1] - 1 ) ( m[2] - 2 ) ( m[3] - 3 ) ... ( m[n] - n )

must be even if n is odd.