Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 9 / 1

Use $\mathbb{N}=\{1,2,\dots \}$. First recall the Ramsey theorem for r-sets in its infinite form: every finite colouring of the $r$-element subsets of an infinite countable set has an infinite homogeneous subset. Here is a proof, so the combinatorial input is explicit.

For $r=1$, this is the infinite pigeonhole principle. Suppose it holds for $r$. Given a colouring of $(r+1)$-sets, choose a first point $a_1$. Colour the $r$-sets in the remaining tail by adjoining $a_1$, and use the induction hypothesis to obtain an infinite tail on which that colouring is constant, with colour $d_1$. Choose $a_2$ from that tail and repeat, always thinning the unused tail. This produces increasing $a_i$, nested infinite reservoirs containing all later selected points, and colours $d_i$ such that every $(r+1)$-set of selected points whose least point is $a_i$ has colour $d_i$. Infinitely many $d_i$ are equal. Keeping the corresponding points gives an infinite homogeneous subset. This is a successive thinning proof of the infinite Ramsey theorem.

Now let $\chi$ be the given finite colouring of positive integers. Colour each unordered pair $\{a,b\}$, with $a<b$, by $\chi (a+2b)$. Apply the proved theorem with $r=2$, and enumerate its homogeneous set increasingly as $x_1<x_2<\cdots$. Thenfor one fixed colour $\gamma$. This proves the requested monochromatic pattern without requiring the $x_i$ themselves to have that colour.

For a positive integer $n$, let $v_2(n)$ be its 2-adic valuation and let $k(n)=\lfloor {\log }_{2}n\rfloor$. Use the four-colour dyadic valuation and scale colouringSuppose an increasing infinite sequence had all its two indicated kinds of pair sums in one colour. There are two exhaustive possibilities for its valuations.

If the valuations are bounded, infinitely many terms have one fixed valuation $t$. Among them, infinitely many have the same odd part modulo four. Choose two such terms $a<b$. Their odd parts have sum congruent to two modulo four, while the odd part of $a+2b$ is odd. HenceTheir first colour coordinates differ, contradicting monochromaticity.

If the valuations are unbounded, fix one term $a$ and choose a later $b$ with $2^{v_2(b)}>a$. Put $k=\lfloor {\log }_{2}b\rfloor$. The distance $2^{k+1}-b$ is a positive multiple of $2^{v_2(b)}$, so it exceeds $a$. Similarly $2^{k+2}-2b$ exceeds $a$. Therefore adding $a$ crosses neither upper dyadic boundary:Their second colour coordinates differ, again a contradiction. Thus this four-colouring admits no such increasing infinite sequence.

Apply the Ramsey theorem for r-sets, proved in part (i), with $r=4$ to the even positive integers. Colour the four-set $\{a,b,c,d\}$ with $a<b<c<d$ by $\chi (a+b+2c+2d)$. This gives increasing even integers $u_1<u_2<\cdots$ such that every such four-index expression has one colour $\gamma$.

For the simultaneous coefficient patterns from a homogeneous four-set colouring, setBoth sequences consist of positive integers and are strictly increasing. The evenness ensures that the shared half-prefix in $y_i$ is integral. For $i<j$, the two types of sum areandIn both expressions the four indices are strictly ordered, so their colour is $\gamma$. Therefore the union of the two families is monochromatic. The common half-prefix is what permits the second family to use the same coefficient pattern despite having different generating variables.