1
$\begingroup$

With 2000 index cards, each having a single number on it, I am tasked with the job of finding the grand total of all numbers. In order to do so, I have 1000 people, each who sit at a desk in a room that has 25 rows with 40 desks. Each person can pass a stack of cards to their neighbor front, back, right and left. Given that I am only allowed to give the entire stack to one person, it takes 3 seconds for a person to pass a stack (regardless of size) to their neighbor. It takes 1 second to add 2 numbers and the person allowed to write the sum on the card to pass to the neighbor.

What's the fastest means of obtaining the sum of all numbers on the card if I am required to gather all subtotals to give to the original person I passed the entire stack to?

I'm wondering whether it's fastest to utilize all 1000 or whether there's a faster way of getting the sum without having to use all.

EDIT: I feel like the best thing to do is to give the initial stack to the person in the middle so that it'll be quickest to have everything passed back to him/her

$\endgroup$
  • $\begingroup$ @Sh3ljohn It takes 3 seconds per neighbor $\endgroup$ – trungnt Sep 19 '16 at 23:22
  • 1
    $\begingroup$ You don't seem to have a clear idea of the problem you are trying to solve. Do you want a fast way to distribute the data? Or a fast way of calculating the sum? Or what? This gets you a close vote from me, because I don't think you have done much work on the problem. $\endgroup$ – Rob Arthan Sep 19 '16 at 23:39
  • $\begingroup$ @RobArthan I'm trying to figure out what's the fastest way of calculating the sum, whether that means using all 1000 members or not. Right now, I'm trying to reduce the size from 25 x 40 to 5 x 8 and work on a smaller scale. Still stumped though. $\endgroup$ – trungnt Sep 19 '16 at 23:47
  • 1
    $\begingroup$ @trungnt Your question explicitly asks "What's the fastest means of distributing cards to everyone", and that is already a non-trivial problem. You should clarify your post. $\endgroup$ – Sheljohn Sep 19 '16 at 23:48
  • $\begingroup$ @trungnt If a person passes the stack to their neighbour, does it prevent their neighbour from doing something during the 3 seconds? Can a person receive cards simultaneously from several neighbours? $\endgroup$ – Sheljohn Sep 19 '16 at 23:56
4
$\begingroup$

I don't know if this is optimal, but here is a pattern to beat:

Give the whole stack to the person at $(2,2)$. They then pass to the person at $(2,3)$, and then both pass to $(3,2)$ and $(3,3)$. The four then pass to $(1,2), (1,3), (4,2), (4,3)$ and then the eight pass so that everyone in the block from $(1,1)$ to $(4,4)$. Now, $16$ people have cards, and we are $12$ seconds in. Group the people in terms of the round in which they received cards - there are groups $P_0, P_1, P_2, P_3, P_4$ with $1,1,2,4,8$ people respectively.

$P_0$ takes $136$ cards, $P_1$ takes $132$ cards, each person in $P_2$ takes $128$ cards, each in $P_3$ takes $125$ cards, and each in $P_4$ takes $122$ cards. Silence reigns for the next $121$ seconds as everyone sums cards.

Then, everyone in $P_4$ is done and passes their cards to their neighbor in $P_3$. This takes $3$ more seconds, while everyone else keeps working. Then group $P_3$ finish their cards, having taken $125$ seconds, including adding $P_4$'s sums to theirs. They then pass to $P_2$, who are waiting and so on.

At the end, this takes $137 + 12 = 149$ seconds for $P_0$ to have the total.

For a loose lower bound, note that someone needs to sum all $2000$ cards, so we can't do better than (around) $\min_k \frac{2000}{2^k} + 6k$, where $k$ is the number of rounds of passing, overestimating the number of people after $k$ rounds as $2^k$. Wolframalpha gives that bound at around $55$ seconds.

$\endgroup$
  • $\begingroup$ I understand that the last group to receive cards will have the least do that they can pass the cards to the previous group while they still work, but can you explain how you came to deciding how many cards each group receives? $\endgroup$ – trungnt Sep 20 '16 at 1:16
  • $\begingroup$ $P_3$ gets $3$ more seconds than $P_4$, $P_2$ gets $4$ more seconds than $P_3$ ($3$ to pass, $1$ to add), and so on. If $P_4$ gets $x$ cards each, then we get $8x + 4(x + 3) + 2(x+7) + (x + 11) + (x+15) = 16x + 52$. That gives $x = 121$, plus a remainder of $12$.. I distributed the extra $12$ to $P_3$ and $P_4$ to get the numbers. $\endgroup$ – Michael Biro Sep 20 '16 at 1:21
  • $\begingroup$ I understand. Thanks for your input! $\endgroup$ – trungnt Sep 20 '16 at 1:29
  • $\begingroup$ Your lower bound is not quite clear. As in your example, the late people can have a few cards less than their share, which reduces the time a few seconds. $\endgroup$ – Ross Millikan Sep 20 '16 at 1:37
3
$\begingroup$

Following on Michael Biro's suggestion, give the stack to somebody in the center and call that position $(0,0)$ and that person $P_0$. They pass cards to $P_1$ in $(0,-1)$. Each of them next pass to $P_2's$ in $(1,0)$ and $(0,-2)$. The third round the first two pass to $(-1,0)$ and $(-1,-1)$ and the $P_2$s pass to $(1,1)$ and $(1,-2)$. These are $P_3$s. Everybody can pass to a $P_4$, but $P_0, P_1$ and two of the $P_3$s cannot pass to a $P_5$. Everybody else does so. We now have one $P_0$, one $P_1$, two $P_2$s, four $P_3$s eight $P_4$s and twelve $P_5$s. $P_0$ keeps $81$ cards, $P_1$ keeps $79, P_2$ keeps $77, P_3$s who pass to $P_5$s keep $74, P_3$'s who don't pass to $P_5$s keep $77, P_4$'s keep $71, $ and $P_5$'s keep $68.$ It takes $15$ seconds to pass cards, $68$ for the $P_5$s to add, $15$ seconds to pass the cards back for a total of $98$ seconds. There may be an additional $5$ seconds if you need a second to add the number from te stack you received.

We can do a little better passing $6$ times. We can only get cards to $1$ people in round $6$, but the $P_6$s can do $42$ cards. We have $18$ seconds passing, $42$ seconds adding, $18$ seconds passing back for a total of $78$ seconds. Even better we can enlist $20\ P_7$s to do $28$ cards each, for a total time of $21+28+21=70$ seconds.

$\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.