proof by contradiction example 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. 
 A: 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?
A: 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.
A: Hint: There are $12$ months in a year and $25 = 2\cdot 12 + 1$.
A: 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.
