1
$\begingroup$

Prove that in every 100 consecutive integers there is an integer whose digits sum to a number divisible by 14

How would one go about proving this? Many thanks!

$\endgroup$
  • 2
    $\begingroup$ What have you tried so far? $\endgroup$ – John Douma Jan 2 at 0:32
  • $\begingroup$ Every 14th integer is divisible by 14 so in a series of 100 consecutive integers.............????? $\endgroup$ – Phil H Jan 2 at 0:36
  • 1
    $\begingroup$ @PhilH OP is asking for the sum of the digits to be divisible by $14$, not the number itself. $\endgroup$ – saulspatz Jan 2 at 0:38
  • 2
    $\begingroup$ Have you written down the first few numbers that satisfy the condition? $\endgroup$ – saulspatz Jan 2 at 0:40
  • 1
    $\begingroup$ In a set of 100 consecutive integers, you can write each number as $10a + b$, where a and b form the tens and ones place, respectively. Over those 100 digits, we can ignore the hundreds, the thousands, etc. places. Then both $a$ and $b$ will have cycled through the digits $0-9$ at least once. 14, as a sum of two digits, can be expressed as $9+5, 8+6, 7+7, 6+8, 5+9$, so that means in 100 consecutive integers, there will be at most $5$ numbers whose digital sum is 14. This only works up to a certain number, of course, because you'll hit something like $1,234,567,890$ to $1,234,567,990$, failing. $\endgroup$ – Christopher Marley Jan 2 at 1:01
2
$\begingroup$

One of these 100 consecutive integers $a$ will end in 00. Say that the remainder of $a$ divided by 14 is $v\in\{0,1,\ldots,13\}$.

Case 1. There exist among these 100 consecutive integers at least 49 larger than $a$. In such case the remainders of the sum of the digits of $a,a+1,\ldots,a+49$ will range between $$ a\!\!\!\!\!\!\mod\!\! 14,\,\, a+1\!\!\!\!\!\!\mod\!\! 14,\ldots, a+49\!\!\!\!\!\!\mod\!\! 14, $$ and hence will cover the whole of $\{0,1,\ldots,13\}$.

Case 2. There exist among these 100 consecutive integers at least 50 smaller than $a$. Then we shall 50 numbers with two last digits ranging for 50 to 99 and all the other digits identical, and if the remainder the sum of the digits of the one ending in 50 is $w$ then we shall have as remainders $$ w\!\!\!\!\!\!\mod\! 14, w+1\!\!\!\!\!\!\mod 14,\ldots, w+49\!\!\!\!\!\!\mod 14 $$ which again will cover the whole of $\{0,1,\ldots,13\}$.

$\endgroup$
  • $\begingroup$ Note the OP asked for the sum of the digits being divisible by $14$, not the number itself. Your proof is basically correct, but there are $2$ things you should change. First, have $v$ and $w$ be the remainders of the number when divided by $14$. Second, your list of "mod" statements should end with $a + 4 + 9 \mod 14$, with a statement that all of the possible remainders from $0$ to $13$ inclusive are included so, no matter the starting point, one of them needs to be equal to a multiple of $14$. Also, you may wish to provide a more detailed explanation for this part. $\endgroup$ – John Omielan Jan 2 at 2:01
  • $\begingroup$ @JohnOmielan See my revised answer. $\endgroup$ – Yiorgos S. Smyrlis Jan 2 at 13:01
  • $\begingroup$ Thanks for making the corrections. However, this might be a bit picky, but note your $2$ sets of mod statements are not quite correct at the end. This is because $w + 49 \mod 14$ is not the same as $w + 4 + 9 \mod 14$ as $49 - 4 - 9 = 36$ with $36 \equiv{8} \pmod{14}$. This is why I suggested my earlier change. However, here is a perhaps a slightly easier way to see this, & how I see it myself. Note you only need to use $0$ to $3$, then end with $4 + 0, \ldots 4 + 9$ for $40$ to $49$, with this more simply & directly showing it covers all $0$ to $13$ values. $\endgroup$ – John Omielan Jan 2 at 17:57
  • $\begingroup$ One other thing you may wish to do is make it explicit why $100$ is the minimum value for this problem. It's because between $0$ to $49$, the span of $0$ to $13$ for the sum of digits is only achieved with the final value, i.e., $49$, giving $13$. Thus, there may be cases where a smaller set of consecutive set of integers don't have any which are a multiple of $14$. Note, however, I haven't tried to prove this rigorously myself (e.g., perhaps $99$ might still work), so I suggest you first confirm this yourself before potentially mentioning it. $\endgroup$ – John Omielan Jan 2 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.