All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
39 does it (Posted on 2012-02-19) Difficulty: 2 of 5
Prove that within any 39 consecutive natural numbers there must exist at least one number with the sum of its digits divisible by 11.
Bonus: Can the bound (39) be lowered?

See The Solution Submitted by Ady TZIDON    
Rating: 5.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Proof | Comment 3 of 4 |
Take any 39 consecutive natural numbers. One of the first 10 numbers must be divisible by 10. Let 10x be that number. Since 10x is in the first 10 numbers, the next 29 numbers must be in the 39 numbers. Therefore, all numbers from 10x to 10x+29 are in the set.

Suppose none of the sums of digits are divisible by 11. Let s(x) be the sum of digits of x. Then, s(10x)=s(x). Also, s(10x+1)=s(x)+1, s(10x+2)=s(x)+2, ..., s(10x+9)=s(x)+9. If none of s(x), s(x)+1, ..., s(x)+9 are divisible by 11, then s(x) must be 1 mod 11. Then, s(x)+1=2 mod 11, s(x)+2=3 mod 11, ..., s(x)+9=10 mod 11. The numbers from 10x+10 to 10x+19 are 10(x+1) to 10(x+1)+9. For the same reason as the numbers from 10x to 10x+9, s(x+1)=1 mod 11. The numbers from 10x+20 to 10x+29 are 10(x+2) to 10(x+2)+9. That means that s(x+2)=1 mod 11. Therefore, s(x), s(x+1), and s(x+2) are all 1 mod 11.

Suppose x+1 is divisible by 10. Let x+1=10n. Then, x+2=10n+1. Also, s(x+1)=s(n) and s(x+2)=s(n)+1, so s(x+2)=s(x+1)+1. Since s(x+1)=1 mod 11, s(x+2)=2 mod 11. However, s(x+2)=1 mod 11, so x+1 is not divisible by 10.

Let x+1=10n+m, where m is the last digit of x+1. Since x+1 is not divisible by 10, m>=1. Therefore, x+1>=10n+1, so x>=10n. Since x=10n+(m-1) and x>=10n, m-1 is the last digit of x. Therefore, s(x)=s(n)+(m-1) and s(x+1)=s(n)+m, so s(x+1)=s(x)+1. Since s(x)=1 mod 11, s(x+1)=2 mod 11. However, s(x+1)=1 mod 11, so that is a contradiction. Therefore, at least one of the 39 numbers adds to a multiple of 11.

To find 38 numbers where none of them adds to a multiple of 11, have the tenth number be divisible by 10. Let 10x be that number. Then, 10x+28 is the 38th number, so 10x+29 is not in the set. For the same reasons as above, s(x) and s(x+1) are both 1 mod 11. However, s(x+2) is different. The numbers from 10x+20 to 10x+28 are 10(x+2) to 10(x+2)+8. Then, s(10x+20)=s(x+2), s(10x+21)=s(x+2)+1, ..., s(10x+28)=s(x+2)+8. If none of these are divisible by 11, then s(x+2)=1 or 2 mod 11. We know that 1 mod 11 will not work, so s(x+2)=2 mod 11. If x+1 is not divisible by 10, we get the same contradiction as above. Therefore, x+1 is divisible by 10. When x+1 was divisible by 10 above, we got s(x+2)=2 mod 11. Therefore, this works.

Let x+1=10n. Then, x=10(n-1)+9. Therefore, s(x)=s(n-1)+9 and s(x+1)=s(n). Since s(x)=1 mod 11, s(n-1)=3 mod 11. Since s(x+1)=1 mod 11, s(n)=1 mod 11. For similar reasons as above, if n is not divisible by 10, then s(n-1)+1=s(n). However, s(n-1)+1=4 mod 11 and s(n)=1 mod 11, so n is divisible by 10. Let n=10n'. Then, s(n'-1)=5 mod 11 and s(n')=1 mod 11. s(n'-1)+1=6 mod 11, so n' is divisible by 10. Let n'=10n''. Then, s(n''-1)=7 mod 11 and s(n'')=1 mod 11. s(n''-1)+1=8 mod 11, so n'' is divisible by 10. Let n''=10n'''. Then, s(n'''-1)=9 mod 11 and s(n''')=1 mod 11. s(n'''-1)+1=10 mod 11, so n''' is divisible by 10. Let n'''=10n''''. Then, s(n''''-1)=0 mod 11 and s(n'''')=1 mod 11. s(n''''-1)+1=1 mod 11, so we can stop. The smallest possible value of n'''' is 1. Therefore, x+1=10n=100n'=1000n''=10000n'''=100000n''''=100000. Then, x=99999, so the 10th number in the set is 10x=999990. Then, the first number is 10x-9=999981, and the last number is 10x+28=1000018. Therefore, the numbers from 999981 to 1000018 are 38 consecutive numbers where none adds to a multiple of 11.


  Posted by Math Man on 2012-02-19 13:48:41
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information