Author |
Topic: A Digital Puzzle (Read 573 times) |
|
K Sengupta
Senior Riddler
Gender: 
Posts: 371
|
 |
A Digital Puzzle
« on: May 3rd, 2006, 12:47am » |
 Quote  Modify
|
Determine the total number of positive eight digit integers possessing the form A1A2A3A4A5A6A7A8 constituted by using the digits 1, 2, 3, 4, 5, 6, 7 and 8 once each such that the number A1A2....Ak is divisible by k, for 1<=k<=8.
What would be the total number of positive eight digit integers possessing the form A1A2A3A4A5A6A7 A8 constituted by using exactly 8 distinct digits out of the digits 1, 2, 3, 4, 5, 6, 7, 8 and 9 once each such that the number A1A2....Ak is divisible by k, for 1<=k<=8 ?
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A Digital Puzzle
« Reply #1 on: May 3rd, 2006, 6:24pm » |
Quote Modify
|
On general principles, and without actually checking, I would guess that the answer to the first is 1 , and the answer to the second is 9 .
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A Digital Puzzle
« Reply #2 on: May 4th, 2006, 12:54am » |
Quote Modify
|
I tried to check Icarus's claim without using the computer. For the first question, I got 38165472, which seems to be the only solution.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Digital Puzzle
« Reply #3 on: May 4th, 2006, 2:31am » |
Quote Modify
|
it is in fact the only solution (in base 10) to both questions
|
| « Last Edit: May 4th, 2006, 2:32am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Digital Puzzle
« Reply #4 on: May 4th, 2006, 5:58am » |
Quote Modify
|
And, in fact, appending the digits 9 and 0 leads to the only related solution in 10 unique digits.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A Digital Puzzle
« Reply #5 on: May 4th, 2006, 8:19pm » |
Quote Modify
|
My reasoning, for what it's worth: There are 8! digit combinations. Half of those have the first two digits divisible by 2, 1/3 of those (approximately) should have the first 3 digits divisible by 3, 1/4 of those should satisfy the 4 digit condition, etc.
So in the end there should be 8!/(1*2*3*4*5*6*7*8) = 1 solution that satisfies all the conditions.
For the second problem, the reasoning is the same, but now you end up with 9!/8! = 9 solutions.
As you can see, it is not solid enough to give an exact number, but it should be in the right neighborhood.
|
| « Last Edit: May 4th, 2006, 8:26pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: A Digital Puzzle
« Reply #6 on: May 20th, 2006, 2:15am » |
Quote Modify
|
Let me consider this problem too.
Let's call the 8-digit number A.
If A is dividable by 1, by 2, by 3, .. 8, then it must be dividable by the lowest common multiple of 1..8.
Let us find the lowest common multiple. It must be greater than 8.
First: Prime-factor the number, giving
1: ignored, because M * 1 = M
2: 21
3: 31
4: 22
5: 51
6: 21 * 31
7: 71
8: 23
Find the highest power of each prime.
2: 23
3: 31
5: 51
7: 71
So the number 23 * 31 * 51 * 71 should be dividable by 1, by 2, etc. Simple calculation proves it right! My assumption is this number is the smallest one, but I can not prove it yet. It should be, though.
The resultant number should thus be a multiple of 840. Since we can't use 0, this leaves ourselves with a problem. Not doable.
Or have I mis-interpreted the question?
The same logic goes for the second question, leaving us with no answer.
|
| « Last Edit: May 20th, 2006, 2:20am by Sjoerd Job Postmus » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Digital Puzzle
« Reply #7 on: May 20th, 2006, 2:43am » |
Quote Modify
|
on May 20th, 2006, 2:15am, Sjoerd Job Postmus wrote:| Or have I mis-interpreted the question? |
|
Yes. You aren't supposed to take the 8 digit number at all stages. Just the number formed by the first two digits need to be divisible by 2, the one formed by the first three by 3, etc.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: A Digital Puzzle
« Reply #8 on: May 20th, 2006, 6:27am » |
Quote Modify
|
Ok, so I was mistaken.
What can we deduce?
A2
A4
A6
A8
must all be even. (A1 + A2 must be divisable by 2), etc.
So, from which follows:
A1
A3
A5
A7
must be odd.
Ok, let's ignore A1 for the moment 
Let's examine, modulo 3, the first 3 digits
A1A2A3
A2 can have four different values: 2, 4, 6 and 8.
Modulo 3, 2 and 8 are equal.
2 and 8 are both -1 (mod 3)
4 is 1 (mod 3)
6 is 0 (mod 3)
Ok, let us first take 2 or 8... and see what this means for a1 + a3 (mod 3)
A1 + A3 has to be 1 (mod 3) (which would be 1, 4, 7, 10, 13)
We only have to look at the even numbers ( sum of two odd)
(4, 10)
4: 1, 3
10: 3,7 7,3
Situation: 4 (1 mod 3)
A1 + A3 has to be -1 (mod 3)
So, it would be: (8, 14)
8: 1,7 3,5 5,3 7,1
14: 9+5 or 7+7, can't have either
Situation: 6 (0 mod 3)
A1 + A3 has to be (0 mod 3)
So: (6, 12)
6: 1,5 3,3 5,1
12: 5,7 7,5
Which limits the possibilites for none of the above yet
A4: Must be even: 2, 4, 6, 8
A3A4 must be divisable by 4.
12, 32, 52, 72: Can be.
24, 44, 64, 84: Can't
16, 36, 56, 75: Can
28, ... 88: Can't
So that limits A4 to: (2, 6)
A1A2A3A4A5: Needs to be divisable by 5... From which follows: A5 = 0 OR A5 = 5... Can't be 0, so it must be 5.
Let's re-cap
A1: 1, 3, 7
A2: 2, 4, 6, 8
A3 1, 3, 7
A4: 2, 6
A5: 5
A6: No Info Yet
A7: No Info Yet
A8: No Info Yet
Let's look at what we have deduced before.
Consider A2 = 6
Situation: 6 (0 mod 3)
A1 + A3 has to be (0 mod 3)
So: (6, 12)
6: 1,5 3,3 5,1
12: 5,7 7,5
We can't use 5, or doubles. This eliminates A2 = 6
Ok, let's look at A8...
If n = 0 (mod  , this means that the last three digits are 0 (mod
So, we only have to search:
A6 = 2, 4, 6, 8
A8 = 2, 4, 6, 8
Which gives us: 4 * 3 * 3 = 36 combinations to search!
Doable by hand, but then again, why would we? Because it's fun!
Because A6 = 2, 4, 6 or 8, we just test if 200, 400, 600 and 800 are divisable by 8, which they all are.
So we only have to look at the last two digits, which limits us to 12 combinations! Only looking at the multiples of 8, leaves:
1,6
3,2
7,2
Notice I left out 5,6: 5 is already used.
A4 AND A8 have merely 2,6. If A4 is 2, A8 has to be 6, and vica-versa. Eliminate them from the others.
A1: 1, 3, 7
A2: 4, 8
A3: 1, 3, 7
A4: 2, 6
A5: 5
A6: 4, 8
A7: 1, 3, 7
A8: 2, 6
Well... Taking into account dependencies:
A1 can have 3 values
A2 can have 2 values
A3 can have 2 values (One already taken at A1)
A4 can have 2 values
Multiply: 3 * 2 * 2 * 2 = 24. Only 24 possibilities left
We could even hand-search these... Eliminating could be done very quickly, I hope...
Let A1 = 1 and A2 = 4
A1A2A3 = 143, 147
Only 1 of these is divisable by 3.
1472
1476
Both can be divided At this stage, the remaining part of the number is fixed for this.
14725836 Which is not dividable by 8
14765832 Which is not dividable by 7
We found the number was fixed after only two choices.
Let's change our next choices:
18 The next number must be 3
183 The question: 2 or 6?
18325
18365
Finish the number off
18325476 Not divisable by 8
18365472 Not divisable by 7
Ok, so A1 can not be 1. So it must be 3 or 7... We have only tried 4 things so far.
341 and 347 aren't dividable
381
387
2 or 6?
3812
3816
1872
1876
The numbers are fixed now
381254 : Error, not divisable by 6
38165472 Works
387254 : Error, not divisable by 6
3876541 : Error, not divisable by 7
Ok... So we have tried a few...
A1 = 1 failed... A1 = 3 works, but only for A = 3816547
Let's try A1 = 7
741
783
2, or 6 Both work for both!
7412583 Error: not div' by 7
741658 Error: Not div' by 6
783254 Error: Not div' by 6
783654 Error: Not div' by 7
So, we have eliminated A1 = 1 and A1 = 7... Leaving A1 = 3, with only one valid option...
So, 38165472 is the only valid number A.
Mere logic, and a bit of trial-and error, but no PC-search
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print