Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A class of students takes a quiz marked out of . Every score is a whole number from to . The teacher notices that several students got the same score, and she asks how many must share a score whatever the results.
Find the largest number such that some score is always shared by at least students. Then find the smallest class size that makes sure some score is shared by at least students. Explain both answers with the generalised pigeonhole principle.
objects in boxes put at least in some box. To force objects into one of boxes you need . Some number in a list is at least the average.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Given. students, scores to .
Plan. The scores are the boxes. Use and .
Step 1. The boxes. The scores are boxes.
Step 2. Shared by how many. , so some score is shared by at least students.
Step 3. Five is the most we can promise. Six students could not be promised: give students each to scores and students each to the other scores. That is students, and no score has .
Step 4. Forcing six. The worst case puts students on each of the scores, which is students. One more student forces on some score. So the class size is .
Check. A common slip uses scores and gets and . The score is a box too.
Answer: , and a class of students forces on one score.
Log in to join the discussion.
Loading…