2
$\begingroup$

A group of N children, who are numbered 1, 2, . . . , N, want to play hide and seek. In a single round of hide and seek, there will one seeker, and N −1 hiders. Children like to hide and not seek and each child has her own idea of how many times she would like to hide. You will be given for each child i, a number H[i] denoting the number of rounds she would like to be a hider. She will be satisfied only if she gets to be a hider in at least H[i] rounds.

For example, suppose N = 4, and H[1] = 1, H[2] = 3, H[3] = 2 and H[4] = 1. Here is one way to satisfy them all. In Round 1, Child 1 is the seeker, and in Rounds 2 and 3, Child 4 is the seeker. Then Child 1 has been a hider in 2 Rounds, Child 2 has been a hider in 3 Rounds, Child 3 has been a hider in 3 Rounds, and Child 4 has been a hider in 1 Round. Thus, they are all satisfied. You can check it is not possible to satisfy all of them in fewer than 3 Rounds.

You aim is to determine the least number of rounds that needs to be played so that every child is satisfied. For the example in the previous paragraph, the answer is 3.

Determine the minimum number of rounds needed in the following cases: **(a) N = 7, H[1] = 6, H[2] = 13, H[3] = 9, H[4] = 5, H[5] = 15, H[6] = 8, H[7] = 9.

(b) N = 12 H[1] = 6, H[2] = 7, H[3] = 7, H[4] = 8, H[5] = 9, H[6] = 9, H[7] = 9, H[8] = 9, H[9] = 9, H[10] = 9, H[11] = 9, H[12] = 9**

(c) N = 15 H[1] = 131, H[2] = 135, H[3] = 130, H[4] = 138, H[5] = 132, H[6] = 140, H[7] = 137, H[8] = 133, H[9] = 131, H[10] = 137, H[11] = 138, H[12] = 132, H[13] = 135, H[14] = 136, H[15] = 134.

Is there any mathematical or algorthmic way to solve this problem. Ans:- (a) 15 (b) 10

My attempt:- For (a) , H[4] can be seeker 6 times so H{1] get satisifed, and then H[1] will be next seeker for 9 times, so the rest like H[5] get satisfied.
I can't think about (b).

$\endgroup$

1 Answer 1

1
$\begingroup$

The answer to (b) obviously has to be at least $9$. To do it in $9$ rounds, then child $1$ can be the seeker at most $3$ times, children $2$ and $3$ at most $2$ times, and child $4$ at most $1$ time. The rest must hide every time. This only gives $3+2+2+1=8$ rounds, so it is not possible.

However, if we make two different children seek one more time each, then everyone is satisfied, so the answer is $10$.

A possible configuration is $(4, 3, 2, 1, 0, 0, \ldots)$.

General solution: The strategy for (b) works in general. Let $R$ be the total number of rounds. Let $h_i$ and $s_i$ be the number of times child $i$ actually hides and seeks in the games.

First find the largest wish, $M:=\max(H[i])$. Then $R\ge M$. For each child we have $$ s_i = R-h_i \le R-H[i] $$ If $D:=\sum_{i=1}^N (M-H[i])\ge M$, then we can have $R=M$ by just making each child seek at most $M-H[i]$ times. For example in (a), the sum is $9+2+6+10+0+7+6$, which is way more than $M=15$, so we have a lot of freedom.

If $D < M$, then we need more rounds than $M$. First we make each child seek $M-H[i]$ times. That uses $D$ rounds. Now every child has hidden $D-(M-H[i])$ times, so they still need to hide $$ H[i] - (D-(M-H[i])) = M-D $$ times, which is the same for all of the children. Now we simply let child $1$ seek once, then child $2$, then child $3$, and so on until they are all satisfied. If we get to child $N$, we start from $1$ again. How long does this take? It takes a bit of working out, but I believe it takes an additional $$ M-D + \left\lceil \frac {M-D}{N-1} \right\rceil $$ number of rounds. So the final answer in all cases should be $$ R_\min = \begin{cases} M & M\le D \\ M + \left\lceil \frac {M-D}{N-1} \right\rceil & M>D \end{cases} \\ = M + \max\left\{ 0, \left\lceil \frac {M-D}{N-1} \right\rceil \right\} $$

Check: In (a) we have $D=9+2+6+10+0+7+6=40$, so the formula gives $R_\min=M=15$.

In (b), $D = 3+2+2+1 = 8$, so the formula gives $R_\min = 9 + \lceil\frac{9-8}{12}\rceil = 10$.

Let's apply it to (c). $M= 140$, $D=9+5+10+2+8+0+3+7+9+3+2+8+5+4+6 = 81$. So we should have $$ R_\min = 140 + \lceil\frac{140-81}{14}\rceil = 145 $$ Do you have the real answer to check against? There also might be typos in the numbers of course. The algorithm gives the following configuration of seekers: $$ (9,5,10,2,8,0,3,7,9,3,2,8,5,4,6) + (5,5,5,5,4,4,4,\ldots) = (14, 10, 15, 7, 12, 4, 7, 11, 13, 7, 6, 12, 9, 8, 10) $$ which means they hid the following number of times: $$ (131, 135, 130, 138, 133, 141, 138, 134, 132, 138, 139, 133, 136, 137, 135) $$ We can see that the first four children hid exactly $H[i]$ number of times, while the rest hid $H[i]+1$ number of times.

I am almost certain that this is the optimal solution, but I haven't made a real proof.

$\endgroup$
11
  • $\begingroup$ How do you find that child 1 has to be seeker at most 3 times, and child 2 and 3 at most 2 times. $\endgroup$
    – Ayush Raj
    Nov 4, 2019 at 7:50
  • $\begingroup$ If there are $9$ rounds and child $1$ hides in more than $6$, there are at most $3$ rounds available for seeking. "seek $+$ hide $= 9$". $\endgroup$
    – Milten
    Nov 4, 2019 at 7:53
  • $\begingroup$ Oops, that was a typo. Let's say $S[i]$ is the number of times they seek. Then I meant to write $S[1]\le 3$, $S[2]\le 2$, $S[3]\le 2$, $S[4]\le 1$. $\endgroup$
    – Milten
    Nov 4, 2019 at 7:57
  • $\begingroup$ Oh, right, I'm sorry -.- We actually need to make two different children seek (doesn't matter who). Then we also actually get to $10$ rounds. Sorry I'm so distracted. $\endgroup$
    – Milten
    Nov 4, 2019 at 8:09
  • $\begingroup$ Hey, I am not able to do the same with (c) $\endgroup$
    – Ayush Raj
    Nov 4, 2019 at 8:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .