Problems
John’s father is 28 years older than John and next year he will be exactly three times the age of John. How old is John’s father?
You have an hourglass that measures 8 minutes and an hourglass that measures 12 minutes. How can you measure exactly 44 minutes with them?
Joe has two kinds of weights: 15 grams and 50 grams. He has an infinite supply of each type. Can you help him find a combination that is exactly 310 grams?
You may have seen the first example (seen below) previously. Before we get to that, let’s introduce some notation. We write \(K_n\) for the _complete_ graph on \(n\) vertices - that is, every possible edge is present.
Note that edges don’t have a direction, and are between pairs of different vertices. Ramsey theory looks at what happens when we colour every edge in \(K_n\) either red or blue. Are we guaranteed a red \(K_3\) subgraph? No, because we could just colour every edge in \(K_n\) blue. Instead, we ask if we are guaranteed a red \(K_3\) or a blue \(K_3\) subgraph? It turns out yes, so long as \(n\) is big enough.
We can then look at extensions to this problem. We write \(R(s,t)\) for the least number \(n\) such that whenever you colour the edges of \(K_n\) in red or blue, then you’re guaranteed a red \(K_s\) or a blue \(K_t\). By least \(n\), this means that there’s a colouring of the edges of \(K_{n-1}\) with no red \(K_s\) or blue \(K_t\).
Find a formula for \(R(2,k)\), where \(k\) is a natural number.
Show that \(R(4,3)\ge9\). That is, there exists a way of colouring the edges of \(K_8\) with no red \(K_4\), nor any blue \(K_3\).