Puzzles/Joy of n

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 Roger Hui, with further contributions by Andrew Nikitin.