MathDB

4

Part of 2012 Iran MO (3rd Round)

Problems(7)

Points of a grid

Source: Iran 3rd round 2012-Special Lesson exam-Part1-P4

7/27/2012
Prove that from an n×nn\times n grid, one can find Ω(n53)\Omega (n^{\frac{5}{3}}) points such that no four of them are vertices of a square with sides parallel to lines of the grid. Imagine yourself as Erdos (!) and guess what is the best exponent instead of 53\frac{5}{3}!
probabilityexpected valuecombinatorics proposedcombinatorics
Finding a subsquare from the main square

Source: Iran 3rd round 2012-Special Lesson exam-Part 2-P4

9/15/2012
Prove that if nn is large enough, in every n×nn\times n square that a natural number is written on each one of its cells, one can find a subsquare from the main square such that the sum of the numbers is this subsquare is divisible by 13911391.
linear algebramatrixcombinatorics proposedcombinatorics
Two polynomials, a division

Source: Iran 3rd round 2011-Number Theory exam-P3

9/19/2012
P(x)P(x) and Q(x)Q(x) are two polynomials with integer coefficients such that P(x)∣Q(x)2+1P(x)|Q(x)^2+1.
a) Prove that there exists polynomials A(x)A(x) and B(x)B(x) with rational coefficients and a rational number cc such that P(x)=c(A(x)2+B(x)2)P(x)=c(A(x)^2+B(x)^2).
b) If P(x)P(x) is a monic polynomial with integer coefficients, Prove that there exists two polynomials A(x)A(x) and B(x)B(x) with integer coefficients such that P(x)P(x) can be written in the form of A(x)2+B(x)2A(x)^2+B(x)^2.
Proposed by Mohammad Gharakhani
algebrapolynomialRing Theorymodular arithmeticnumber theory proposednumber theory
Incircle and perpendicular

Source: Iran 3rd round 2012-Geometry exam-P4

9/20/2012
The incircle of triangle ABCABC for which AB≠ACAB\neq AC, is tangent to sides BC,CABC,CA and ABAB in points D,ED,E and FF respectively. Perpendicular from DD to EFEF intersects side ABAB at XX, and the second intersection point of circumcircles of triangles AEFAEF and ABCABC is TT. Prove that TX⊥TFTX\perp TF.
Proposed By Pedram Safaei
geometrycircumcircleMITcollegeangle bisectorgeometry proposedIran
Coloring subsets of a set

Source: Iran 3rd round 2012-Combinatorics exam-P4

9/20/2012
a) Prove that for all m,n∈Nm,n\in \mathbb N there exists a natural number aa such that if we color every 33-element subset of the set A={1,2,3,...,a}\mathcal A=\{1,2,3,...,a\} using 22 colors red and green, there exists an mm-element subset of A\mathcal A such that all 33-element subsets of it are red or there exists an nn-element subset of A\mathcal A such that all 33-element subsets of it are green.
b) Prove that for all m,n∈Nm,n\in \mathbb N there exists a natural number aa such that if we color every kk-element subset (k>3k>3) of the set A={1,2,3,...,a}\mathcal A=\{1,2,3,...,a\} using 22 colors red and green, there exists an mm-element subset of A\mathcal A such that all kk-element subsets of it are red or there exists an nn-element subset of A\mathcal A such that all kk-element subsets of it are green.
combinatorics proposedcombinatorics
Interval for roots

Source: Iran 3rd round 2012-Algebra exam-P4

9/20/2012
Suppose f(z)=zn+a1zn−1+...+anf(z)=z^n+a_1z^{n-1}+...+a_n for which a1,a2,...,an∈Ca_1,a_2,...,a_n\in \mathbb C. Prove that the following polynomial has only one positive real root like α\alpha xn+ℜ(a1)xn−1−∣a2∣xn−2−...−∣an∣x^n+\Re(a_1)x^{n-1}-|a_2|x^{n-2}-...-|a_n|
and the following polynomial has only one positive real root like β\beta xn−ℜ(a1)xn−1−∣a2∣xn−2−...−∣an∣.x^n-\Re(a_1)x^{n-1}-|a_2|x^{n-2}-...-|a_n|. And roots of the polynomial f(z)f(z) satisfy −β≤ℜ(z)≤α-\beta \le \Re(z) \le \alpha.
algebrapolynomialalgebra proposed
Bags of coins, one different

Source: Iran 3rd round 2012-Final exam-P4

9/20/2012
We have nn bags each having 100100 coins. All of the bags have 1010 gram coins except one of them which has 99 gram coins. We have a balance which can show weights of things that have weight of at most 11 kilogram. At least how many times shall we use the balance in order to find the different bag?
Proposed By Hamidreza Ziarati
ceiling functioncombinatorics proposedcombinatorics