MathDB

3

Part of 2006 IMO Shortlist

Problems(4)

"pseudo-Fibonnaci" sequence

Source: IMO Shortlist 2006, Algebra 3

6/28/2007
The sequence c0,c1,...,cn,...c_{0}, c_{1}, . . . , c_{n}, . . . is defined by c0=1,c1=0c_{0}= 1, c_{1}= 0, and cn+2=cn+1+cnc_{n+2}= c_{n+1}+c_{n} for n≥0n \geq 0. Consider the set SS of ordered pairs (x,y)(x, y) for which there is a finite set JJ of positive integers such that x=∑j∈Jcjx=\textstyle\sum_{j \in J}{c_{j}}, y=∑j∈Jcj−1y=\textstyle\sum_{j \in J}{c_{j-1}}. Prove that there exist real numbers α\alpha, β\beta, and MM with the following property: An ordered pair of nonnegative integers (x,y)(x, y) satisfies the inequality m<αx+βy<Mm < \alpha x+\beta y < M if and only if (x,y)∈S(x, y) \in S.
Remark: A sum over the elements of the empty set is assumed to be 00.
inequalitiesalgebraSequenceIMO Shortlist
Did you talk to Noga Alon?

Source: IMO Shortlist 2006, Combinatorics 3, AIMO 2007, TST 6, P2

6/28/2007
Let S S be a finite set of points in the plane such that no three of them are on a line. For each convex polygon P P whose vertices are in S S, let a(P) a(P) be the number of vertices of P P, and let b(P) b(P) be the number of points of S S which are outside P P. A line segment, a point, and the empty set are considered as convex polygons of 2 2, 1 1, and 0 0 vertices respectively. Prove that for every real number x x \sum_{P}{x^{a(P)}(1 \minus{} x)^{b(P)}} \equal{} 1, where the sum is taken over all convex polygons with vertices in S S.
Alternative formulation:
Let M M be a finite point set in the plane and no three points are collinear. A subset A A of M M will be called round if its elements is the set of vertices of a convex A \minus{}gon V(A). V(A). For each round subset let r(A) r(A) be the number of points from M M which are exterior from the convex A \minus{}gon V(A). V(A). Subsets with 0,1 0,1 and 2 elements are always round, its corresponding polygons are the empty set, a point or a segment, respectively (for which all other points that are not vertices of the polygon are exterior). For each round subset A A of M M construct the polynomial P_A(x) \equal{} x^{|A|}(1 \minus{} x)^{r(A)}. Show that the sum of polynomials for all round subsets is exactly the polynomial P(x) \equal{} 1.
Proposed by Federico Ardila, Colombia
algebrapolynomialprobabilityexpected valueProbabilistic MethodIMO Shortlist
Italian WinterCamps test07 Problem4

Source: ISL 2006, G3, VAIMO 2007/5

1/29/2007
Let ABCDE ABCDE be a convex pentagon such that \angle BAC \equal{} \angle CAD \equal{} \angle DAE\qquad \text{and}\qquad \angle ABC \equal{} \angle ACD \equal{} \angle ADE. The diagonals BDBD and CECE meet at PP. Prove that the line APAP bisects the side CDCD.
Proposed by Zuming Feng, USA
geometrycircumcirclepentagonIMO Shortlist
Italian WinterCamps test07 Problem2

Source: IMO Shortlist 2006, N3, AIMO 2007, TST 3, P1

1/29/2007
We define a sequence (a1,a2,a3,…) \left(a_{1},a_{2},a_{3},\ldots \right) by a_{n} \equal{} \frac {1}{n}\left(\left\lfloor\frac {n}{1}\right\rfloor \plus{} \left\lfloor\frac {n}{2}\right\rfloor \plus{} \cdots \plus{} \left\lfloor\frac {n}{n}\right\rfloor\right), where ⌊x⌋\lfloor x\rfloor denotes the integer part of xx.
a) Prove that an+1>ana_{n+1}>a_n infinitely often. b) Prove that an+1<ana_{n+1}<a_n infinitely often.
Proposed by Johan Meyer, South Africa
calculusfloor functionnumber theorySequenceSummationIMO Shortlist