Topic: 11111....00000...
 Message: Posted by: Nir Dahan (Jun 27, 2005 03:41PM)
Hi all,

Here is a nice puzzle that can be solved either in an easy way or the hard way. I must say that the hard way needs some number theory to crack it down especially some help from our friend Mr. Fermat... but there is a much more intuitive way - ok here goes:

Prove or disprove that for any natural number (positive integer) you can find a DECIMAL number consisting of a some 1s followed by some 0s that will divide this number.

Some examples:
integer - 5 -> 110 divides it (in words "one hundred ten") 2 "1"s and 1 "0"s
integer - 3 -> 111 divides 3 - 3 "1"s and 0 "0"s

and so on...

I would not give a counterexample because if it exists it would solve the puzzle.

enjoy,

Nir

P.S. Just to prevent confusion here - no binary inumbers are involved even though we are dealing with 1s and 0s. It is important to stress it cause many people get back to that and misunderstand the puzzle.
 Message: Posted by: stanalger (Jun 27, 2005 05:55PM)
[quote]
On 2005-06-27 16:41, Nir Dahan wrote:

prove or disprove that for any natural number (positive integer) you can find a DECIMAL number consisting of a some 1s followed by some 0s that will divide this number.

some examples:
integer - 5 -> 110 divides it (in words "one hundred ten") 2 "1"s and 1 "0"s
integer - 3 -> 111 divides 3 - 3 "1"s and 0 "0"s
[/quote]

Nir, when you say "divides it" I think you mean "is a multiple of it."

111 is a multiple of 3 (111= 3*37)
110 is a multiple of 5 (110= 5*22)
Note: 10 is also a multiple of 5 (10= 5*2)
 Message: Posted by: Nir Dahan (Jun 27, 2005 06:16PM)
You are right stan.
I just gave an example there can be many solutions to 1 integer.
example
integer - 2
solutions
10
110
1110
1....10
or
100
1000
10...0
the solution need not be unique

but the "1"s and "0" number divided by the integer must result in an integer as well - by that I mean "divides it"

Nir

p.s. sorry english is not my first language and I translated from Hebrew (my first language)
 Message: Posted by: stanalger (Jun 27, 2005 06:41PM)
1=(10^1-1)/9
11=(10^2-1)/9
111=(10^3-1)/9
etc.

Given n (a natural number), the following list contains
n+1 numbers, all between 0 and n-1 (inclusive).
(10^1-1)/9 mod n
(10^2-1)/9 mod n
(10^3-1)/9 mod n
.
.
.
(10^n - 1)/9 mod n
(10^(n+1) - 1)/9 mod n}
By the pigeon-hole principle, we can find a
pair of numbers in the list which are equal.

Say (10^a - 1)/9 mod n = (10^b -1)/9 mod n
and a > b.

Then n divides the difference:
n divides (10^a -1)/9 - (10^b -1)/9
and this last number is of the
required form.

(The difference is the base ten integer
consisting of (a-b) 1's
followed by b 0's.)
 Message: Posted by: MPHanson (Jun 28, 2005 01:16AM)
Please tell me that's not the easy way...
 Message: Posted by: Nir Dahan (Jun 28, 2005 03:07AM)
Given n (a natural number), the following list contains
n+1 numbers, all between 0 and n-1 (inclusive).
(10^1-1)/9 mod n
(10^2-1)/9 mod n
(10^3-1)/9 mod n
.
.
.
(10^n - 1)/9 mod n
(10^(n+1) - 1)/9 mod n}
By the pigeon-hole principle, we can find a
pair of numbers in the list which are equal.

-------------

That is right - but I would say there is an easier way to look at it :)

Very nice stan.

An easier (for me) way to look at it is
to notice two things (basically stan already mentioned them
1 - a "1"s and "0"s number minus another "1"s and "0"s number with the same amount of "0"s will result in a new number of the form "1"s and "0"s
2 - start with a big enough number say 11100, say the result when dividing 11100 by N is some number and a remainder x1. now like stan said, we "generate" another result by adding a leading 1. so we have 111100 now. 111100/N gives us remainder x2 now. Comtinue doing this N+1 times and you are guarenteed that two remainders are the same (pigeon hole).
Now take the two big numbers that generated those remainders (say 1111111111100 and 1111100) and subtract one from the other. According to (1) we get a new "1"s and "0" number. 1111111000000. And this must divide without remainder N.

Again, stan's solution is perfectly correct, for me it is just easier to look at it without the need for the power representations of the numbers.

Nir

P.S. The hard way uses little Fermat theorem, so I have been told by number theorist friends and it is almost straight forward. I do not have the knowledge to say whether that solution is more elegant or exactly equivalent but since I don't know it I find it harder.
 Message: Posted by: Jonathan Townsend (Jun 28, 2005 07:56AM)
[quote]
On 2005-06-27 16:41, Nir Dahan wrote:...you can find a DECIMAL number consisting of some 1s followed by some 0s that will divide this number....
[/quote]
As 1.0... goes into anything... I went for the trivial case, thus avoiding issues about 1 and 10 (2) and prime ( relatively prime ) number considerations.

Yeah this felt like a situation for Fermat's Little Theorem.
 Message: Posted by: stanalger (Jun 28, 2005 09:04AM)
The original statement of the problem contained
a language/translation problem.

3 divides 11100
(i.e. 11100 is a multiple of 3)
7 divides 111111000
(i.e. 111111000 is a multiple of 7)
12 divides 11100
(i.e. 11100 is a multiple of 12)
13 divides 111111000000
(i.e. 111111000000 is a multiple of 13)

Show that for any positive integer, n,
there is a multiple of n
which is an integer whose base
ten representation consists of a
string of 1's followed by a
string of 0's.
 Message: Posted by: stanalger (Jun 28, 2005 11:44AM)
It seems I'm often careless with my wording.
Let me try again:

Show that every positive integer has a multiple
whose base ten representation
consists entirely of
a string of 1's (with AT LEAST one 1)
followed by a string of 0's.

Without the "AT LEAST one 1" part, I suppose one
could say 0 is a string of zero 1's followed by
one 0. And 0 is a multiple of every number.