MathDB

1

Part of 2012 Iran MO (3rd Round)

Problems(7)

Points and lines in plane

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

7/27/2012
Prove that the number of incidences of nn distinct points on nn distinct lines in plane is O(n43)\mathcal O (n^{\frac{4}{3}}). Find a configuration for which Ω(n43)\Omega (n^{\frac{4}{3}}) incidences happens.
analytic geometrygraphing linesslopecombinatorics proposedcombinatorics
Coloring points of a square, finding a monochromatic hexagon

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

9/15/2012
Prove that for each coloring of the points inside or on the boundary of a square with 13911391 colors, there exists a monochromatic regular hexagon.
combinatorics proposedcombinatorics
Polynomial having infinitely many prime divisors

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

9/19/2012
P(x)P(x) is a nonzero polynomial with integer coefficients. Prove that there exists infinitely many prime numbers qq such that for some natural number nn, q∣2n+P(n)q|2^n+P(n).
Proposed by Mohammad Gharakhani
algebrapolynomialmodular arithmeticinequalitiesnumber theoryprime numbersnumber theory proposed
A fixed ratio

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

9/20/2012
Fixed points BB and CC are on a fixed circle ω\omega and point AA varies on this circle. We call the midpoint of arc BCBC (not containing AA) DD and the orthocenter of the triangle ABCABC, HH. Line DHDH intersects circle ω\omega again in KK. Tangent in AA to circumcircle of triangle AKHAKH intersects line DHDH and circle ω\omega again in LL and MM respectively. Prove that the value of ALAM\frac{AL}{AM} is constant.
Proposed by Mehdi E'tesami Fard
ratiogeometrycircumcircletrigonometryparallelogramgeometry proposed
Rainbow vertices

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

9/20/2012
We've colored edges of KnK_n with n−1n-1 colors. We call a vertex rainbow if it's connected to all of the colors. At most how many rainbows can exist?
Proposed by Morteza Saghafian
algorithmcombinatorics proposedcombinatorics
Polynomial having at most n real roots

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

9/20/2012
Suppose 0<m1<...<mn0<m_1<...<m_n and mi≡i(mod  2)m_i \equiv i (\mod 2). Prove that the following polynomial has at most nn real roots. (∀1≤i≤n:ai∈R\forall 1\le i \le n: a_i \in \mathbb R). a0+a1xm1+a2xm2+...+anxmn.a_0+a_1x^{m_1}+a_2x^{m_2}+...+a_nx^{m_n}.
algebrapolynomialinductionfunctionmodular arithmeticalgebra proposed
Number of acyclic orientations

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

9/20/2012
Let GG be a simple undirected graph with vertices v1,v2,...,vnv_1,v_2,...,v_n. We denote the number of acyclic orientations of GG with f(G)f(G).
a) Prove that f(G)≤f(G−v1)+f(G−v2)+...+f(G−vn)f(G)\le f(G-v_1)+f(G-v_2)+...+f(G-v_n).
b) Let ee be an edge of the graph GG. Denote by G′G' the graph obtained by omiting ee and making it's two endpoints as one vertex. Prove that f(G)=f(G−e)+f(G′)f(G)=f(G-e)+f(G').
c) Prove that for each α>1\alpha >1, there exists a graph GG and an edge ee of it such that
f(G)f(G−e)<α\frac{f(G)}{f(G-e)}<\alpha.
Proposed by Morteza Saghafian
combinatorics proposedcombinatorics