Rainbow-Free Colorings

★ 9/10combinatorics Arithmetic Progression number theory Induction Extremal Principle

Problem

Color $1, 2, \dots, n$ with $k$ colors so that no three distinctly colored numbers form an arithmetic progression. Let $f(n)$ be the largest such $k$ . Prove that

\log_3 n \le f(n) \le \log_2 n + 1.

Answer

Solution

Difficulty	9/10
Topics	combinatorics, Arithmetic Progression, number theory, Induction, Extremal Principle

Whiteboard

Your sketch is saved only in this browser. To share it, export your drawing as an image (whiteboard menu → Export as → PNG), then upload that image in the comments below.

Discussion

Ask questions, share alternate solutions, and use LaTeX freely.

0 comments

No comments yet.