Musical Chairs Cipher

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.

If the game began with the words

CRAYONS
READING
TEACHER

PENCILS
BOOKBAG

And ended with

MJEMHSB
ZLTYQIJ
DSGUXMZ
SIAKAPV
FCZUJEU

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

Answer

First of all, let's assume that the encrypted words are in the same order as the plaintext ones, since otherwise this puzzle would just be some boring busywork.

Then, we notice that the kid's names start with the letters A to F only. This means that each round can only shift the first letter of a word by 5 spots in the alphabet.

Let's start with calculating

how many spots in the alphabet the first letter of each chair has shifted.

 CRAYONS -> MJEMHSB 10

 READING -> ZLTYQIJ  8
 TEACHER -> DSGUXMZ 10
 PENCILS -> SIAKAPV  3
 BOOKBAG -> FCZUJEU  4

All in all, those seem to a bit on the small side; the average starting letter in the kid's names is "C and a half", so applying that 15 times you'd expect a total of 37.5, while we only have 35. This doesn't mean much, but we'd probably do well if we dropped Denise, Eddie, or Flo on the first round.

Now, let's find the first chair out.

Because the maximum first letter shift in one round is 5 (Flo), the only two options are PENCILS and BOOKBAG. From the first letters, PENCILS would have to be encrypted with DENISE, so let's try that first:

PENCILS $\oplus$ DENISE = SIAKAPV

What do you know, it worked!

This is interesting, because

the kids are in alphabetic order, so BOOKBAG got either Eddie or Flo. The latter is impossible (it would take the first letter past the encrypted one, and there isn't time to bring it back around), so in the first round, BOOKBAG got Eddie, and on the remaining rounds it got ALICE. We can find out how many times it got Alice by just counting the necessary encryptions: BOOKBAG $\oplus$ EDDIE = FRRSFEJ and FRRSFEJ $\oplus$ ALICE = FCZUJEU. Ah, so just once was enough.

So now we have

 Chair      Result   N  Round 1  Round 2
 CRAYONS -> MJEMHSB 10
 READING -> ZLTYQIJ  8

 TEACHER -> DSGUXMZ 10 
 PENCILS -> SIAKAPV  3  Denise   -----    -----
 BOOKBAG -> FCZUJEU  4  Eddie    Alice    -----

Now we see that Denise and Eddie didn't drop out on the first round, so we'd really like to get rid of Flo, because otherwise the average letter shift would drift even further away from the one in the final ciphers. This is of course just an educated guess, so if we run into a contradiction later, we'll need to return here and start over.

 Chair      Result   N  Round 1  Round 2 Round 3
 CRAYONS -> MJEMHSB 10  Alice
 READING -> ZLTYQIJ  8  Ben

 TEACHER -> DSGUXMZ 10  Carl
 PENCILS -> SIAKAPV  3  Denise   -----    -----
 BOOKBAG -> FCZUJEU  4  Eddie    Alice    -----
                Out  -  Flo 

Since CRAYONS can't possibly reach its encryption on round three, it's going to be either READING or TEACHER. Let's try all the possibilities:

READING $\oplus$ BEN $\oplus$ DENISE $\oplus$ EDDIE = ZPDUIIN
READING $\oplus$ BEN $\oplus$ EDDIE $\oplus$ DENISE = (same as above, Vigenère is commutative)
TEACHER $\oplus$ CARL $\oplus$ EDDIE $\oplus$ EDDIE = DKXDRMO

Ouch. So Flo wasn't the first one out, after all. Then we really, really want to kick Flo out on round 2, because we are way off from the desired letter shift average now. For the same reason, let's try kicking Carl out on round 1. Again, this is a guess which we might have to revisit later.

The table now looks like this:

 Chair      Result   N  Round 1  Round 2 Round 3
 CRAYONS -> MJEMHSB 10  Flo      Ben
 READING -> ZLTYQIJ  8  Alice    Denise
 TEACHER -> DSGUXMZ 10  Ben      Eddie
 PENCILS -> SIAKAPV  3  Denise   -----    -----
 BOOKBAG -> FCZUJEU  4  Eddie    Alice    -----

                Out  -  Carl?    Flo?

Now to find the third chair to be removed, we need to only try one kid for each of the three chairs:

CRAYONS $\oplus$ FLO $\oplus$ BEN $\oplus$ EDDIE = MJEMHSB

Nice, got it on the first try. Incidentally, after this result, the alphabetical order now confirms our earlier guess about Flo. (The guess about Carl is still unconfirmed.)

 Chair      Result   N  Round 1  Round 2  Round 3  Round 4

 CRAYONS -> MJEMHSB 10  Flo      Ben      Eddie    -----
 READING -> ZLTYQIJ  8  Alice    Denise
 TEACHER -> DSGUXMZ 10  Ben      Eddie
 PENCILS -> SIAKAPV  3  Denise   -----    -----    -----
 BOOKBAG -> FCZUJEU  4  Eddie    Alice    -----    -----
                Out  -  Carl?    Flo

For the fourth round, there are a bit too many possibilities, so let's bring out the secret weapon I was hoping to do without: the second letter shift. We'll only do it for the remaining chairs and kids, though.

 Chair      Result  1st 2nd Round 1  Round 2   Round 3  Round 4
 CRAYONS -> MJEMHSB 10      Flo      Ben   (4) Eddie    -----
 READING -> ZLTYQIJ  8  33  Alice    Denise(4)
 TEACHER -> DSGUXMZ 10  14  Ben      Eddie (3)
 PENCILS -> SIAKAPV  3      Denise   -----     -----    -----
 BOOKBAG -> FCZUJEU  4      Eddie    Alice(11) -----    -----
                Out  -      Carl?    Flo

From this, we can instantly see, that

TEACHER is seven steps short in the second letter, so Eddie must sit there once more. That leaves 4 steps, and the first letter shift excludes Denise, so the remaining two must be Ben and Eddie. Since Eddie is already placed on round 3, we have the order too, so we can (after double checking that TEACHER $\oplus$ BEN $\oplus$ EDDIE $\oplus$ BEN $\oplus$ EDDIE = DSGUXMZ, which it does) also place Alice using the alphabetical order:

 Chair      Result  1st 2nd Round 1  Round 2   Round 3  Round 4 Round 5
 CRAYONS -> MJEMHSB 10      Flo      Ben   (4) Eddie    -----   -----
 READING -> ZLTYQIJ  8  33  Alice    Denise(4) Alice
 TEACHER -> DSGUXMZ 10  14  Ben      Eddie (3) Ben      Eddie   -----
 PENCILS -> SIAKAPV  3      Denise   -----     -----    -----   -----
 BOOKBAG -> FCZUJEU  4      Eddie    Alice(11) -----    -----   -----
                Out  -      Carl?    Flo       Denise

And then we can use the first letters to determine that READING must have

Ben and Eddie on the last two rounds. The second letter also works out, so we are probably good, even without checking the final full encryption. However, we are still not 100% sure about our guess about Carl, so let's do it anyway:
READING $\oplus$ ALICE $\oplus$ DENISE $\oplus$ ALICE $\oplus$ BEN $\oplus$ EDDIE = ZLTYQIJ (Yay!)

So finally, here's the full game:

 Chair      Result  1st 2nd Round 1  Round 2   Round 3  Round 4 Round 5 Winner
 CRAYONS -> MJEMHSB 10      Flo      Ben   (4) Eddie    -----   -----

 READING -> ZLTYQIJ  8  33  Alice    Denise(4) Alice    Ben     Eddie
 TEACHER -> DSGUXMZ 10  14  Ben      Eddie (3) Ben      Eddie   -----
 PENCILS -> SIAKAPV  3      Denise   -----     -----    -----   -----
 BOOKBAG -> FCZUJEU  4      Eddie    Alice(11) -----    -----   -----
                Out  -      Carl     Flo       Denise   Alice   Ben     Eddie

Afterthought

At the beginning, we calculated the shifts only for the first letter. Since it later became necessary to calculate the shifts for the second letter too, we could have used a neat trick to do the two (and the rest of the letters, too) at the same time:

If we decrypt the final words on the chairs using the original names of the chair as the key, we get the letter shift for every letter position (mod 26) as the result. Since one of the chairs was only encrypted once, one of the results should instantly reveal a kid's name, too.

$\texttt{MJEMHSB} \ominus \texttt{CRAYONS} = \texttt{KSEOTFJ}$

$\texttt{ZLTYQIJ} \ominus \texttt{READING} = \texttt{IHTVIVD}$
$\texttt{DSGUXMZ} \ominus \texttt{TEACHER} = \texttt{KOGSQII}$
$\texttt{SIAKAPV} \ominus \texttt{PENCILS} = \texttt{DENISED}$
$\texttt{FCZUJEU} \ominus \texttt{BOOKBAG} = \texttt{EOLKIEO}$

So, as expected, the first letters of the results (K,I,K,D,E) correspond to the numbers (10,8,10,3,4) we had in the first spoiler block, and Denise was revealed to be the kid to sit in the PENCILS chair, which was the first one to be removed.