91Ó°ÊÓ

Prove that of any five points chosen within a square of side length 2, there are two whose distance apart is at most \(\sqrt{2}\).

(a) Prove that of any five points chosen within an equilateral triangle of side length 1, there are two whose distance apart is at most \(\frac{1}{2}\). (b) Prove that of any 10 points chosen within an equilateral triangle of side length 1 , there are two whose distance apart is at most \(\frac{1}{3}\). (c) Determine an integer \(m_{n}\) such that if \(m_{n}\) points are chosen within an equilateral triangle of side length 1, there are two whose distance apart is at most \(1 / n\).

The line segments joining 10 points are arbitrarily colored red or blue. Prove that there must exist three points such that the three line segments joining them are all red, or four points such that the six line segments joining them are all blue (that is, \(r(3,4) \leq 10)\).

Suppose that the \(m n\) people of a marching band are standing in a rectangular forination of \(m\) rows and \(n\) columns in such a way that in each row each person is taller than the one to his or her left. Suppose that the leader rearranges the people in each column in increasing order of height from front to back. Show that the rows are still arranged in increasing order of height from left to right.

A collection of subsets of \(\\{1,2, \ldots, n\\}\) has the property that each pair of subsets has at least one element in common. Prove that there are at most \(2^{n-1}\) subsets in the collection.

At a dance party there are 100 men and 20 women. For each \(i\) from \(1,2, \ldots, 100\), the ith man selects a group of \(a_{1}\) women as potential dance partners (his "dance list," if you will), but in such a way that given any group of 20 men, it is always possible to pair the 20 men with the 20 women, with each man paired with a woman on his dance list. What is the smallest sum \(a_{1}+a_{2}+\cdots+a_{100}\) for which there is a selection of dance lists that will guarantee this?