USAMO 2009 Problem 3

I found a different solution to the second part of this problem.

We define a chessboard polygon to be a polygon whose edges 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 squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping \(1\times 2\) rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a \(3\times 4\) rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.

a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.

b) Prove that such a tasteful tiling is unique.

===============================================

Sol:

a)

There must be an upper right corner of the polygon \(P\). If it's white, cover it with a vertical domino and then tile the rest by induction. Otherwise cover it with a horizontal. It is clear that this domino doesn't form distasteful tiling with the rest.

b)

Suppose there are two different tasteful tilings, then they form a chain surrounding a non-empty chessboard polygon \(R\) with a tasteful tiling because of induction. We show that walking counterclockwise along the perimeter of such surrounded \(R\) we can always find a domino with B following W, which we call bad domino, and making one of the tilings distasteful. This is proved by induction. Given any surrounded tasteful tiling with at least a bad domino, we will prove that adding any other domino does not decrease the number of bad dominoes. Suppose the bad domino is W above B somewhere locally rightmost in \(R\). The new domino covers either W or B to its right, but not both as that'd be distasteful. However no matter what the new domino will be bad, which concludes the proof.

USAMO 2017 Problem 2

Let \(m_1, m_2, \ldots, m_n\) be a collection of \(n\) positive integers, not necessarily distinct. For any sequence of integers \(A = (a_1, \ldots, a_n)\) and any permutation \(w = w_1, \ldots, w_n\) of \(m_1, \ldots, m_n\), define an \(A\)-inversion of \(w\) to be a pair of entries \(w_i, w_j\) with \(i < j\) for which one of the following conditions holds:

\(a_i \ge w_i > w_j\),
\(w_j > a_i \ge w_i\),
\(w_i > w_j > a_i\).

Show that, for any two sequences of integers \(A = (a_1, \ldots, a_n)\) and \(B = (b_1, \ldots, b_n)\), and for any positive integer \(k\), the number of permutations of \(m_1, \ldots, m_n\) having exactly \(k\) \(A\)-inversions is equal to the number of permutations of \(m_1, \ldots, m_n\) having exactly \(k\) \(B\)-inversions.

==========================================================

Proof:

It suffices to show that swapping any \(a_i\) with \(a_{i+1}\) does not alter the distribution of number of \(A\)-inversions, as then any sequence \(A\) could be transformed to any other sequence \(B\) with a combination of such swapping and update of the last element \(a_n\).

USAMO 2008 Problem 3

The problem is rephrased.

Q: A diamond of size n consists of 2n rows of nodes with lengths from top to bottom being 1, 3, 5, ..., 2n-1, 2n-1, 2n-3, ..., 3, 1. The middle nodes of all rows are in the same column. For instance the following '+' show a diamond of size 3:

##+##

#+++#

+++++

+++++

#+++#

##+##

We want to partition each diamond into acyclic paths such that each node is contained in exactly one path. A path is a sequence of distinct nodes in which neighboring nodes are horizontally or vertically adjacent. Prove that for diamond of size n the number of paths is at least n.

Proof:

We'll prove by induction. The case for n=1 is trivial. Now as an example consider a diamond of size 4. We draw part of it below where 'X' denote nodes of diamond we don't quite care:

A

BC

XDE

XXFG

XXIH

XLJ

NP

Q

A useful argument we name OA (optimality argument) is that if a node has only one neighbor, connecting it to its neighbor doesn't affect optimality. Suppose x has only one neighbor y and is not connected to y. If in some optimal partitioning y is an endpoint of some path, certainly adding x to that path reduces number of paths; if y is in the middle of some path, splitting that path at y and connecting x with y gives the same number of paths.

With OA, we connect AB. If C is connected with B then regard ABC as a super node C' with only one neighbor D; if C is not connected with B then C has only one neighbor D. In either case we are allowed to connect C with D using OA. Similarly, either E or super node CDE or super node ABCDE has only one neighbor F and thus we connect E with F. By symmetry we connect N with Q, L with P, I with J.

Next we argue that at least one pair of FG and IH can be connected. If not, G and H should be connected for optimality and is regarded as a super node; if EFIJ is a sub-path then EFGHIJ reduces number of paths by 1; if EFIJ is not a sub-path then we can split EFX... and attach GH to F without increasing number of paths. In either case, connecting FG or IH does not affect optimality.

Suppose FG is connected. Because from G we can't go beyond Q and never reach D, we connect DE and hence BC. Now ABCDEFG is a super node with one neighbor H so we connect GH, IH, JL, NP in order. This leaves us a path that can't be further extended and the rest is a diamond of size 3.

Q. E. D.

USAMO 2017 Problem 4

Let \(P_1, P_2, \dots, P_{2n}\) be \(2n\) distinct points on the unit circle \(x^2+y^2=1\), other than \((1,0)\). Each point is colored either red or blue, with exactly \(n\) red points and \(n\) blue points. Let \(R_1, R_2, \dots, R_n\) be any ordering of the red points. Let \(B_1\) be the nearest blue point to \(R_1\) traveling counterclockwise around the circle starting from \(R_1\). Then let \(B_2\) be the nearest of the remaining blue points to \(R_2\) traveling counterclockwise around the circle from \(R_2\), and so on, until we have labeled all of the blue points \(B_1, \dots, B_n\). Show that the number of counterclockwise arcs of the form \(R_i \to B_i\) that contain the point \((1,0)\) is independent of the way we chose the ordering \(R_1, \dots, R_n\) of the red points.

==================================================================

Solution:

Show that swapping \(R_i\) and \(R_{i+1}\) does not change the number of arcs crossing \((1,0)\).