ELMO Shortlist 2012 C8

Consider the equilateral triangular lattice in the complex plane defined by the Eisenstein integers; let the ordered pair (x,y) denote the complex number x+y\omega for \omega=e^{2\pi i/3}. We define an \omega-chessboard polygon to be a (non self-intersecting) polygon whose sides are situated along lines of the form x=a or y=b, where a and b are integers. These lines divide the interior into unit triangles, which are shaded alternately black and white so that adjacent triangles have different colors. To tile an \omega-chessboard polygon by lozenges is to exactly cover the polygon by non-overlapping rhombuses consisting of two bordering triangles. Finally, a tasteful tiling is one such that for every unit hexagon tiled by three lozenges, each lozenge has a black triangle on its left (defined by clockwise orientation) and a white triangle on its right (so the lozenges are BW, BW, BW in clockwise order).

a) Prove that if an \omega-chessboard polygon can be tiled by lozenges, then it can be done so tastefully.

b) Prove that such a tasteful tiling is unique.


ELMO Shortlist 2012 C9

For a set A of integers, define f(A)=\{x^2+xy+y^2: x,y\in A\}. Is there a constant c such that for all positive integers n, there exists a set A of size n such that |f(A)|\le cn?

On sets defining few ordinary lines

What's new

Ben Green and I have just uploaded to the arXiv our new paper “On sets defining few ordinary lines“, submitted to Discrete and Computational Geometry. This paper asymptotically solves two old questions concerning finite configurations of points $latex {P}&fg=000000$ in the plane $latex {{mathbb R}^2}&fg=000000$. Given a set $latex {P}&fg=000000$ of $latex {n}&fg=000000$ points in the plane, define an ordinary line to be a line containing exactly two points of $latex {P}&fg=000000$. The classical Sylvester-Gallai theorem, first posed as a problem by Sylvester in 1893, asserts that as long as the points of $latex {P}&fg=000000$ are not all collinear, $latex {P}&fg=000000$ defines at least one ordinary line:

It is then natural to pose the question of what is the minimal number of ordinary lines that a set of $latex {n}&fg=000000$ non-collinear points can generate. In 1940, Melchior gave an elegant proof of the Sylvester-Gallai theorem based…

View original post 4,423 more words