11
$\begingroup$

You are a new Math 102 professor in a university class of 88 students and would like to learn their grades from previous semester to know your students better and put a note of it to get an idea how good they are because the electronic system is broken right now.

But you need the precise grades from the last semester class Math 101, which could be integers between 0 to 100. You want to ask the least number of questions not to bother your students somehow or to show off, who knows... But you can ask only one kind of question:

"How many people got x,y,z... points from the last semester math class, raise your hand please?"

and take notes of the students accordingly whoever lift his/her hands. x,y,z,... could be any number of points/grades. such as;

"How many people got 0,15,30,32,38 points from the last semester math class, raise your hand please?"

So

What is the least number of questions you can ask to guarantee to know every single student grades in the class?

$\endgroup$
  • 2
    $\begingroup$ I assume that "you can ask only one question" means "you can ask only one kind of question"? $\endgroup$ – Gareth McCaughan Aug 1 at 21:23
  • $\begingroup$ @GarethMcCaughan fixed. $\endgroup$ – Oray Aug 1 at 22:19
20
$\begingroup$

The answer is:

a minimum of 7 questions

Here's the way you get that number:

To solve this puzzle, I'm first going to look at a simpler variation where every student can have only 1 out of 4 possible grades: A, B, C, or D. We can do this the normal way with 3 questions (Which students got A, which students got B, which students got C. The ones with the D are the rest which didn't lift up their hand) but there's a better way.
Split up the class population in half with the question "Which students got A or B". So for every student, no matter the answer, we cut the possibility spectrum of grades they could have in half. Now, we could ask "Which students got A" to determine the grade of the people who lifted their hand in the first question, but we could also ask "Which students got A or D". If a student lifted their hand on both questions, we know they have an A because the first question told us they can't have a D. Each grade thus corresponds to an unique set of hand lifts and hand abstains, which we could represent as a binary number like so:
A - 11
B - 10
C - 00
D - 01
With every doubling of the possible number of grades, we need 1 more question to determine which half every student is in. So for 8 possible grades that is 3 questions, for 16 it's 4 and so on. So, for N possible grades, we have to ask log2(n) questions (rounded up) to know the precise score every single student has. There are 101 scores (don't forget the 0), log2(101) is 6.65 or 7 questions needed.

$\endgroup$
  • 4
    $\begingroup$ Technically you probably can't take 102 if you didn't pass 101, which would limit the possibilities. $\endgroup$ – Kat Aug 3 at 1:25
  • $\begingroup$ Yes, I thought of that as well, but OP's text said 0-100. $\endgroup$ – Chris Cudmore Aug 3 at 15:37
18
$\begingroup$

The answer is 7, It's a simple extension of the Magic Calculator trick.

enter image description here

Each card represents a bit, with the upper left index value being the value of that bit. To perform it as a trick, you ask the volunteer to pick a number between 1 and 64, and hand you the cards on which their number appears. Add up the index values on the selected cards, and you have the number.

This can be extended up to 127 with one more card, indexed as 64, (and additional values on each card).

You simply ask "Who's grade appears on card X" for each card, and record the results.

This solution is essentially the same as @umnikos,

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