MathDB

3

Part of 2003 All-Russian Olympiad

Problems(6)

Given 2k −1 white segments and 2k −1 black ones

Source:

11/3/2010
On a line are given 2k−12k -1 white segments and 2k−12k -1 black ones. Assume that each white segment intersects at least kk black segments, and each black segment intersects at least kk white ones. Prove that there are a black segment intersecting all the white ones, and a white segment intersecting all the black ones.
pigeonhole principlesymmetrycombinatorics proposedcombinatorics
A tree with numbers in vertices and edges

Source: All-Russian Olympiad, 2003, grade 10, day 1, no. 3

9/1/2011
A tree with n≥2n\geq 2 vertices is given. (A tree is a connected graph without cycles.) The vertices of the tree have real numbers x1,x2,…,xnx_1,x_2,\dots,x_n associated with them. Each edge is associated with the product of the two numbers corresponding to the vertices it connects. Let SS be a sum of number across all edges. Prove that n−1(x12+x22+⋯+xn2)≥2S.\sqrt{n-1}\left(x_1^2+x_2^2+\dots+x_n^2\right)\geq 2S.
(Author: V. Dolnikov)
inductioninequalitiescombinatorics
write a natural number in all cell of an infinite chessboard

Source:

11/3/2010
Is it possible to write a natural number in every cell of an infinite chessboard in such a manner that for all integers m,n>100m, n > 100, the sum of numbers in every m×nm\times n rectangle is divisible by m+n ?m + n \ ?
geometryrectanglecombinatorics proposedcombinatorics
Points O,N, I lie on a line [Russia 2003]

Source:

11/4/2010
In a triangle ABC,OABC, O is the circumcenter and II the incenter. The excircle ωa\omega_a touches rays AB,ACAB,AC and side BCBC at K,M,NK,M,N, respectively. Prove that if the midpoint PP of KMKM lies on the circumcircle of △ABC\triangle ABC, then points O,N,IO,N, I lie on a line.
geometrycircumcirclegeometry unsolved
Show that if b > m, then f = g [Russia 2003]

Source:

11/4/2010
Let f(x)f(x) and g(x)g(x) be polynomials with non-negative integer coefficients, and let m be the largest coefficient of f.f. Suppose that there exist natural numbers a<ba < b such that f(a)=g(a)f(a) = g(a) and f(b)=g(b)f(b) = g(b). Show that if b>m,b > m, then f=g.f = g.
algebrapolynomialalgebra unsolved
Russia 2003

Source:

10/31/2010
There are 100100 cities in a country, some of them being joined by roads. Any four cities are connected to each other by at least two roads. Assume that there is no path passing through every city exactly once. Prove that there are two cities such that every other city is connected to at least one of them.
combinatorics unsolvedcombinatorics