A class of 100 students takes a six question exam. For the first question, a student receives 1 point for answering correctly, -1 point for answering incorrectly or not answering at all. For the second question, the student receives 2 points for answering correctly and -2 points for answering incorrectly or not answering at all and so on. What is the minimum number of students having the same scores?
Solution
The maximum score is $$1+2+3+4+5+6 = 21$$, and a student who misses a set of questions with total value $$k$$ scores $$21 - 2k$$. Every value of $$k$$ from 0 to 21 is attainable as a subset sum of $$\{1,2,3,4,5,6\}$$, so there are 22 possible scores. By the pigeonhole principle $$\left\lceil \frac{100}{22} \right\rceil = 5$$ students must share a score.
Get AI Help
Book Free CAT Mentorship
Get personalized CAT strategy from a 99%iler
500+ students mentored
OTP Verification
Enter the 6-digit code sent to your phone
Booking Summary
Enter OTP
Didn't receive the OTP?
