The Magic Café
Username:
Password:
[ Lost Password ]
  [ Forgot Username ]
The Magic Cafe Forum Index » » Puzzle me this... » » 11111....00000... (0 Likes) Printer Friendly Version

Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
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.
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
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


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)
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
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)
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
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.)
MPHanson
View Profile
New user
17 Posts

Profile of MPHanson
Please tell me that's not the easy way...
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
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 Smile

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.
Jonathan Townsend
View Profile
Eternal Order
Ossining, NY
27034 Posts

Profile of Jonathan Townsend
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....

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.
...to all the coins I've dropped here
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
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.
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
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.
The Magic Cafe Forum Index » » Puzzle me this... » » 11111....00000... (0 Likes)
[ Top of Page ]
All content & postings Copyright © 2001-2020 Steve Brooks. All Rights Reserved.
This page was created in 0.19 seconds requiring 5 database queries.
The views and comments expressed on The Magic Café
are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic.
> Privacy Statement <

ROTFL Billions and billions served! ROTFL