Problem 25 · 2009 Math Kangaroo
Stretch
Counting & Probability
careful-countingsum-constraint
55 pupils are taking part in a competition. A jury marks each question with a “+” if it is solved correctly, with a “−” if it is solved incorrectly, and a “0” if it was not attempted. It turns out that no two students had the same number of “+” as well as the same number of “−”. What is the minimum number of questions that had to be asked in the competition?
Show answer
Answer: B — 9
Show hints
Hint 1 of 2
Each pupil is described by the pair (number of +, number of −), and these pairs must all be different.
Still stuck? Show hint 2 →
Hint 2 of 2
Count how many such pairs are possible with Q questions, and make it reach 55.
Show solution
Approach: count the distinct (plus, minus) pairs
- With Q questions a pupil’s pluses and minuses satisfy (#+) + (#−) ≤ Q, giving (Q+1)(Q+2)/2 possible pairs.
- All 55 pupils need different pairs, so (Q+1)(Q+2)/2 ≥ 55.
- The smallest Q is 9, since 10·11/2 = 55. Answer 9.
Mark:
· log in to save