Musical Chairs Cipher: Intermediate

Question

This question is a continuation of the first question: Musical Chairs Cipher.

The basic rules:

Six children -- Alice, Ben, Carl, Denise, Eddie, and Flo -- are playing a game of musical chairs in class. On each of the five chairs is written a seven letter word.

The children start out in alphabetical order, and maintain that same order through the whole game. At the end of each round, each person sits in a chair, except for one, who is out.

Then, each of the sitting children scribbles out the word on their chair, in its place writing the same word under a vigenere cipher, using their name as the key.

One chair is then removed before resuming the game, which continues until there is only one person left. When removed, the word written on the chair is no longer changed. The final chair's word is still changed by the winner.

So Alice, Bob, Carl, Denise, Eddie, and Flo are going to play another round of musical chairs in class when they are approached by Greg, Hillary, and Ivan, all of them wanting to play as well.

Greg, Hillary, and Ivan are not nearly as well behaved as the rest of the children, so while the others stay in the same alphabetical order through the whole game, they instead are hopping, pushing, and running all around the circle, constantly changing their positions between rounds. Other than that, they follow all the same rules as the rest.

Their teacher, not wanting to leave anyone out of the game, brings in three more chairs and writes up some more words, but she doesn't check to make sure they are the same length as the others.

If the game began with the words:

CHEDDAR
FONTINA
MUNSTER
HAVARTI
RICOTTA
ASIAGO
STILTON
PROVOLONE

And ended with:

UDPCGUU
ZCDUGQT
CZBPNZI
ORWSYFM
YQNZTKY
CRUSHF
BOZZRJU
CQSBQKIPB

What order did the children get out, and who won?

NOTE: I will accept code-based answers, but I expect a bit more than brute force.

Answer 1

Let's begin by seeing what each chair has changed by over all the rounds it was involved in, by de-Vigenere-ing its final state using its initial state as key. We get, in order:

SWLZDUD
UOQBYDT
QFOXUVR
HRBSHME
HILLARY
CZMSBR
JVROYVH
NZEGCZUCX

We can already see that

the first chair to be removed was RICOTTA, and Hillary sat in it in the first round.

But let's take a different approach.

If we "add" (the first six letters of) all the chairs' deltas, we get 1 of one child's name + 2 of another's + ... + 8 of another's. (Whichever child was eliminated first doesn't appear at all.) Each of those six letters gives us one linear relation, mod 26, between the numbers of times the children appear; e.g., if those numbers are $c_i,\dots,c_9$ for children A..I then the first letter is $c_1A+\cdots+c_9I$, the second is $c_1L+\cdots+c_9V$, etc. We also know that the sum of the numbers $c_1+\cdots+c_9$ is just $1+\cdots+8=36$. So we have seven linear relations between nine numbers. That leaves a relatively small space to search. I happen to have used Mathematica for this, but it could be done without: it's basically just linear algebra (with the slight complication that we're working to a non-prime modulus, but that doesn't hurt too much).

So:

Add up all the deltas. Convert names and deltas to numbers. The equations described in the paragraph above look like this (in Mathematica's input language):
Reduce[{c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8 + c9 == 36,
0 c1 + 1 c2 + 2 c3 + 3 c4 + 4 c5 + 5 c6 + 6 c7 + 7 c8 + 8 c9 == 14,
11 c1 + 4 c2 + 0 c3 + 4 c4 + 3 c5 + 11 c6 + 17 c7 + 8 c8 + 21 c9 == 7,
8 c1 + 13 c2 + 17 c3 + 13 c4 + 3 c5 + 14 c6 + 4 c7 + 11 c8 + 0 c9 == 8,
2 c1 + 1 c2 + 11 c3 + 8 c4 + 8 c5 + 5 c6 + 6 c7 + 11 c8 + 13 c9 == 12,
4 c1 + 4 c2 + 2 c3 + 18 c4 + 4 c5 + 11 c6 + 6 c7 + 0 c8 + 8 c9 == 3,
0 c1 + 13 c2 + 0 c3 + 4 c4 + 4 c5 + 14 c6 + 17 c7 + 17 c8 + 21 c9 == 6},
{c1, c2, c3, c4, c5, c6, c7, c8, c9}, Modulus -> 26]

which (more or less) just solves some linear equations, and returns this:

c1 == C[1] && c2 == C[2] && c3 == 24 + 2 C[1] + 10 C[2] && c4 == 16 + 11 C[1] + 20 C[2] && c5 == 1 + 6 C[2] && c6 == 21 + 22 C[1] + 8 C[2] && c7 == 11 + 12 C[1] + 16 C[2] && c8 == 13 + 17 C[1] + 13 C[2] && c9 == 2 + 13 C[1] + 4 C[2]

meaning

that we have (as we should expect since 9-7=2) a two-parameter family of solutions. But of course we have a further constraint, not so amenable to linear algebra: we know that the coefficients have to be 0,1,...,8 in some order. Well, we know that those parameters C[1] and C[2] are chosen from 0,1,...,8, so there are only 81 9-tuples to look at. That's not too much brute force, I think.
Select[Flatten[Table[Mod[{u, v, 24 + 2 u + 10 v, 16 + 11 u + 20 v, 1 + 6 v, 21 + 22 u + 8 v, 11 + 12 u + 16 v, 13 + 17 u + 13 v, 2 + 13 u + 4 v}, 26], {u, 0, 8}, {v, 0, 8}], 1], Max[#] == 8 &]

yielding this:

{{4, 0, 6, 8, 1, 5, 7, 3, 2}}

In other words,

A enciphered with her name 4 times, B 0 times, C 6 times, etc. So B was eliminated first, then E, then I, then H, then A, then F, then C, then G, and finally D who must be our winner.

It wouldn't be difficult to

figure out who was in which chair when, but we don't actually have to.