Differences between revisions 11 and 12
 ⇤ ← Revision 11 as of 2006-06-01 05:05:54 → Size: 3103 Editor: RogerHui Comment: x. y. etc. ← Revision 12 as of 2008-12-08 10:45:54 → ⇥ Size: 3104 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 55: Line 55: methods similar to those for solving the [:Essays/N_Queens_Problem: n queens problem], methods similar to those for solving the [[Essays/N Queens Problem| n queens problem]], Line 106: Line 106: [[BR]] <
>

Posed by Jose Mario Quintana.

A few days ago while riding the train back from work I stumbled upon Scott Kim's The Joy of Six boggler in the July issue of the Discover magazine. There was a picture of six books numbered 1 2 3 4 5 6 on a shelf followed by the text:

"Six books sit side by side on a shelf. Put the books in order so that the sequence of the numbers on their spines satisfies the following conditions:

1. [Easy].

2. [Easy].

3. [Challenging] Rearrange the books yet again so that adjacent book numbers form two-digit numbers that cannot be divided by 3, 4 or 5. For instance, the order 1-2-3-4-5-6 fails on several counts: The two-digit number 12 divides evenly by 3 and 4; the number 45 divides evenly by 3 and 5; and 56 divides evenly by 4."

However, "challenging" depends whether or not one has J in a pocket (pc). Furthermore, one can define a general verb JoyOf=. ... so that JoyOf 6  solves, in particular, the puzzle above. A spoiler follows several lines below.

## Solution 0

```   test=.  -.@(0&e.)@,@(2: |~&.]/&3 4 5@".@(,"2)@:(":"0)\ ])

anagrams=. i.@! A. i.

JoyOf=. (test"1 # ])@(anagrams { >:@i.) f.

JoyOf
(-.@(0&e.)@,@(2: |~&.]/&3 4 5@".@(,"2)@:(":"0)\ ])"1 # ])@((i.@! A. i.) { >:@i.)

JoyOf 6
5 3 1 4 6 2```

However, to continue the sequence,

```   (#@JoyOf"0) 2 3 4 5 6 7 8 9
0 1 2 0 1 2 30 208```

one would require a different approach...

## Solution 1

The puzzle can be solved effectively using methods similar to those for solving the n queens problem, which is also a problem of selecting permutations of order n satisfying particular properties.

For example, for n=:9 , it is obvious that

1 2 ...

is not going to work (12 is divisible by 3 and 4; queens on (1,1) and (2,2) would attack each other), but there are !7 permutations beginning with 1 2, and it is wasteful to generate all of them only to discard them.

```J2=: 4 : 0
t=. 1+(n,n)#:i.*:n=.y
t #~ (~:/"1 t) *. *./ 0 ~: (,x) |/ -.&' '"1&.": t
)

JoyOf1=: 3 4 5&\$: : (4 : 0)
n=. y
if. 2>n do. i.0,n return. end.
t=. x J2 n
x=. ((~.{."1 t)i. i.1+n) { (</./|:t),a:
for. i.n-2 do.
t=. t ((#&>@] # [) ,. ;@]) ({:"1 t){x
t=. t #~ *./@~:"1 t
end.
t
)```

This version accepts a left argument of the divisors (3 4 5 are used if the left argument is elided). It builds the solution one column at a time, starting with 2 columns. The new column uses only those values that, when combined with the last existing column, would not form multiples of the divisors. Then rows with duplicate entries are removed.

## Solution 2

For N>9 soltion is given by

`JoyOfGreaterThan9=:[: i. 0: , ]`

Proof: for any permutation either 10 or 5 is not in the leftmost position, there fore 10 #.n 10 or 10 #. n 5 is divisble by 5

So, the sequence above extends to

`0 1 2 0 1 2 30 208 0 0 0 0 0 ....`

Contributed by RogerHui, with further contributions by AndrewNikitin.

Puzzles/Joy of n (last edited 2008-12-08 10:45:54 by anonymous)