[Math] Proof : Do 4 days fall on the same day

discrete mathematicsproof-writing

I was working my way through some discrete math proof examples from Discrete Math by Rosen and being a newbie am stuck on this problem :

Show that at least four of any 22 days must fall on the same day of the week

Book Solution:

  • Let p be the proposition “At least four of 22 chosen days fall on the same day of the
    week.”

  • Suppose that ¬p is true

  • This means that at most three of the 22 days fall on the same day of the week.

  • Because there are seven days of the week, this implies that at most 21 days could have been chosen, as for each of the days of the week, at most three of the chosen days
    could fall on that day.

  • This contradicts the premise that we have 22 days under consideration.

  • That is, if r is the statement that 22 days are chosen, then we have shown that ¬p → (r ∧¬r).

  • Consequently, we know that p is true

  • We have proved that at least four of 22 chosen days fall on the same day of the week.

My Question :

I am unable to understand this explanation — can anyone help me out ?

Best Answer

The idea here is you assume the opposite of what you want to prove, then show that leads to a contradiction, a statement which is false. Therefore, the false assumption is false, so you get what you wanted.

Here, you want to show the statement "At least 4 of any 22 days chosen must be on the same day of the week". So, assuming the opposite. The opposite of a statement of the form "at least 4" means "at most 3". So, assuming at most 3 is on the same day of the week, of your 22 random days chosen out of a year (or a month, or wherever we are choosing the days from), we have as possibilities: 0-3 mondays, 0-3 tuesdays, 0-3 wednesdays, 0-3 thursdays, etc. So the amount of chosen days can range form 0 to 21 (3*7), if its a maximum of 3 in each day.

But we're supposed to pick 22 days! once we have 3 of each day of the week, where does that extra day go? Whichever day it goes into will have 4...this is known as the "pigeonhole principle": If you have n+1 objects going into n holes, at least 1 hole gets more than 1 object.

Thus, one of the days of the week will be represented 4 times. This contradicts your assumption that it won't happen, so we know the assumption could not be true. Therefore we have the OPPOSITE of your assumption: at least 4 of the days are on the same day of the week

Related Question