wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> A Digital Puzzle
        
(Message started by: K Sengupta on May 3rd, 2006, 12:47am)
Title: A Digital Puzzle
Post by K Sengupta on May 3rd, 2006, 12:47am
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 A1A2A3A4A5A6A7A8 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 ?
Title: Re: A Digital Puzzle
Post by Icarus on May 3rd, 2006, 6:24pm
On general principles, and without actually checking, I would guess that the answer to the first is [hide]    1  [/hide], and the answer to the second is [hide]   9   [/hide].
Title: Re: A Digital Puzzle
Post by Barukh on May 4th, 2006, 12:54am
I tried to check Icarus's claim without using the computer. For the first question, I got [hide]38165472, which seems to be the only solution[/hide].

:-/
Title: Re: A Digital Puzzle
Post by towr on May 4th, 2006, 2:31am
[hide]it is in fact the only solution (in base 10) to both questions[/hide]
Title: Re: A Digital Puzzle
Post by SMQ on May 4th, 2006, 5:58am
And, in fact, [hide]appending the digits 9 and 0 leads to the only related solution in 10 unique digits[/hide].

--SMQ
Title: Re: A Digital Puzzle
Post by Icarus on May 4th, 2006, 8:19pm
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.
Title: Re: A Digital Puzzle
Post by Sjoerd Job Postmus on May 20th, 2006, 2:15am
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.
Title: Re: A Digital Puzzle
Post by towr on May 20th, 2006, 2:43am

on 05/20/06 at 02:15:21, 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.
Title: Re: A Digital Puzzle
Post by Sjoerd Job Postmus on May 20th, 2006, 6:27am
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 8), this means that the last three digits are 0 (mod 8)

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
Title: Re: A Digital Puzzle
Post by towr on May 21st, 2006, 2:30pm
Nicely done!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board