Zeros and Ones
Math brain teasers require computations to solve.
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
Back to Top
 

Follow Braingle!