Xtykutl

Each of the letters of the word PALINDROME is assigned a different integer value between 0 and 9, for a total value for the word of 45. With the same value for each of the letters, the values of the letters in the eleven words below are all different. Moreover, the eleven words have been organized from left to right in increasing order of value (thus NAIL has the greatest value).

DRIP
PAIN
LIME
MEAL
DROP
DINE
RIND
LIAR
LORE
LEAD
NAIL

What was the value assigned to each of the letters of PALINDROME?

The solution is

$$ P=0,, A=5, ,L=9, , I=4, ,N=6, , D=7, , R=3, , O=8, , M=1, , E=2 $$ $$ PALINDROME = 0594673812 $$

Reasoning

Each word takes a different value and the words are ordered left to right. This means, for example, that $$PAIN + 8 < NAIL Rightarrow P+8 < LRightarrow P=0, ,L=9$$ $$MEAL +5 < LEAD Rightarrow M + 5 < D Rightarrow D>6 Rightarrow DRIP > 9$$ In fact, since $E < R$ and $M < D-5$ the smallest value that $DRIP$ can attain is $13$. $$DROP > DRIP + 3 Rightarrow O > I + 3 Rightarrow I < 5$$ This means that $NAIL$ can be at most $28$. In fact, we also observe that since $D>6$ and $O > I+3$ this further restricts the maximum value of $NAIL$ to be $24$. Since the words all have distinct values and are ordered left to right, we must have $DRIP + 9 < NAIL$.

If we set $DRIP=13$, we quickly find that $NAIL < 23$ (a contradiction) so it must be that $DRIP=14$ which forces $NAIL=24$. From there, the value of each word is fully determined and the corresponding letters that work are $$ P=0,, A=5,, L=9,, I=4,, N=6,, D=7,, R=3,, O=8,, M=1,, E=2 $$

As a start (partial answer):

One-letter conclusions:
$L+I+M+E<M+E+A+L$ so $I<A$
$D+R+I+P<D+R+O+P$ so $I<O$
$D+R+I+P<R+I+N+D$ so $P<N$
$M+E+A+L<L+E+A+D$ so $M<D$
$L+I+A+R<N+A+I+L$ so $R<N$
$D+I+N+E<R+I+N+D$ so $E<R$
$D+R+O+P<R+I+N+D$ so $O+P<I+N$. Logically, $I<O$ so $P<N$ (as was already known) and $O-I<N-P$ (which may prove useful)

More observationally:

L seems to have a high value (it's in the last four and only one other one besides) and M seems to have a low value (it's only in two words on the low end of the scale)

There is exactly one solution to this problem:

P=0, A=5, L=9, I=4, N=6, D=7, R=3, O=8, M=1, E=2

I didn't solve this deductively, but by using linear algebra. I realize this sort of defeats the intention of such a puzzle, but it was an interesting algebra and programming challenge nonetheless.

All the code below was used in GNU Octave (similar to MATLAB).

First, I represent each of the words as a vector to map which letters belong to the words.

#       p a l i n d r o m e

DRIP = [1 0 0 1 0 1 1 0 0 0]

PAIN = [1 1 0 1 1 0 0 0 0 0]

LIME = [0 0 1 1 0 0 0 0 1 1]

MEAL = [0 1 1 0 0 0 0 0 1 1]

DROP = [1 0 0 0 0 1 1 1 0 0]

DINE = [0 0 0 1 1 1 0 0 0 1]

RIND = [0 0 0 1 1 1 1 0 0 0]

LIAR = [0 1 1 1 0 0 1 0 0 0]

LORE = [0 0 1 0 0 0 1 1 0 1]

LEAD = [0 1 1 0 0 1 0 0 0 1]

NAIL = [0 1 1 1 1 0 0 0 0 0]

I don't actually use the above vectors, but instead put all 11 words into one matrix:

words = [[1 0 0 1 0 1 1 0 0 0]

         [1 1 0 1 1 0 0 0 0 0]

         [0 0 1 1 0 0 0 0 1 1]

         [0 1 1 0 0 0 0 0 1 1]

         [1 0 0 0 0 1 1 1 0 0]

         [0 0 0 1 1 1 0 0 0 1]

         [0 0 0 1 1 1 1 0 0 0]

         [0 1 1 1 0 0 1 0 0 0]

         [0 0 1 0 0 0 1 1 0 1]

         [0 1 1 0 0 1 0 0 0 1]

         [0 1 1 1 1 0 0 0 0 0]];

I generate a 10! x 10 matrix that represents all permutations of the letter values [0..9]. This large of a matrix took up about 290 MB of memory (no sweat for a modern computer).

lettervalues = perms([0,1,2,3,4,5,6,7,8,9]);

I compute all word values for all 11 words for all letter value permutations. (This is a 10! x 11 matrix.)

wordvalues =  lettervalues * words';

I define a 10x11 matrix to help computing the difference in word value for neighboring words.

difference = [[-1  1  0  0  0  0  0  0  0  0  0]

              [ 0 -1  1  0  0  0  0  0  0  0  0]

              [ 0  0 -1  1  0  0  0  0  0  0  0]

              [ 0  0  0 -1  1  0  0  0  0  0  0]

              [ 0  0  0  0 -1  1  0  0  0  0  0]

              [ 0  0  0  0  0 -1  1  0  0  0  0]

              [ 0  0  0  0  0  0 -1  1  0  0  0]

              [ 0  0  0  0  0  0  0 -1  1  0  0]

              [ 0  0  0  0  0  0  0  0 -1  1  0]

              [ 0  0  0  0  0  0  0  0  0 -1  1]];

Next, I compute the word value differences between every neighboring pair of words
(makes a 10! x 10 matrix)

wordvaluedifferences = wordvalues * difference';

For each row of word value differences where all the differences are positive, show us the corresponding letter values. This will give us ALL solutions. In our case, there is one and only one solution.

lettervalues(all(wordvaluedifferences > 0, 2), :)

ans =

0 5 9 4 6 7 3 8 1 2