Brain Teasers
Zeros and Ones
What is the smallest integer greater than 0 that can be written entirely with zeros and ones and is evenly divisible by 225?
Answer
The prime factorization of 225 is 5*5*3*3. So the answer will be both a factor of 25 and of 9.All multiples of 25 end in either 00, 25, 50, or 75. The only one of these composed of 0's and 1's is obviously 00, so the answer must end in 00. The hard part is finding a series of 0's and 1's preceding the 00 that will make the entire number divisible by 9.
If you didn't already know the following trick then this problem would be very hard. If you did know it then the problem was likely very easy. The trick is that if the sum of digits of a number is divisible by 9 then the number itself is also divisible by 9. Note that this is true for 3 also. For example the number 17685 is divisible by 9 because 1+7+6+8+5=27, and 27 is divisible by 9.
To prove this let's consider any five digit number, abcde. This number can be expressed as follows.
a*10000 + b*1000 + c*100 + d*10 + e = a*(9999+1) + b*(999+1) + c*(99+1) + d*(9+1) + e*1 = a*9999 + b*999 + c*99 + d*9 + a + b + c + d + e =
9*(a*1111 + b*111 + c*11 + d*1) + a + b + c + d + e .
9*(a*1111 + b*111 + c*11 + d*1) must be divisible by 9 because it is a factor of 9. So if a+b+c+d+e is also a factor of 9 then the entire number must be a factor of 9. Note also that the remainder of abcde/9 is the same as the remainder of (a+b+c+d+e)/9.
The smallest number consisting of all 1's and divisible by 9 is thus 111,111,111. Adding the two zeros at the end results in the answer to the problem: 11,111,111,100.
Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
If you write the integer in binary (base 2) instead of base 10, the smallest integer is 225 = 11100001
Well if you write the integer in base 225 then it would be 10 (if you insist that a zero must be used). Very interesting puzzle and well explained. I cannot believe the difficulty rating this puzzle currently has. There must be a lot of geniuses out there.
hard
Agree! It looked like a trick question and it seemed to shout binary! Maybe the question should have specified the number base.
Good teaser though!
Good teaser though!
Ooops! I meant I agreed woth gizzer and Limbo! Not that is was hard!
I got the solution in the same way it was given. I was going to be pissed though if the answer had been binary, which I thought of.
If this was a trick you could turn a 1 on its side to make a minus sign: 1000-100. (900=4*225).
To post a comment, please create an account and sign in.
Follow Braingle!