MathDB
Points of a grid

Source: Iran 3rd round 2012-Special Lesson exam-Part1-P4

July 27, 2012
probabilityexpected valuecombinatorics proposedcombinatorics

Problem Statement

Prove that from an n×nn\times n grid, one can find Ω(n53)\Omega (n^{\frac{5}{3}}) points such that no four of them are vertices of a square with sides parallel to lines of the grid. Imagine yourself as Erdos (!) and guess what is the best exponent instead of 53\frac{5}{3}!
Back to ProblemsView on AoPS