4

Any ideas on how I can use proof by contradiction to show that at least 3 of any 25 days chosen must fall in the same month of the year?

I don't even understand the question.

4 Answers4

3

Pick any $25$ different dates in $2013$ (or any other year), like $13$ May, $27$ June, etc. The claim is that no matter which $25$ dates you pick, at least three of them will be in the same month.

HINT: Suppose that you picked at most two dates from each month of the year; what’s the largest number of dates that you could possibly pick?

Brian M. Scott
  • 616,228
  • Suppose for contradiction at least two of any days chosen must fall in the same month of the year. So the largest number of dates we can possibly pick is $2 X 12 =24$. So this contradicts our assumption of $25$ days. English is my second language so it's a bit difficult for me sometimes to understand word problems. –  Oct 25 '13 at 19:47
  • @AJR: You need to make one small change, and your argument will be fine: where you have at least two it should be at most two. – Brian M. Scott Oct 25 '13 at 19:53
2

There are 12 months in a year. Suppose we are given 25 distinct days and no three of them fall in the same month. Then at most 2 fall in each month, so we calculate that we have been given at most $2 \times 12 =24$ days. This is the contradiction that proves our assumption that no three of them fall in the same month must be false.

This strategy of proof is sometimes called the "pigeonhole principle", which you can google to learn more.

TBrendle
  • 3,253
0

Hint: There are $12$ months in a year and $25 = 2\cdot 12 + 1$.

njguliyev
  • 14,473
  • 1
  • 26
  • 43
0

Suppose this is false. This would imply that there was some way pick 25 days of the calendar year so that each month contains either $0, 1$ or $2$ of the days. But how can this ever add up to $25$ days? This leads to a contradiction. So the statement we thought was false must be true.