Deriving Van der Waerden Theorem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

11 users

TOPICS

No tags match your search

M

No tags match your search

M

Deriving Van der Waerden Theorem

G H J

Reveal topic tags

arithmetic sequence

Van der Waerden number

L

G H BBookmark kLocked kLocked NReply

Source: Khamovniki 2023-2024 (group 10-1)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

72 posts

#1 h Mar 29, 2025, 5:18 PM

Y by

Suppose we have already proved that for any coloring of $\Large \mathbb{N}$ in $r$ colors, there exists an arithmetic progression of size $k$ . How can we derive Van der Waerden's theorem for $W(r, k)$ from this?

This post has been edited 2 times. Last edited by Didier2, Mar 29, 2025, 5:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

72 posts

#2 h Monday at 8:04 AM

Y by

My attempt to revive the topic).

I found a solution which uses induction on $r$ and Szemeredi's theorem. But this is, obviously, not the intended solution and so I wonder if there exists a solution which uses nothing but relatively elementary methods (maybe even the same induction on $r$ , or on $k$ ). Thank you.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

65 posts

#3 h Monday at 10:13 AM • 1 Y

Y by Didier2

There is a theorem of compactness which states the following:
Let $X=\left\{x_1,x_2,...\right\}$ be a countable set and let A be some set of finite subsets of X.
Suppose for some natural k that for every k coloring of X, A must contain a monochromatic set.
The theorem states that there exists some n (dependent on k) such that for every k coloring of $\left\{x_1,...,x_n\right\}$ , A contains a monochromatic set.

For our case we take A to be all arithmetic progressions of size k and $X=\mathbb{N}$ , this immediately implies Van der Waerden.

You are welcome to try proving this theorem yourself, it only uses pure combinatorical arguments which don't require any extensive prior knowledge.

This post has been edited 2 times. Last edited by rrrMath, Monday at 10:17 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

72 posts

#4 h Yesterday at 8:01 AM

Y by

Nice, thank you very much! Can we prove it by contradiction?

If we suppose that for $\forall n$ , there $\exists$ a $k$ -coloring $C_n$ of $\{x_1, \dots, x_n \}$ such that $A$ doesn't contain monochromatic set. Then by Dirichlet, there must be infinitely many colorings $C_{n_1} \subset C_n$ , such that $\{x_1\}$ are all colored in the same way. If repeat the argument for the $C_{n_1}$ , then there are infinitely many $C_{n_2} \subset C_{n_1}$ , so that the $\{x_1, x_2 \}$ are all colored in the same way. And so on. We will be gradually constructing the coloring of $\Large X$ , call it $C$ , where for any prefix $\{x_1, x_2, \dots, x_m \}$ there is no monochromatic set in $A$ if we only color this prefix. By the assumption, $C$ contains some monochromatic set $\{x_{a_1}, x_{a_2}, \dots, x_{a_s}\} \in A$ . But that means if we only color prefix $\{x_1, x_2, \dots, x_{a_s}\}$ there exists a monochromatic set of $A$ , which is a contradiction to the construction of $C$

This post has been edited 2 times. Last edited by Didier2, Yesterday at 8:30 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a