Picking A Certain Number Of Days Proof

Question

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.

Answer 1

You're starting your indirect proof wrong. What you want to prove is

A: For every choice of 64 days, at least one day-of-the-week will be hit more than 9 times.

In order to conduct an indirect proof, you start by assuming the negation of (A). However that negation is not, as you write

B: if you choose 64 days at random, then, at most, nine of those days will be the same day of the week.

There's nothing about randomness in A, and negating a claim that's not about randomness does not make it into one. So if nothing else, you're making your task harder here by suddenly introducing randomness.

However, the negation of A is not even

C: For every choice of 64 days, at most nine of those days will be the same day of the week.

C is quite obviously false because nothing stops me from choosing 64 Thursdays, which will then be a counterexample. If C and A had been negations, then this would constitute an indirect proof of A -- but clearly and intuitively just because I can choose 64 Thursdays doesn't mean that every choice I can make must contain 10 of some day. (And indeed if the argument was valid, it would be hard to argue what would be wrong with the same proof with "63" instead of "9").

The actual negation of (A) is

D: There is at least one way to choose 64 days such that each day of the week is used at most 9 times.

If we assume that, we get something concrete to work with, namely a set $S$ of 64 days where each weekday appears at most 9 times. We can then begin to construct a contradiction, such as by verifying that the size of $S$ is 64 by adding the number of Mondays in the set to the number of Tuesdays, Wednesdays, and so on.

Answer 2

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:)

Answer 3

We have a set $S$ with 64 elements (the days we have chosen), to every one of them we associate an element of the set $W$ (the days of the week). If for every element $x$ of $W$ we can associate at most 9 elements of $S$, then our set $S$ can have at most $9\cdot 7 = 63$ elements, and this is a contradiction.