Save Time!

Logic Level 2

A teacher is about to give the quiz papers back to her class of 60 students. To save time, she doesn't want to hand the papers to each student in person. Rather, she will just call some of the students and hand them some of the papers so that they, in turn, can give the papers to their classmates. But the class also wants to save time, so they will do the same thing as the teacher does.

If everyone needs one second to call a classmate and give him or her some paper(s), then what is the least amount of time (in seconds) the class has to spend to let everyone get their quiz paper?

For example, suppose there are three students: A, B, C. The $1^\text{st}$ second, the teacher gives student A two papers: A's and B's. The $2^\text{nd}$ second, the teacher gives C's paper to C, as A gives B's paper to B, so they spend 2 seconds altogether.

5 6 7 8

2 solutions

Nick Turtle
May 6, 2018

There are in total $61$ people in the classroom (including the teacher). With the optimum strategy, since the number of people that have the test papers gives a test to someone else, after each second, the number of people that have the tests double.

After $n$ seconds, the number of people that have the tests is simply $2^{n}$ .

Then, $\begin{aligned}2^{n}&>61\\ n&=6\end{aligned}$

Richard Desper
Apr 28, 2020

Thm: it takes at most $n$ seconds to distribute $2^n - 1$ papers.

Base case: obviously true for $n=1$ .

Inductive step: Suppose true for $n \leq k$ .

Let us suppose the teacher has $2^{k+1} - 1$ papers. She divides the papers into two stacks, one with $2^k$ papers and one with $2^k -1$ papers. She takes $1$ second to give the first stack to a person whose paper is in that stack. Then she has $2^k -1$ papers to distribute and the student also has $2^k - 1$ papers to distribute (since he can keep his own). By induction the rest of the distribution can be done in $k$ seconds, so the entire process takes at most $(k+1)$ seconds.

Save Time!

2 solutions

0 pending reports