[Math] Picking A Certain Number Of Days Proof

discrete mathematicsproof-writing

The Problem is:

Show that at least ten of any 64 days chosen must fall on the same day of the week.

I know that in order to prove this, it's best to use a proof by contradiction.

So, let's assume that if you choose 64 days at random, then, at most, nine of those days will be the same day of the week.

To be honest, I am not sure how to proceed after this initial step.

Best Answer

You have started correctly.

Suppose no day of week has more than $9$ members.

So, the number of days will be $\le 9\cdot7=63$


Alternatively,

If we distribute $63$ days among available $7$ days of week, if none of the $7$ days has $>9$ members, each will have exactly $9$ days each.

Now, the remaining $64$th day will be added to one of the $7$ days of week to make it $10$ member team:)

Related Question