Subcontests
(6)Tasteful domino tilings
We define a chessboard polygon to be a polygon whose sides are situated along lines of the form x \equal{} a or y \equal{} 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×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×4 rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.
[asy]size(300); pathpen = linewidth(2.5);
void chessboard(int a, int b, pair P){
for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j)
if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6));
D(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle);
}
chessboard(2,2,(2.5,0));fill(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6)); chessboard(4,3,(6,0)); chessboard(4,3,(11,0)); MP("\mathrm{Distasteful\ tilings}",(2.25,3),fontsize(12)); /* draw lines */
D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1)); D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3));[/asy] 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. Rational sequences
Let s1,s2,s3,… be an infinite, nonconstant sequence of rational numbers, meaning it is not the case that s1=s2=s3=…. Suppose that t1,t2,t3,… is also an infinite, nonconstant sequence of rational numbers with the property that (si−sj)(ti−tj) is an integer for all i and j. Prove that there exists a rational number r such that (si−sj)r and (ti−tj)/r are integers for all i and j. Inequality in a_1, ... a_n
For n≥2 let a1,a2,…an be positive real numbers such that
(a_1 \plus{} a_2 \plus{} \cdots \plus{} a_n)\left(\frac {1}{a_1} \plus{} \frac {1}{a_2} \plus{} \cdots \plus{} \frac {1}{a_n}\right) \leq \left(n \plus{} \frac {1}{2}\right)^2.
Prove that max(a1,a2,…,an)≤4min(a1,a2,…,an). Largest subset
Let n be a positive integer. Determine the size of the largest subset of {−n,−n+1,…,n−1,n} which does not contain three elements a, b, c (not necessarily distinct) satisfying a+b+c=0.