MATH301 - Assignment 3 - Solved

1.       Write a short essay (300-400 words) on the life and work of Issai Schur.

2.       Write a short essay (300-400 words) on the life and work of Richard Rado.

3.       (a) Use van der Waerden’s Theorem to prove the following statement:

Let c : N → {1,2} be a 2-colouring of N and let k ∈ N. There exists at least one colour i ∈ {1,2} such that there is an infinite number of monochromatic k-term arithmetic progressions in that colour.

(b)    If in the first part of this exercise you replace “a 2-colouring” by “an r-colouring, r ≥ 2,” would the statement still be true? In other words, is it true that for any finite colouring of the natural numbers and any (fixed) k ∈ N there is always an infinite number of monochromatic k-term arithmetic progressions in a single colour? Why yes, or why not!

(c)    If in the first part of this exercise you replace “an infinite number of monochromatic k-term arithmetic progressions” by “an infinite monochromatic progression,” would the statement still be true? In other words, is it true that for any 2-colouring of the natural numbers there is always an infinite monochromatic arithmetic progressions? Why yes, or why not!

4.       The upper density of a set A ⊂ N is defined as

 .

Szemer´edi’s theorem states that any set of integers with positive upper density contains an arithmetic progression of any length.

Let A = {ai : i ∈ N} ⊆ N be a set with bounded gaps, i.e. let d ∈ N be such that

0 < ai+1 − ai ≤ d, for all i ∈ N.

In addition suppose that a1 = 1.

(a)    Show that for any n ≥ d

 .

(b)    Conclude that the upper density of A is at least 1/d.

(c)    Use Szemer´edi’s theorem to conclude that A contains arithmetic progressions of any finite length.

Note: The assumption a1 = 1 was there only to simplify your calculations. It is true that any set with bounded gaps has a positive density and that, consequently, it contains arithmetic progressions of any finite length.

5.       Two players play the following game. On an one-way endless checkered strip, the first player puts one triangle into a free cell, and the second player puts 1000 zeroes in free cells.The goal of the first player is to create an arithmetic progression of triangles of length 3, and the goal of the second player is to prevent him.

1

(a)    Prove that the first player has a winning strategy.

(b)    What would happen if the players switch the order who starts the game?

(c)    What would happen if the goal of the game is to create an arithmetic progression of crosses of length k, k > 3?

6.       Prove that any equinumerous 3-colouring of the set [1,9] = {1,2,3,4,5,6,7,8,9} contains a rainbow solution of Schur’s equation x + y = z.

[Here, equinumerous 3-colouring means that each colour is used exactly three times and a rainbow solution means that x,y,z are all coloured differently.