superprismatic

A Boggle-like Challenge

In the game, Boggle, a letter may have at most 8 adjacent letters.
That fact inspired this challenge.

This first part of this challenge is to place letters in such a way
that each letter of the alphabet has precisely eight other different
letters adjacent to it. You must use all 26 letters and, of course,
"adjacent" is a commutative relation. To specify your placement,
all you need to do is list the eight letters adjacent to A, the
eight letters adjacent to B, the eight letters adjacent to C,...,etc.
But remember that, if Q is on A's adjacency list, then A must be
on Q's adjacency list, and this is true for every pair of letters
-- not just A and Q.

The second part of the challenge is to create a cycle of all 26
letters, such that each adjacent pair of letters in the cycle are
adjacent in the sense of the first part of the challenge.

Note that there is no requirement that the graph of adjacent letters
is realizable in a small number of dimensions. So, trying to visualize
such a graph may be hazardous to your mental health!

If we have any 4-tuple of distinct real
numbers, there is a simple way to have
this determine a permutation on 4 things:
Just replace each number with its ranking
amongst the 4 numbers.  For example,
suppose I had the 4-tuple, (36,95,1,18).
By replacing each number with its rank,
I get the permutation (2,1,4,3).

I would like to be able to use 4 fair
dice to generate a permutation in this
way.  The dice would give me the 4-tuple
(each die would have its own spot in the
tuple) and I would use the ranks to
determine a permutation.  Of course, In
order to insure that I get 4 distinct
numbers, no die can have a number which
is on any other die. But it may be the
case that a paricular die has two or more
faces having the same value. The number
of faces on the dice may be any positive
integer (I'm assuming that fair dice can
always be made this way).  It is not
necessary that all of the dice have the
same number of faces.

Can you construct a set of 4 dice which
can produce all 24 permutations of 4
things, each with probability 1/24 ?
I have several such sets with 12 faces
on each die.  Can you find a set with
fewer total faces?

Find 11 common English words, each of
which is a subsequence of the string
PLUFIEMDATNGORPAPNLCHGE.  The words
are all related by their meanings.

As an example, IMPALE is a subsequence
since its letters occur, in sequence,
from left to right in the string
PLUFIEMDATNGORPAPNLCHGE. Unfortunately,
IMPALE isn't one of the words in the
answer to this puzzle.

I recently read an article in the American Mathematical Monthly,
August-September 2012, about straight line programs.  The article,
by Peter Borwein and Joe Hobart, was about how these things would be
affected by allowing the division operation.  But a rather simple idea
for a puzzle formed in my head after reading it.  So, here it is:

A straight line program is a sequence of integers p₁,p₂,p₃,....,p_n
such that p₁=1 and p_i is the sum, difference, or product of p_k and p_l
where k and l are both less than i. It is OK if k=l.  So, for example,
one possible straight line program which ends in 12 is 1,2,4,3,12.  To be
explicit, p₁=1, p₂=p₁+p₁, p₃=p₂+p₂, p₄=p₃-p₁, p₅=p₄*p₃.

Find a shortest straight line program ending in 137.

Below is a set of 10 related words which have been
encripted using a letter substitution code (as in a
standard cryptogram), and placed into the two small
crisscross grids shown. Four words read across and
six words read down. The object is to decode the
grids.

+TUI+T++
+O+PNOP+
+P+++P++
+++OUNOP
+++++O++
+++++P++

++C+Y
+HGRB
+++L+
+++B+

Here are two hints:

1. The longest word in the grid (TOPNOP), when decoded,
has a second meaning having nothing to do with the other
words in the grid. This other meaning could be expressed
as 1/2 NOPOBUOBU + 1/2 TOPOAEB. (These words are
encrypted with the same alphabet as the words in the grids.)
In a very different way, TOPNOP = 1/2 TOP + 1/2 YB.

2. If the 15 different letters that appear in the decoded
grid words and decoded hint words are placed in
alphabetical order and then reencrypted using the same
alphabet that they had been encrypted with before, they will
spell a 15-letter word that appears in the English Wiktionary.

Note on the origin of this puzzle:
This is very nearly a verbatim statement of a contest
on page 76 of the July, 2012 issue of GAMES magazine.
The deadline for entering this contest (July 31, 2012) has
passed.