Skip to content

Three Combinatoric Puzzles

by Roger K.W. Hui

Vector 9:2, page 139

programming techniques mathematics and statistics competitions and puzzles

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 139

1. Being involved in the development of a programming language has its rewards, none more pleasant than receiving gems like the following (EEM is Eugene E. McDonnell):

No. 6122659 filed 2.13.00 Sun 5 Apr 1992
From EEM
To KEI RHUI
Subj Josephus Problem

With n people numbered 1 to n in a circle, every second one is eliminated until only one survives. For example, for n=10, the elimination order is 2 4 6 8 10 3 7 1 9, so 5 survives.

The problem: Determine the survivor’s number J(n).

J=.1&|.&.#:

Try J"0 i.50 for a nice pattern to emerge.
See also Graham et al, Concrete Mathematics, Section 1.3.

J can be derived by observing that:

   ] y=.2^?10$10
2 128 16 32 4 1 64 64 512 8
   J"0 y
1 1 1 1 1 1 1 1 1 1
   ] y=.>:?10$1000
520 831 35 54 530 672 8 384 67 418
   (J"0 >:y) - J"0 y
2 2 2 2 2 2 2 2 2 2

That is, J 2^y is 1, and (J 1+y)-J y is 2 if 1+y is not a power of 2. As McDonnell asserts, the pattern is made evident by applying J to the first few integers:

   >:i.5 10                          J"0 >:i.5 10
 1  2  3  4  5  6  7  8  9 10        1  1  3  1  3  5  7  1  3  5
11 12 13 14 15 16 17 18 19 20        7  9 11 13 15  1  3  5  7  9
21 22 23 24 25 26 27 28 29 30       11 13 15 17 19 21 23 25 27 29
31 32 33 34 35 36 37 38 39 40       31  1  3  5  7  9 11 13 15 17
41 42 43 44 45 46 47 48 49 50       19 21 23 25 27 29 31 33 35 37

The statement of J in J is interesting in its own right. 1&|.&.#: is in the form f&.g, defined as follows:

f  &.g  y      is      g^:_1 f   g y
1&|.&.#: y     is      #.    1&|. #: y

That is, convert to the binary representation (#:), rotate by one (1&|.), and invert by computing the binary value (#.).

As a matter of historical interest, binary representation and binary value (denoted by the monads ⊤ and ⊥) were once defined in APL (see Falkoff, Iverson, and Sussenguth [1964]), but were later removed due to space limitations. Such draconian measures are understandable; at the time, APL was running on a S/360 Model 50 with 256 Kbytes of main storage (nevertheless supporting 24 users simultaneously with sub-second response).

2. Compute the ((2^n),n) sorted table of the n-bit binary numbers.

bin0 =. #&2 #: i.@(2&^)
bin1 =. (1 0&$)`((0&,. , 1&,.)@$:@<:) @. *
grow =. 0&,. , 1&,.
bin2 =. 'grow^:y.i.1 0' : ''

bin0 exploits the fact that encode (#:) does almost exactly what is required. bin0 is a fork:

(#&2 #: i.@(2&^)) n
(#&2 n) #: i.@(2&^) n
(n#2) #: i.2^n

If 0<n, bin0 can be simplified to #:@i.@(2&^).

bin1 is recursive: n-bit numbers are formed by prefacing (n-1)-bit numbers by 0 and by 1. Agenda (@.) applies signum (*) to the argument, and selects 1 0&$ or (0&,. , 1&,.)@$:@<: for execution according to whether the result is 0 or 1. The word $: denotes self-reference.

   ] t=.bin1 2          0&,. t            1&,. t
0 0                  0 0 0             1 0 0
0 1                  0 0 1             1 0 1
1 0                  0 1 0             1 1 0
1 1                  0 1 1             1 1 1

   (0&,. t),(1&,. t)            (0&,. , 1&,.) t
0 0 0                        0 0 0
0 0 1                        0 0 1
0 1 0                        0 1 0
0 1 1                        0 1 1
1 0 0                        1 0 0
1 0 1                        1 0 1
1 1 0                        1 1 0
1 1 1                        1 1 1

bin2 uses the same idea as bin1, but replaces recursion by explicit definition (:) and the power conjunction (^:). That is:

bin2 n
'grow^:y.i.1 0':'' n
grow^:n i.1 0
grow grow ... grow i.1 0

Generating Gray codes is a minor variation on generating binary numbers: Given n, compute the ((2^n),n) table of the n-bit Gray codes, with each row differing from a neighbour by one bit. As with the binary numbers, Gray codes can be generated in many ways; the following algorithm illustrates that it is a reflected code. Note the use of |. (reverse), and compare with bin1.

gray =. (1 0&$)`((0&,. , 1&,.@|.)@$:@<:) @. *
gray 0       gray 1      gray 2      gray 3
             0           0 0         0 0 0
             1           0 1         0 0 1
                         1 1         0 1 1
                         1 0         0 1 0
                                     1 1 0
                                     1 1 1
                                     1 0 1
                                     1 0 0

The same general strategy can be used to compute the following enumerations:

  • all size m combinations of i.n
  • all size m compositions of i.n
  • all permutations of i.n
  • all self-upgrading permutations of i.n
  • all self-downgrading permutations of i.n
  • all size m partitions of n
  • all partitions of n

3. Ackerman’s function is defined on the non-negative integers as follows:

ack =. c1`c1`c2`c3 @. (#.@(,&*))
c1=. >:@]                        NB. 1+y
c2=. <:@[ ack 1:                 NB. (x-1) ack 1
c3=. <:@[ ack [ ack <:@]         NB. (x-1) ack x ack y-1

   2 ack 3                   3 ack 2
9                         29

In the definition of ack, the phrase #.@(,&*) computes the base-2 value (#.) of the catenated signs of the arguments (,&*), and the resultant number is used to select c1, c2, or c3 for execution.

Lemma: If x ack y is f&.(3&+) y, then (x+1) ack y is f^:(1+y)&.(3&+) 1.

Proof: By induction on y.

(x+1) ack 0                              Basis
x ack 1                                  Definition
f&.(3&+) 1                               x&ack
f^:(1+0)&.(3&+) 1                        ^:

(x+1) ack y                              Induction
x ack (x+1) ack y-1                      Definition
f&.(3&+) (x+1) ack y-1                   x&ack
f&.(3&+) f^:(1+y-1)&.(3&+) 1             Inductive Hypothesis
_3&+ f 3&+ _3&+ f^:(1+y-1) 3&+ 1         &.
_3&+ f f^:(1+y-1) 3&+ 1                  +
_3&+ f^:(1+y) 3&+ 1                      ^:
f^:(1+y)&.(3&+) 1                        &.         QED

Using the lemma (or otherwise), it can be shown that:

0&ack =  >:&.(3&+)                       NB.  >:
1&ack = 2&+&.(3&+)                       NB.  2&+
2&ack = 2&*&.(3&+)                       NB.  3&+@(2&*)
3&ack = 2&^&.(3&+)
4&ack = ^/@(#&2)&.(3&+)
5&ack = '^/@(#&2)^:(1+y.)&.(3&+) 1' : ''

References

[1] Graham, R.L., D.E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, Section 1.3.

[2] Falkoff, A.D., K.E. Iverson, and E.H. Sussenguth, A Formal Description of System/360, IBM Systems Journal, Volume 3, Number 3, 1964, Table 1, page 200-201.