Question 1182820: All the digits of the positive integer N are either 0 or 1. The remainder after dividing N by 37 is 18. What is the smallest number of times that the digit 1 can appear in N?
Answer by greenestamps(13200)   (Show Source):
You can put this solution on YOUR website!
Previously answered; response copied here.
--------------------------------------------------------------------
The requirements of the problem are that an integer N must contain only digits 0 and 1, and that N leave remainder 18 when divided by 37 - i.e., N-18 is a multiple of 37, or mod(N-18,37)=0.
The analysis below will allow us to find as many integers as we want that satisfy the conditions. An assertion will be made -- but not formally proved -- that the minimum number of 1's in the number is 5.
To analyze the problem, we know that the value of an integer mod 37 is the sum of the values mod 37 of the digits in each place in the number. If the only non-zero digits are 1’s, then the value of the integer mod 37 is the sum of the mod 37 values of the place values where the 1’s are.
So we find the pattern in the mod 37 values of the place values - i.e., the mod 37 values of the powers of 10.
mod(10^0,37) = 1
mod(10^1,37) = 10
mod(10^2,37) = 26
mod(10^3,37) = 1
We see that the mod 37 values of the place values in base 10 follow a pattern with a cycle of length 3.
So let’s write our number N with the digits grouped in groups of 3, just as we often do when writing large numbers in base 10. E.g., a number might look like this: BC,ABC,ABC,ABC,ABC,ABC,ABC,ABC.
Then a 1 in any “C†place will have a mod 37 value of 1; a 1 in any “B†place will have a mod 37 value of 10; and a 1 in any “A†place will have a mod 37 value of 26. And of course the 0’s in all the other places have a mod 37 value of 0.
We want our numbers N to be equal to 18 mod 37, so we can look for linear combinations of 1, 10, and 26 that are equal to 18 mod 37.
There is no linear combination of 1, 10, and 26 that is equal to 18.
Add 37 to 18 and we need linear combination(s) that sum to 55.
This we can do: 2(26)+3(1)=55.
That means any number with 2 1’s in the “A†places and 3 1’s in the “C†places will leave a remainder of 18 when divided by 37.
The smallest such number is N = 1,101,101; checking verifies that N-18 =1,101,083 is divisible by 37.
But there are obviously an infinite number of other numbers that have 1’s in two “A†places and in 3 “C†places:
N = 1, 001,001,100,100
N = 1,000,000,000,100,100,000,001,001
etc.
Again calculation shows that for each of those numbers N-18 is divisible by 37.
Finally, in the context of the problem, note that in any of these numbers the number of 1's is 2+3=5.
So we had no linear combinations of 1, 10 and 26 adding to 18; then we had one linear combination of 1, 10, and 26 adding to 18+37=55. Next we look for linear combinations of 1, 10, and 26 adding to 55+37=92.
There are (at least) two:
2(26)+4(10)=92
3(26)+1(10)+4(1)=92
The first of these linear combinations means any number with 1's in 2 "A" positions and 4 "B" positions will be an N that satisfies the conditions of the problem -- e.g.
10,010,011,011
Obviously for any number like that, the number of 1's in the number is 2+4=6.
The second of these linear combinations means any number with 1's in 3 "A" positions, 1 "B" position, and 4 "C" positions will be another number that satisfies the conditions of the problem. The smallest such number is
1,101,101,111.
Obviously in any number of this form the number of 1's will be 3+1+4=8.
So we have found ways to find an unlimited number of numbers N with 5, 6, or 8 1's that satisfy the conditions of the problem. I did not find any with 7 1's, or any with less than 5 1's. And there undoubtedly numbers N that satisfy the conditions of the problem that have more than 8 1's.
In the end, the answer -- although not formally proved -- is that the minimum number of 1's in the numbers that satisfy the conditions of the problem is 5.
|
|
|
