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

Home > Numbers
Niners (Posted on 2002-10-23) Difficulty: 4 of 5
The set of numbers {9, 99, 999, 9999, ...} has some interesting properties. One of these has to do with factorization. Take any number n that isn't divisible by 2 or by 5. You will be able to find at least one number in the set that is divisible by n. Furthermore, you won't need to look beyond the first n numbers in the set.

Prove it.

(from http://www.ocf.berkeley.edu/~wwu/riddles/)

See The Solution Submitted by levik    
Rating: 4.2500 (8 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Here is my proof | Comment 14 of 15 |
The set {9, 99, 999, ...} can be expressed as {10^1 - 1, 10^2 - 1, 10^3 - 1, ...}

Choose any number n coprime to 10 (stated by the problem) and consider the subset {10^1 - 1, 10^2 - 1, 10^3 - 1, ..., 10^(n+1) - 1}.

There are at most n unique remainders when the elements of the subset are divided by n. But because there are n+1 elements, there are at least two elements with the same remainder.

Let 10^y - 1 and 10^x - 1 be two elements with the same remainder with y > x. Then ((10^y - 1) - (10^x - 1)) mod n = 0.

Let d=y-x. (10^y - 1) - (10^x - 1) = 10^y - 10^x = 10^x * (10^(y-x) - 1) = 10^x * (10^d - 1)

Since n is coprime to 10, n is a factor of 10^d - 1.

This proves there is some member of the set {9, 99, 999, ...} (the dth member) which has n as a factor.

Since n+1 >= y and y > d, d will never be greater than n.

This proves that the number 10^d - 1 is one of the first n terms of the set {9, 99, 999, ...}.
Edited on January 22, 2004, 1:14 pm
  Posted by Brian Smith on 2003-05-08 06:26:33
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 (2)
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