There are 17 students in the German language class. For the fi rst essay, the students are required to partition into 4 groups, each containing at least one student. For the second essay the lecturer asks the students to divide into 4 non-empty groups, but no two students that worked together on the fi rst essay are allowed to be in the same group for the second essay. Verify whether this requirement is possible to satisfy and prove your claim.

  • $\begingroup$ I am guessing you know that you should be applying the pigeonhole principle here since presumably you've recently covered it in class. If you want further help, you should include your thoughts about what you've tried and where you've gotten stuck. $\endgroup$ – Casteels Nov 27 '13 at 15:43
  • $\begingroup$ Okay thanks - have tried to think a lot about this one. Seems that 3 groups of 4 people and one group of 5 gets you the closest to it, leaving one person 'homeless'. From what I have tried it looks to be that it cannot be satisfied, its just proving it that gives me a problem. Is it something along the lines of it having a remainder and the fact that 17 is not a multiple of 4? Seems that if the number of students was 16 or 20 it would be possible? @Casteels $\endgroup$ – user111860 Nov 27 '13 at 19:55
  • $\begingroup$ kaine's hint is the right way to go. But you've almost got the first part: no matter how the first partition goes, at least one group must have $5$ kids in it. Now in the second partition, these $5$ kids must be split into $4$ parts, so... $\endgroup$ – Casteels Nov 27 '13 at 20:01
  • $\begingroup$ @Casteels oh okay, so the smallest number of kids in the largest group would be 5, and where you try and split them into 4 groups so none of them are all together, well, it just cant be done and hence the pigeonhole principle as you are going to always have at least one that just cant follow the rule! Is there a way of being able to formally write this down, or would just saying this be enough? $\endgroup$ – user111860 Nov 27 '13 at 20:14
  • $\begingroup$ Yes explain it in words like that. But "and hence the pigeonhole principle" isn't good wording. You would want to write something like "by the pigeonhole principle." (Maybe look to see if there are example problems in your textbook or done in class, and try to imitate their wording.) $\endgroup$ – Casteels Nov 27 '13 at 20:29

Hint: What is the smallest possible number of students in the largest group for the first essay? What happens when you try to split them into 4 different groups?


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.