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.

  • $\begingroup$ I guess what confusing me most is, are we picking one day from each week, or are we also picking multiple days from each week? $\endgroup$ – Mack Feb 14 '13 at 16:21
  • $\begingroup$ I'll try to clarify in a different language: You have 64 random dates - collected from any year/decade/century/whatever. The question simply asks that in any such collection of random 64 dates (not necessarily distinct), atleast 10 dates would fall on the same day - eg. atleast 10 would be a Monday (or a Tuesday etc.). $\endgroup$ – Paresh Feb 14 '13 at 16:24
  • $\begingroup$ If at most nine of the chosen days fall on each day of the week, then the total numbers of days is at most seven times nine, i.e., $\le 63$. $\endgroup$ – mjqxxxx Feb 14 '13 at 16:29

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.

| cite | improve this answer | |
  • $\begingroup$ So, the way the question is worded is ambiguous? As you said, it is possible that you could 64 Thursdays, seeing as random isn't consider. $\endgroup$ – Mack Feb 14 '13 at 16:40
  • $\begingroup$ I think the question wording is not ambiguous $\endgroup$ – Hagen von Eitzen Feb 14 '13 at 16:43
  • $\begingroup$ @EliMackenzie: I don't think the question is ambiguous. It doesn't ask about picks from the particular 7-element set {Mo,Tu,We,Th,Fr,Sa,So}. It asks you to pick actual days. For example, the set of all Thursdays between 1 December 2011 and today (inclusive) is a set of 64 (different) Thursdays. $\endgroup$ – hmakholm left over Monica Feb 14 '13 at 16:48
  • $\begingroup$ Hmm, I guess I am having trouble seeing why we simply multiply 7 by 9, and how that creates a contradiction. $\endgroup$ – Mack Feb 14 '13 at 16:50
  • 1
    $\begingroup$ @Eli: We ask: What's the largest size a set of days can have if it contains at most 9 Mondays, at most 9 Tuesdays, at most 9 Wednesdays, and so forth? Clearly we get the largest set by using up our entire allowance of each weekday, so the largest possible set that satisfies the condition has size 9+9+9+9+9+9+9, one nine for each weekday name. That is the same as $9\times 7=63$, and since $64$ is larger than that, there is no set of 64 days that satisfies the condition. $\endgroup$ – hmakholm left over Monica Feb 14 '13 at 16:56

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$


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

| cite | improve this answer | |
  • $\begingroup$ Classic use of the pigeonhole principle (extended version). $\endgroup$ – vonbrand Feb 15 '13 at 1:58

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.