Differences between revisions 9 and 10
 ⇤ ← Revision 9 as of 2006-06-01 05:07:14 → Size: 1959 Editor: RogerHui Comment: x. y. etc. ← Revision 10 as of 2008-12-08 10:45:53 → ⇥ Size: 1959 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 3: Line 3: Find a 9-digit number [[latex(\$a_1a_2\dots a_9\$)]],containing all the digits 1,2,...,9, such that [[latex(\$k\$)]] divides[[latex(\$a_1a_2\dots a_k\$)]] for each [[latex(\$k=1,2,\dots 9\$)]]. Find a 9-digit number <>,containing all the digits 1,2,...,9, such that <> divides<> for each <>. Line 9: Line 9: Since 5 divides [[latex(\$a_1a_2a_3a_4a_5\$)]], [[latex(\$a_5\$)]] must be 5.Similarly [[latex(\$a_k\$)]] must be even for even [[latex(\$k\$)]] and by elimination [[latex(\$a_1\$)]], [[latex(\$a_3\$)]], [[latex(\$a_7\$)]] and [[latex(\$a_9\$)]] Since 5 divides <>, <> must be 5.Similarly <> must be even for even <> and by elimination <>, <>, <> and <> Line 53: Line 53: [[BR]] <
>

Find a 9-digit number , containing all the digits 1,2,...,9, such that divides for each .

Solution

Since 5 divides , must be 5. Similarly must be even for even and by elimination , , and must be the remaining digits 1, 3, 7 and 9 in some order. Candidate solutions thus have the form oeoe5eoeo where o=odd, e=even.

From this point it's not too difficult to reduce the candidates to a unique solution; here is how one might use J:

oe=: (i.24)&A.&> 1 3 7 9; 2 4 6 8   NB. permuted odds and evens
a0=: 5 ,. ,/ ,"1// oe               NB. proto-candidates (5ooooeeee)
a =: 1 5 2 6 0 7 3 8 4 {"1 a0       NB. candidates (oeoe5eoeo)
ok=: 0 = (# | 10&#.)\"1 a           NB. 0 remainders in all prefixes
(*./"1 ok) # a                      NB. solution
3 8 1 6 5 4 7 2 9

Still using the same oeoe5eoeo idea, but building the solution one column at time:

nd    =: 0 1 0 1 2 1 0 1 0 { 1 3 7 9 ; 2 4 6 8 ; ,5
ext   =:  [: ,/ ] ,."2 0 {:@\$ {:: nd"_
ok    =: *./@~:"1 *. 0: = {:@\$ | 10&#.
extend=: (ok # ]) @ ext

extend^:9 i.1 0
3 8 1 6 5 4 7 2 9

Initially, there is 1 solution of 0 columns. i{::nd are the digits to use when the current solution has i columns, and ext appends each of these digits to each row of the current solution. ok indicates the valid rows -- unique digits and divisible by i+1 .

The method keeps the number of rows small, and therefore might be the method to use if one were to solve the problem by hand (with only pencil and paper).

3 : '# extend^:y i.1 0'"0 i.10
1 4 16 20 30 30 20 8 1 1

Contributed by RogerHui and EwartShaw.

Puzzles/Div9 (last edited 2008-12-08 10:45:53 by anonymous)