Brain Teasers
Multiple Divisors
Professor Abacus is looking for a number. The number must have 10 digits. It must contain all 10 numerals (0 through 9, once each). It must also be evenly divisible by all integers 2 through 18. Find one of the four possible solutions.
Answer
First, use prime factorization to determine the lowest common multiple (LCM).2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 * 2 * 2
9 = 3 * 3
10 = 2 * 5
11 = 11
12 = 2 * 2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2 * 2 * 2 * 2
17 = 17
18 = 2 * 3 * 3
LCM = 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 = 12252240.
The smallest 10-digit number that is a multiple of the LCM is 1004683680 (12252240 * 82). The largest 10-digit number that is a multiple of the LCM is 9997827840 (12252240 * 816). The solution must be somewhere between these two numbers.
To solve, multiply the LCM by each of the integers 82 through 816. The four solutions are:
2438195760 = 12252240 * 199
3785942160 = 12252240 * 309
4753869120 = 12252240 * 388
4876391520 = 12252240 * 398
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
cant you just keep adding the LCM again and again to get all the answers?
Repeatedly adding the LCM is the same as multiplying it by consecutively higher numbers - both work (and are a lot of work)! Nice C!
I gave it about 15 minutes trying too find a "smarter" solution (for instance, using the fact that the sums of odd and even digits of all numbers divisible by 11 differ by a factor of 11), but decided there wasn't one. No way I was going to sit there multiplying 700 pairs of numbers together.
Thank you Excel for your wonderful assistance in working this one out.
The only "shortcut" I could find was working out all the factors that would give me between 1,100,000,000 and 1,199,999,999, between 2.2*10^9 and 2.3*10^9, etc, and removing all of those initially, as if the first two digits are the same then it won't fit into the criteria, but that was only going to get rid of 70 or so.
Very curly. I like this teaser.
The only "shortcut" I could find was working out all the factors that would give me between 1,100,000,000 and 1,199,999,999, between 2.2*10^9 and 2.3*10^9, etc, and removing all of those initially, as if the first two digits are the same then it won't fit into the criteria, but that was only going to get rid of 70 or so.
Very curly. I like this teaser.
I tried to get somewhere helpful by realizing a few things, but eventually gave up due to the sheer massiveness of these numbers. Firstly - the divisibility of 3 and 9 will ALWAYS be there, as they depend on an addition rule, always satisfied (that is to say, any 10 digit number, using all digits 0-9 once will be divisible by both 3 and 9, no matter what).
Then, to be divisible by 10, it must end in zero, which also takes care of 2 and 5. Since it is divisible by both 2 and 3 (even and adds up to multiple of 3), then 6 is taken care of as well.
Ending in zero, divisible by 4 makes it end in 20, 40, 60, or 80.
The 8 rule left me with jsut enough possibilities to give up, though maybe I jsut got too lazy as the 8 rule, coupled with the ten rule and the 4 rule leaves um... 120, 160, 240, 280, 320, 360, 480, 520, 560, 640, 680, 720, 760, 840, 920, and 960. but from there, i wouldnt know where to begin, and i dont know the rules for any other number (though i jsut read the rule for 11 today, which is quite interesting, i find), and kinda gave up there. Any serious rules or help would be appreciated.
Then, to be divisible by 10, it must end in zero, which also takes care of 2 and 5. Since it is divisible by both 2 and 3 (even and adds up to multiple of 3), then 6 is taken care of as well.
Ending in zero, divisible by 4 makes it end in 20, 40, 60, or 80.
The 8 rule left me with jsut enough possibilities to give up, though maybe I jsut got too lazy as the 8 rule, coupled with the ten rule and the 4 rule leaves um... 120, 160, 240, 280, 320, 360, 480, 520, 560, 640, 680, 720, 760, 840, 920, and 960. but from there, i wouldnt know where to begin, and i dont know the rules for any other number (though i jsut read the rule for 11 today, which is quite interesting, i find), and kinda gave up there. Any serious rules or help would be appreciated.
Other than reducing the range to 85 to 806 I did it as the solution suggests using Excel. Only took a couple of minutes. (85 to 806 covers the 10 digit numbers from 1023456789 to 9876543210.)
After finding the answers I looked to see if there was something in common between the multiplier, but I don't see one.
After finding the answers I looked to see if there was something in common between the multiplier, but I don't see one.
I solved this puzzle using scip (a linear, mixed integer and nonlinear programming solver), using the following simple model.
set digits := { 0 .. 9 };
param numberLength := 10;
set numberDigits:= { 1 .. numberLength };
# numbers 2-9 are divisors of 10-18, so need not be taken into account
set divisors := { 10 .. 18 };
set NxD := numberDigits * digits;
var x[numberDigits] integer >=0 = 1;
subto tot: sum in numberDigits : x[i]*10^(numberLength-i) == num;
var z[NxD] binary;
subto c0: forall in numberDigits do sum in digits : z[i,d]*d == x[i];
# x_i = sum ( z_i_k * k ) 1
set digits := { 0 .. 9 };
param numberLength := 10;
set numberDigits:= { 1 .. numberLength };
# numbers 2-9 are divisors of 10-18, so need not be taken into account
set divisors := { 10 .. 18 };
set NxD := numberDigits * digits;
var x[numberDigits] integer >=0 = 1;
subto tot: sum in numberDigits : x[i]*10^(numberLength-i) == num;
var z[NxD] binary;
subto c0: forall in numberDigits do sum in digits : z[i,d]*d == x[i];
# x_i = sum ( z_i_k * k ) 1
For some unknown reason (probably having to do with maximum comment length restrictions) the model in my previous comment was truncated. I have uploaded it to pastebin.
http://pastebin.com/zXYBRcQR
http://pastebin.com/zXYBRcQR
To post a comment, please create an account and sign in.
Follow Braingle!