The Magic Cafe Forum Index » » Puzzle me this... » » 11111....00000... (0 Likes) Nir Dahan Inner circle Munich, Germany 1390 Posts  Posted: Jun 27, 2005 03:41 pm 0 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. Adventures in ASIC digital design stanalger Special user St. Louis, MO 996 Posts  Posted: Jun 27, 2005 05:55 pm 0 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 Inner circle Munich, Germany 1390 Posts  Posted: Jun 27, 2005 06:16 pm 0 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) Adventures in ASIC digital design stanalger Special user St. Louis, MO 996 Posts  Posted: Jun 27, 2005 06:41 pm 0 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 New user 17 Posts  Posted: Jun 28, 2005 01:16 am 0 Please tell me that's not the easy way... Nir Dahan Inner circle Munich, Germany 1390 Posts  Posted: Jun 28, 2005 03:07 am 0 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. Adventures in ASIC digital design Jonathan Townsend Eternal Order Ossining, NY 27017 Posts  Posted: Jun 28, 2005 07:56 am 0 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 Special user St. Louis, MO 996 Posts  Posted: Jun 28, 2005 09:04 am 0 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 Special user St. Louis, MO 996 Posts  Posted: Jun 28, 2005 11:44 am 0 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)
 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 <   