MathDB

1

Part of 2011 Iran MO (3rd Round)

Problems(6)

a vertex in all the longest paths

Source: Iran 3rd round 2011-combinatorics exam-p1

9/4/2011
prove that if graph GG is a tree, then there is a vertex that is common between all of the longest paths.
proposed by Sina Rezayi
combinatorics proposedcombinatorics
dividing a necklace between two rubbers

Source: Iran 3rd round 2011-topology exam-p1

9/3/2011
(a) We say that a hyperplane HH that is given with this equation H={(x1,…,xn)∈Rn∣a1x1+⋯+anxn=b}H=\{(x_1,\dots,x_n)\in \mathbb R^n \mid a_1x_1+ \dots +a_nx_n=b\} (a=(a1,…,an)∈Rna=(a_1,\dots,a_n)\in \mathbb R^n and b∈Rb\in \mathbb R constant) bisects the finite set A⊆RnA\subseteq \mathbb R^n if each of the two halfspaces H+={(x1,…,xn)∈Rn∣a1x1+⋯+anxn>b}H^+=\{(x_1,\dots,x_n)\in \mathbb R^n \mid a_1x_1+ \dots +a_nx_n>b\} and H−={(x1,…,xn)∈Rn∣a1x1+⋯+anxn<b}H^-=\{(x_1,\dots,x_n)\in \mathbb R^n \mid a_1x_1+ \dots +a_nx_n<b\} have at most ⌊∣A∣2⌋\lfloor \tfrac{|A|}{2}\rfloor points of AA.
Suppose that A1,…,AnA_1,\dots,A_n are finite subsets of Rn\mathbb R^n. Prove that there exists a hyperplane HH in Rn\mathbb R^n that bisects all of them at the same time.
(b) Suppose that the points in B=A1∪⋯∪AnB=A_1\cup \dots \cup A_n are in general position. Prove that there exists a hyperplane HH such that H+∩AiH^+\cap A_i and H−∩AiH^-\cap A_i contain exactly ⌊∣Ai∣2⌋\lfloor \tfrac{|A_i|}{2}\rfloor points of AiA_i.
(c) With the help of part (b), show that the following theorem is true: Two robbers want to divide an open necklace that has dd different kinds of stones, where the number of stones of each kind is even, such that each of the robbers receive the same number of stones of each kind. Show that the two robbers can accomplish this by cutting the necklace in at most dd places.
floor functiontopology
set closed under adding

Source: Iran 3rd round 2011-number theory exam-p1

9/5/2011
Suppose that S⊆ZS\subseteq \mathbb Z has the following property: if a,b∈Sa,b\in S, then a+b∈Sa+b\in S. Further, we know that SS has at least one negative element and one positive element. Is the following statement true? There exists an integer dd such that for every x∈Zx\in \mathbb Z, x∈Sx\in S if and only if d∣xd|x. proposed by Mahyar Sefidgaran
algorithmnumber theory proposednumber theory
4 circles and concurrent lines

Source: Iran 3rd round 2011-geometry exam-p1

9/6/2011
We have 44 circles in plane such that any two of them are tangent to each other. we connect the tangency point of two circles to the tangency point of two other circles. Prove that these three lines are concurrent.
proposed by Masoud Nourbakhsh
geometrycircumcirclepower of a pointradical axisgeometry proposed
similar to chebyshev polynomial

Source: Iran 3rd round 2011-algebra exam-p1

9/7/2011
We define the recursive polynomial Tn(x)T_n(x) as follows: T0(x)=1T_0(x)=1 T1(x)=xT_1(x)=x Tn+1(x)=2xTn(x)+Tn−1(x)T_{n+1}(x)=2xT_n(x)+T_{n-1}(x) ∀n∈N\forall n \in \mathbb N.
a) find T2(x),T3(x),T4(x)T_2(x),T_3(x),T_4(x) and T5(x)T_5(x).
b) find all the roots of the polynomial Tn(x)T_n(x) ∀n∈N\forall n \in \mathbb N.
Proposed by Morteza Saghafian
inequalitiesalgebrapolynomialalgebra proposed
regular dodecahedron

Source: Iran 3rd round 2011-final exam-p1

9/11/2011
A regular dodecahedron is a convex polyhedra that its faces are regular pentagons. The regular dodecahedron has twenty vertices and there are three edges connected to each vertex. Suppose that we have marked ten vertices of the regular dodecahedron.
a) prove that we can rotate the dodecahedron in such a way that at most four marked vertices go to a place that there was a marked vertex before.
b) prove that the number four in previous part can't be replaced with three.
proposed by Kasra Alishahi
geometry3D geometrydodecahedronrotationgeometric transformationgroup theorygeometry proposed