0

Wondering if anyone is able to give help for this question (doing for my own learning, can't find any material online).

Let’s say that an era is a historical time period with a definitive start date and definitive end date. For example, the Meiji Era ran from October 23, 1868 to July 30, 1912, and the Cuban Missile Crisis ran from October 16, 1962 to October 28, 1962. For simplicity, we’ll assume that these time ranges include the entirety of their start and end dates. Prove that no matter how you choose any fifty eras from history, you can either (1) find a date that’s contained in at least eight of those eras, or (2) find eight eras of which no two have any days in common.

KohLP
  • 43
  • 1
    The modelization of this issue should hopefuly use interval graphs – Jean Marie Apr 10 '21 at 14:45
  • If we have a set of eras, no two of which are pairwise disjoint, then there is a date in all of them. (This is the same point that Jean Marie made about interval graphs.) – saulspatz Apr 10 '21 at 14:55
  • Another reference on interval graphs: https://hal.archives-ouvertes.fr/file/index/docid/141338/filename/Paper.pdf – Jean Marie Apr 10 '21 at 15:20
  • Thank you so much for the help. Can I clarify if this would be a right approach: Recognize that it is an interval graph with 50 nodes, then restrict independence number to be less than equal to 7, then by theorem that independence no x chromatic number >= n for graph with n nodes, show that chromatic number >= 8. For interval graphs, chromatic number = clique number, hence clique number >= 8. The clique of size 8 has a date that appears in all represented intervals. – KohLP Apr 10 '21 at 15:37

1 Answers1

2

Sort the eras in increasing order of starting date. Now we try to organize the eras into $7$ slots as follows. For each era $E$, put $E$ into the lowest-numbered slot whose last era, if any, ends before $E$ starts. (It may be easier to think of this in terms of scheduling conference rooms. A hotel has $7$ conference rooms, and must schedule $50$ conferences, each with a stated start and end time.)

We may assume that there are no $8$ eras with a common date, for otherwise, we are done. Then when we come to assign a new era to a slot, there must be a slot free, and we can carry out the assignment of all the eras. Then since $7^2=49$, one of the slots must get at least $8$ eras, by the pigeonhole principle. But then by construction, no two of these $8$ eras have a date in common.

saulspatz
  • 53,131