4
$\begingroup$

Suppose 'M' number of professors have to guess 'N' number of dishes on a roulette menu offered by a restaurant. This restaurant has a special "roulette menu" with N items, in which you choose a menu item from 1 to N that corresponds to one of the N available items, but you don't know which number corresponds to which item.

When the items are ordered, they are brought to the table in no particular order, so if a group orders multiple items at a time, they cannot figure out individually which item was ordered by whom.

The professors have tasked themselves with figuring out which number corresponds to which item in some number of days regardless. Find the minimum number of days they can figure out all dishes.

This is a general form of the question of 5 professors and 9 dishes.

$\endgroup$
  • $\begingroup$ Why you use 'N' when you have 9 dishes. $\endgroup$ – Moti Jun 30 '18 at 6:02
  • 1
    $\begingroup$ I am going further from what is being asked in the problem. Wouldn't be better. if we could find out the general version of the problem. @Moti $\endgroup$ – Antariksha Pattnaik Jun 30 '18 at 8:37
1
$\begingroup$

Unfortunately, I do not have a nice tidy formula to solve this problem, but I do have a relatively straight forward algorithm.

First, we need to evaluate how we differentiate between items. The feedback we can obverse is how many items are received each day. For example, if we only have one item we order 2 of on day 1, 0 on day 2, and 1 on day three, then we know that the dish that follows these numbers corresponds to that item.

For simplicity, I will list the number of items ordered each day as a list. Following this, the example I gave above becomes {2, 0, 1}.

Generally, we want to minimize the number of times an individual item is ordered over all the days. If we have three days we can order {1, 0, 0}, {2, 0, 0}, {3, 0, 0}, and each of their two other permutations to detect $3*3=9$ dishes. However, this requires $1+2+3=6$ professors and as seen by the problem linked in the question, only five are needed if we use {1, 1, 0} instead of {3, 0, 0}. It's also worth noting that {0, 0, 0} is a valid combination that can detect one item.


Given $D$ days and a set $\mathcal{S}$ of a combination length $D$ and its permutations, how many dishes can we detect and how many professors do we need?

Let's start with an example case where $D = 5$ and the combination is {2, 1, 1, 0, 0}. This represents ordering an item twice 1 day, once 2 days, and zero times 2 days. We need to figure out how many permutations there are. In this case, there are $\frac{5!}{2!2!} = 30$ permutations as the 1 and 0 are each repeated twice. This answers the first half of the question as each combination corresponds to a dish. The number of professors we need is $\frac{30 * 4}{5} = 24$ as there are 30 dishes ordered 4 times over 5 days.

This generalizes to $|\mathcal{S}|$ (number of permutations) detectable dishes by $\frac{|\mathcal{S}| x}{D}$ where $x$ is the sum of a combination (4 in the case above).


Now, let's move on to finding a solution.

As you might be able to tell from the equation above, it much easier determine if a given amount of days $D$ is valid for professors $M$ and dishes $N$ rather than calculate it directly. So, one can perform a binary search starting with a guess for $D$, then try higher or lower depending on if $D$ is valid.

Once a $D$ is chosen, we can start adding combinations of length $D$ until we run out of professors (invalid) or detect the number of dishes (valid). The combinations are added in order or their sum as explained above. If both conditions become true at the same time, we must evaluate the case closer. This can be done by comparing the dishes to $\frac{Dm}{x}$ where $x$ again is the combination's sum and $m$ is the number of professors left. I believe this is enough to prove the validity of $D$ but I might have missed an edge case (if you can think of a counter example please let me know).

We can speed this process up a little bit by trying to add all combinations of a given sum $x$. The amount of dishes at that sum is $n = {x+D-1 \choose D-1}$ and the number of professors needed is $\frac{nx}{D}$. I'm not entirely sure on the mathematical explanation for this as I found it by analyzing the trend. Again, as long as both conditions are not simultaneously met, no further investigation is required.

The solution to the problem is where $D$ is valid for the given $M$ and $N$ but $D-1$ is not.


Let's try somewhat complicated example. Let $M=15$ and $N=34$, find $D$. From now on, $x$ represents the sum, $m$ represents the professors, and $n$ represents the dishes at a given step.

Suppose $D=3$.

At $x=0$, $n = {x+D-1 \choose D-1} = {2 \choose 2} = 1$ and $m = \frac{nx}{D} = 0$, leaving 33 dishes and 15 professors.
At $x=1$, $n = {3 \choose 2} = 3$ and $m = \frac{3*1}{3} = 1$, leaving 30 dishes and 14 professors.
At $x=2$, $n = {4 \choose 2} = 6$ and $m = \frac{6*2}{3} = 4$, leaving 24 dishes and 10 professors.
At $x=3$, $n = {5 \choose 2} = 10$ and $m = \frac{10*3}{3} = 10$, leaving 14 dishes and 0 professors.
We have run out of professors, so $D=3$ is invalid.

Suppose $D=7$.

At $x=0$, $n = {6 \choose 6} = 1$ and $m = \frac{nx}{D} = 0$, leaving 33 dishes and 15 professors.
At $x=1$, $n = {7 \choose 6} = 7$ and $m = \frac{7*1}{7} = 1$, leaving 26 dishes and 14 professors.
At $x=2$, $n = {8 \choose 6} = 28$ and $m = \frac{28*2}{7} = 8$, leaving -2 dishes and 6 professors.
We have run out of dishes, so $D=7$ is valid.

Suppose $D=5$.

At $x=0$, $n = {4 \choose 4} = 1$ and $m = \frac{nx}{D} = 0$, leaving 33 dishes and 15 professors.
At $x=1$, $n = {5 \choose 4} = 5$ and $m = \frac{5*1}{5} = 1$, leaving 28 dishes and 14 professors.
At $x=2$, $n = {6 \choose 4} = 15$ and $m = \frac{15*2}{5} = 6$, leaving 13 dishes and 8 professors.
At $x=3$, $n = {7 \choose 4} = 35$ and $m = \frac{35*3}{5} = 21$, leaving -8 dishes and -13 professors.
Both conditions are true so we must add one combination at a time.
For {1, 1, 1, 0, 0}, $n = \frac{5!}{3!2!} = 10$ and $m = \frac{10*3}{5} = 6$, leaving 3 dishes and 2 professors.
Since $\frac{Dm}{x} = \frac{5*2}{3} > n = 3$, $D=5$ should be valid.
We can double check this by possible combinations. The last 3 dishes can be indicated with {2, 1, 0, 0, 0}, {0, 1, 2, 0, 0}, and {0, 0, 0, 2, 1} using 2 professors.

Suppose $D=4$.

At $x=0$, $n = {3 \choose 3} = 1$ and $m = \frac{nx}{D} = 0$, leaving 33 dishes and 15 professors.
At $x=1$, $n = {4 \choose 3} = 4$ and $m = \frac{4*1}{4} = 1$, leaving 29 dishes and 14 professors.
At $x=2$, $n = {5 \choose 3} = 10$ and $m = \frac{10*2}{4} = 5$, leaving 19 dishes and 9 professors.
At $x=3$, $n = {6 \choose 3} = 20$ and $m = \frac{20*3}{4} = 15$, leaving -1 dishes and -6 professors.
Both conditions are true so we must add one combination at a time.
For {1, 1, 1, 0}, $n = \frac{4!}{3!} = 4$ and $m = \frac{4*3}{4} = 3$, leaving 15 dishes and 6 professors.
For {2, 1, 0, 0}, $n = \frac{4!}{2!} = 12$ and $m = \frac{12*3}{4} = 9$, leaving 3 dishes and -3 professors.
We have run out of professors, so $D=4$ is invalid.

Since $D = 5$ is the lowest valid $D$ it must be the correct answer to this example.


Update: After checking the sum there is no need to check the individual combinations and instead can skip straight to the $\frac{Dm}{x}$ formula. This of course still assumes that there is no edge case as I mentioned earlier.

On a side note the edge case would come if a professor has the opportunity to order something but no set of unique combination can use that slot. Think of it as the last professor having three blank slot but needs to fulfill a combination like {3, 0, 0} which is impossible. I believe that this situation can be avoided by choosing a different layout of combinations. However, I don't have anything to prove that.

$\endgroup$

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.