Problems

Alice and Bob were playing outdoors. A mean lady told them that at least one of them has a muddy face and everyone who has a muddy face must step forward at the same time on the count of three. Then the mean lady will leave them alone.

If a child with clean face steps forward, he is punished. If nobody steps forward, then the mean lady will do the count again. The children are not allowed to signal to each other. How can Alice and Bob avoid punishment?

Alice, Bob and Claire were playing outdoors. A mean lady told them that at least one of them has a muddy face and everyone who has a muddy face must step forward at the same time on the count of three. Then the mean lady will leave them alone.

If a child with clean face steps forward, he is punished. If nobody steps forward, then the mean lady will do the count again. The children are not allowed to signal to each other. How can Alice, Bob and Claire avoid punishment?

Alice, Bob, Claire and Daniel were playing outdoors. A mean lady told them that at least one of them has a muddy face and everyone who has a muddy face must step forward at the same time on the count of three. Then the mean lady will leave them alone.

If a child with clean face steps forward, he is punished. If nobody steps forward, then the mean lady will do the count again. The children are not allowed to signal to each other. How can Alice, Bob, Claire and Daniel avoid punishment?

A group of children were playing outdoors. A mean lady told them that at least one of them has a muddy face and everyone who has a muddy face must step forward at the same time on the count of three. Then the mean lady will leave them alone.

If a child with clean face steps forward, he is punished. If nobody steps forward, then the mean lady will do the count again. The children are not allowed to signal to each other. How can they avoid punishment?

Sperner’s lemma in dimension \(2\).
Subdivide a triangle \(ABC\) arbitrarily into a triangulation consisting of smaller triangles meeting edge to edge. Define Sperner coloring of the triangulation as an assignment of three colors to the vertices of the triangulation such that:

• Each of the three vertices \(A, B,\) and \(C\) of the initial triangle has a distinct color

• The vertices that lie along any edge of triangle \(ABC\) have only two colors, the two colors at the endpoints of the edge. For example, each vertex on \(AC\) must have the same color as \(A\) or \(C.\)

Here is an example of Sperner’s triangulation

Prove that every Sperner coloring of every triangulation has at least one "rainbow triangle", a smaller triangle in the triangulation that has its vertices colored with all three different colors. More precisely, there must be an odd number of rainbow triangles.

We’ll look at ways of making big numbers today. Hopefully you know about _powers_ of numbers. Most of the biggest numbers you’ve seen probably involve powers. Powers are typically thought of as ’repeated multiplication’. You could think of this as being similar to how multiplication is ’repeated multiplication’.

We might use powers when decimal representation is far too long to be useful for understanding the size of an object.

But what if powers aren’t helpful enough? Mathematician and computer scientist Donald Knuth introduced Knuth’s up-arrow notation. A single up-arrow means ’raise to the power of’. So \(2\uparrow5=2^5=2\times2\times2\times2\times2=32\). Recall that the \(5\) means we have five \(2\)s. Two arrows means ’tetration’. For example \(2\uparrow\uparrow4=2\uparrow(2\uparrow(2\uparrow2))=2^{(2^{(2^2)})}=2^{(2^4)}=2^{16}=65536\). The \(4\) means that we have four \(2\)s. Three arrows means pentation. So \(2\uparrow\uparrow\uparrow3=2\uparrow\uparrow(2\uparrow\uparrow2)\). Here the \(3\) means that there are three \(2\)s. Remember that \(2\uparrow\uparrow2=2\uparrow2=2^2=4\). So \(2\uparrow\uparrow\uparrow3=2\uparrow\uparrow4=65536\).

A million is \(10^6\) and a billion is \(10^9\). A million seconds is about eleven and a half days. A billion seconds is about 31 years. Other famous big numbers are googol, Skewes’ number, Graham’s number, busy beaver and TREE(3). Another classic big number is the number of atoms in the observable universe - about \(10^{80}\). This is less than \(4\uparrow\uparrow3\), \(3\uparrow\uparrow\uparrow3\), or \(2\uparrow\uparrow\uparrow\uparrow3\).

A couple of these problems are Fermi problems, named after physicist Enrico Fermi. This is where you try to estimate a quantity in the real world. We’re not expecting an exact answer (indeed, we don’t know the exact answer), but using some intelligent estimation, you can get a good idea of the answer.

What’s \(3\uparrow\uparrow3\)?

Is \(4^{15}\) more or less than a billion?

Approximately how many footsteps do I take in a year? (estimate to the nearest power of \(10\))

What’s \(2\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow2\)?