MathDB

2

Part of 2009 Romania Team Selection Test

Problems(7)

Operations on a matrix

Source: Romania TST 1 2009, Problem 2

5/4/2012
Consider a matrix whose entries are integers. Adding a same integer to all entries on a same row, or on a same column, is called an operation. It is given that, for infinitely many positive integers nn, one can obtain, through a finite number of operations, a matrix having all entries divisible by nn. Prove that, through a finite number of operations, one can obtain the null matrix.
linear algebramatrixcombinatorics proposedcombinatorics
A square with a colourful line

Source: Romania TST 2 2009, Problem 2

5/4/2012
A square of side N=n2+1N=n^2+1, n∈N∗n\in \mathbb{N}^*, is partitioned in unit squares (of side 11), along NN rows and NN columns. The N2N^2 unit squares are colored using NN colors, NN squares with each color. Prove that for any coloring there exists a row or a column containing unit squares of at least n+1n+1 colors.
combinatoricspigeonhole principle
Simson line tangent to Euler circle

Source: Romania TST 3 2009, Problem 2

5/4/2012
Prove that the circumcircle of a triangle contains exactly 3 points whose Simson lines are tangent to the triangle's Euler circle and these points are the vertices of an equilateral triangle.
Eulergeometrycircumcirclegeometry proposed
Find all polynomials such that f(a) divides f(2a^k)

Source: Romania TST 6 2009, Problem 2

5/5/2012
Let nn and kk be positive integers. Find all monic polynomials f∈Z[X]f\in \mathbb{Z}[X], of degree nn, such that f(a)f(a) divides f(2ak)f(2a^k) for a∈Za\in \mathbb{Z} with f(a)≠0f(a)\neq 0.
algebrapolynomialalgebra proposed
Inequality for absolute values of vectors in plane

Source: Romania TST 4 2009, Problem 2

5/4/2012
Let m<nm<n be two positive integers, let II and JJ be two index sets such that ∣I∣=∣J∣=n|I|=|J|=n and ∣I∩J∣=m|I\cap J|=m, and let uku_k, k∈I∪Jk\in I\cup J be a collection of vectors in the Euclidean plane such that ∣∑i∈Iui∣=1=∣∑j∈Juj∣.|\sum_{i\in I}u_i|=1=|\sum_{j\in J}u_j|. Prove that ∑k∈I∪J∣uk∣2≥2m+n\sum_{k\in I\cup J}|u_k|^2\geq \frac{2}{m+n} and find the cases of equality.
inequalitiesvectorgeometry proposedgeometry
$n$ divides $a^{n-1}+a^{n-2}+\cdots+a+1$ (Romania TST 2009)

Source: Romania TST 5 2009, Problem

5/4/2012
Let aa and nn be two integers greater than 11. Prove that if nn divides (a−1)k(a-1)^k for some integer k≥2k\geq 2, then nn also divides an−1+an−2+⋯+a+1a^{n-1}+a^{n-2}+\cdots+a+1.
modular arithmeticnumber theory proposednumber theory
Orientability of planar graph

Source: Romania TST 7 2009, Problem 2

5/5/2012
Prove that the edges of a finite simple planar graph (with no loops, multiple edges) may be oriented in such a way that at most three fourths of the total number of dges of any cycle share the same orientation. Moreover, show that this is the best global bound possible.
Comment: The actual problem in the TST asked to prove that the edges can be 22-colored so that the same conclusion holds. Under this circumstances, the problem is wrong and a counterexample was found in the contest by Marius Tiba.
combinatorics proposedcombinatorics