2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Questions should be self-contained, so people do not have the inconvenience of clicking back and forth from the other one, so you should copy and paste the list of rules. $\endgroup$ – Duck Jun 11 at 22:37
  • $\begingroup$ @Duck I have edited in the rules, thanks for letting me know $\endgroup$ – Bewilderer Jun 11 at 22:51
  • $\begingroup$ The teacher apparently wasn't too careful about how to spell "provolone", either :-). $\endgroup$ – Gareth McCaughan Jun 11 at 22:53
  • $\begingroup$ I assume the "!" in front of RVJAQJP is just a typo? $\endgroup$ – Gareth McCaughan Jun 11 at 22:58
  • $\begingroup$ @GarethMcCaughan yeah, i didn't notice lol $\endgroup$ – Bewilderer Jun 11 at 23:01
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice solution. Regarding the discussion at the comments to the question, I was trying to find a shortcut exactly because this method seemed to be way too much drudgework to be worth doing by hand. $\endgroup$ – Bass Jun 12 at 1:23
  • $\begingroup$ Yeah, this is correct. I didn't intend for the solution to involve so much math, only a surface level amount. I intended it to be a series of equations, but I guess I messed up somewhere... Good work. $\endgroup$ – Bewilderer Jun 12 at 1:25
  • $\begingroup$ @Bass Fair enough. To me this seems like rather little drudgework, perhaps because I just take it for granted that linear algebra is a task for computers in the same way as multiplication is a task for calculators. $\endgroup$ – Gareth McCaughan Jun 12 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.