Rawrdon Mamsay pays a visit

Question

Now, I should warn you, this is one of my practical problems; meaning I don't know the solution and the answer's probably anticlimactic (like this or that). Still...

My old pal Rawrdon Mamsay is soon going for a vacation to a town, where his three friends reside.

Those friends are all superbly bad cooks. Every evening each of them prepares a meal for their guests, and every meal (comparing day by day) is different and incomparable to others in their qualities.

Every evening that he stays in town, Rawrdon pays a visit to one of his friends to have a taste of his meal. However, there is a twist.

Each friend plagiarises another, in a chain, completely copying the meal the one prepared the day before. Thus, if A serves a bolognese on Monday, B will serve the same bolognese on Tuesday and C on Wednesday.

As the one hating plagiaraised bolognese, Rawrdon aims to find who is guilty of such unforgivable sin. As the one disliking bad cuisine in general, Rawrdon wants to spent the least amount of days in the city.

How many days (worst case scenario) will it take Rawrdon to locate the 'masterchef' - the one who is first among three to serve the dish?

How many days (worst case scenario) will it take Rawrdon to completely order the friends from most original to least original?

P.S: I intended to post this problem as a commoncase, with N friends; however I considered this too complicated. Anyways, if you find some commonly applicable method, feel free to post.

P.P.S: I will correct typos later as I am in a hurry. Or you can help me with that :3

Answer 1

Rawrdon Mamsay needs to stay at least

$4$

days to identify the head chef, and

$4$

days to identify the cooking order.

Reasoning:

Let's call the friends $A,B,C$ and the meals $Xn$, where $X$ is the preparer's name and $n$ is the number of the day the meal was prepared (example: $A1$ is the first meal prepared by $A$).

Rawrdon Mamsay samples the following meals:

$A1$, $B2$, $B3$, $C4$.
If the order of plagiarism is $ABC$, then $A1 = B2$ and $B3 = C4$.
If the order is $ACB$, then the only equality is $A1 = B3$.
If the order is $BAC$, then the only equality is $B2 = C4$.
If the order is $BCA$, then the only equality is $B3 = C4$.
If the order is $CAB$, then the only equality is $A1 = B2$.
If the order is $CBA$, then all four meals are distinct.
All of these outcomes are disjoint, so Mamsay can identify the order (and thus the head chef) based on the results.

Rawrdon Mamsay cannot complete his task in fewer days:

If he samples the same person twice on the first two days, he will not be able to sample one person at all (wlog. $C$) and thus not be able to distinguish between $BAC$ and $CBA$. If he samples two different people (wlog. $A1,B2$) first, then he also cannot distinguish between $BAC$ and $CBA$ on the third day, no matter which friend he visits.

Answer 2

[EDITED to add:] Seeing Magma's answer, posted about a minute after mine, I realise that the question asked two questions and I've only answered one of them. I shan't modify my question to answer the first as well because Magma's answer already does that perfectly well.

I am not certain that I've understood the explanation in the question quite correctly, so for clarity here is what I take the situation to be.

• Label the friends A,B,C and also 1,2,3. Rawrdon knows who A,B,C are but not the correspondence between ABC and 123.
• On each night, 1 does something new; 2 does whatever 1 did the previous night; and 3 does whatever 2 did the previous night.
• Every time, 1 does something no one else has done recently. (Otherwise Rawrdon could turn up and find everyone cooking the same thing every night, and obviously couldn't tell who was copying whom.)
• Rawrdon can sample one meal per night and wants to figure out the ABC/123 correspondence with as few samples as possible.

Here is one approach Rawrdon can take:

Visit A,B,B.
If B's first meal is the same as A's then we have A->B; so either A->B->C or C->A->B. So now visit C and see whether C copies B or not.
If B's second meal is the same as A's then we have A->C->B and we're done.
If neither B matches A then we have one of B->A->C, B->C->A, C->B->A. Now visit C. If B->A->C then C will match B's first meal; if B->C->A then C will match B's second meal; if C->B->A then C will cook something new.

This uses at most

four visits.

Can we do it with one fewer than that?

If our three visits are all to different people -- say A,B,C -- then we can't distinguish between C->B->A and A->C->B; in either case we will get three different meals.
If we don't visit everyone then suppose we don't visit C. Then nothing we observe can possibly distinguish between A->B->C and C->A->B.

Answer 3

A simple bound in the more general case:

Assume the masterchef never repeats a meal. Denote the $n$ cooks $C_1, \ldots, C_n$. The solution is an ordering of these cooks, and there are $n!$ such orderings. However, we can get a (probably poor) upper bound as follows. First, find who follows $C_1$ by eating in the following order: $C_1, C_2, C_1, C_3, C_1, C_4, \ldots, C_1, C_n$. This has taken $2(n-1)$ days. If it was $C_k$ who follows $C_1$, next find who follows $C_k$ in the same way. We've just eaten at $C_k$'s house, so we save one day, and we don't need to eat at $C_1$'s house any more either. To determine who follows $C_k$ therefore takes us $2(n-2)-1$ days. Continuing this, we get $(n-1)^2 + 1$ days as an upper bound to determine the full ordering in the worst case. Since we are throwing away a lot of information at each stage, it seems likely that one can do much better. For example, this bound is already $1$ day worse than optimal for $n=3$. Can you do better than $n^2$?