MATH301 Assignment 1 Solved

1. Write a short essay (300-400 words) on the life and work of Frank Ramsey.
2. Write a short essay (300-400 words) on the life and work of Paul Erd ̋os.
3. Between 1972 and 2012, the 411 Senior Centre occupied the historic 411 Dunsmuir Street building in Vancouver, British Columbia. The Centre was an important part of life for generations of elderly Vancouverites.

   With this example, we honour the memory of ten members of the Centre: Mirko, Wanda, John, Hubert, Ursula, Gadafi, two ladies remembered as the Librarian and the Volunteer, and two gentlemen remembered as the Miner and the Sailor.

   The 10 friends formed the “411 Ping Pong Club.”

   For the purpose of this example, we assume that between January 1, 1997, and December 31, 1998, four members of the 411 Ping Pong Club got together and played exactly one game of ping pong doubles.

   Prove that in this time period, there was some particular set of four members that had played at least four games of ping pong doubles together.

4. (a)

Color each point in the integer grid [1, 257] × [1, 4] Red, Green, or Blue. Show that some rectangle has all its vertices the same colour. In other words, show that for any function

f :{1,2,…,257}×{1,2,3,4}→{R,G,B}
there are a,b ∈ {1,2,…,257}, a < b, and c,d ∈ {1,2,3,4}, c < d, such that

f(a,c) = f(a,d) = f(b,c) = f(b,d).
(b) Colour each point in the xy plane having integer coefficients Red, Green, or Blue. Then

some rectangle has all its vertices the same colour.

5. You ask your computer to randomly pick, one by one, 50 positive integers. This generates a sequence a1, a2, . . . , a50, where the index i means that the integer ai was the i-th ran- domly picked positive integer. Observe that, since the whole process is random, the sequence a1, a2, . . . , a50 may not be ordered. In other words, for any i ≤ 49, ai+1 may be greater than or equal to or less than ai.

After generating several sequences, you notice that each time you can find at least 8 members of the sequence, say ai1 , ai2 , . . . , ai8 , that form a nondecreasing subsequence, i.e. for each j ∈ {1,…,7}

aij+1 ≥aij,
OR that they form a nonincreasing subsequence, i.e. for each j ∈ {1, . . . , 7}

aij+1 ≤aij.
You wonder if this is just a coincidence or it is true that something like this must always

happen.
What would you do?

Note: Actually, it is true that any sequence of n2 + 1 positive integers, there exists a nonde- creasing or a nonincreasing sequence of length n + 1. Can you prove this statement?

1

6. Show that R(3,3,3) ≤ 17. (This means: Every 3-colouring of the edges of K17 gives a monochromatic K3.)

2