## Solutions for advanced problems "A" in November, 2003 |

In this page only the sketch of the solutions are published; in some cases only the final results. To achieve the maximum score in the competition more detailed solutions needed.

**A. 329.** A circle *k*_{1} of the plane lies in the interior of a circle *k*_{2}. Point *P* lies inside *k*_{1}, and point *Q* lies outside *k*_{2} in the plane. Given the circles and the points, draw an arbitrary line *e* through *P* that does not pass through *Q*. Let *e* intersect *k*_{1} at *A* and *B*. Let the circumscribed circle of *ABQ* intersect *k*_{2} at *C* and *D*. Prove that all line segments *CD* obtained in this way are concurrent.

**Solution.** Denote the intersection between line *PQ* and circles *k*_{1} and *k*_{2} and the crcumcircle *k* of *ABC* by *E*, *F*, *G*, *H* and *R* (see Figure 1). Points *Q*, *G*, *E*, *P*, *F*, *H* are indepentent of the choice of line *e* and they have always this order.

Figure 1

From the power of *P* to circles *k*_{1} and *k*_{3}, *PE*^{.}*PF*=*PA*^{.}*PB* = *PQ*^{.}*PR*. Therefore, the signed distance \(\displaystyle PR=\frac{PE\cdot PF}{PQ}\) is constant and point *R* is fixed. *R* is an interior point of *PF*, since \(\displaystyle 0<\frac{PR}{PF}=\frac{PE}{PQ}<1\). This implies that *R* lies inside *k*_{1} and *k*_{2}.

Point *P* lies between *A* and *B* because it is an interior point of *k*_{1}; hence, line *PQ* separates *A* and *B*. Consider the three arcs of *k*_{3} bounded by points *A*, *B* and *Q*. Points *A* and *B* lie inside *k*_{2}, *Q* is outside. Therefore, *k*_{2} intersects arcs *QA* and *QB*; *C* and *D* lie in these arcs. Hence,points *Q*, *D*, *B*, *R*, *A* and *C* have always this order on circle *k*_{3} and the line segments *CD* and *PR* intersect each other. Denote their intersection point by *S*.

From the power of *S* to the circles, *SG*^{.}*SH*=*SC*^{.}*SD*=*SQ*^{.}*SR*. The power is negative, thus *S* lies inside line segments *QR* and *GH* and thus *GR*. Epressing the signed distances *SH* and *SR* with *SG*,

*SG*^{.}*SH*=*SQ*^{.}*SR*

*SG*^{.}(*SG*-*HG*)=(*SG*+*GQ*)^{.}(*SG*-*RG*)

\(\displaystyle SG=\frac{RG\cdot GQ}{HG+GQ-RG}=\frac{RG\cdot CQ}{HR+GQ}.\)

The signed distance *SG* does not depend on the choice of line *e*, *S* is the common point of all lin segments *CD*.

**A. 330.** The sequence of Lucas numbers is defined by the following recurrence: *L*_{0}=2, *L*_{1}=1, *L*_{n+1}=*L*_{n}+*L*_{n-1}. Show that *L*_{(p+1)/2}^{p}-1 is divisible by *L*_{p} for all primes *p*>3.

**Solution.** From the properties of *p* we only need that *p* is odd and not divisible by 3.

Let \(\displaystyle \alpha={1+\sqrt5\over2}\) and \(\displaystyle \beta={1-\sqrt5\over2}\); then

(1) | L_{n}=\(\displaystyle \alpha\)^{n}+\(\displaystyle \beta\)^{n}. |

The definition and formula (1) can be extended to negative indices as well.

It is easy to check that *L*_{m}*L*_{n}=*L*_{m+n}+(-1)^{m}*L*_{n-m} of all itegers *m*,*n*. This implies

*L*_{n+2m}\(\displaystyle \equiv\)(-1)^{m+1}*L*_{n} (mod *L*_{m});

specially,

(2) | L_{n+2p}\(\displaystyle \equiv\)L_{n} (mod L_{p}). |

Let *k*=(*p*+1)/2. Then

(3) | \(\displaystyle L_k^p=(\alpha^k+\beta^k)^p= \sum_{m=0}^p{p\choose m}\alpha^{(p-m)k}\beta^{mk}=\) |

\(\displaystyle =\sum_{m=0}^{k-1}(-1)^{mk}{p\choose m}\alpha^{(p-2m)k} +\sum_{m=k}^p(-1)^{(p-m)k}{p\choose m}\beta^{(2m-p)k}=\)

\(\displaystyle =\sum_{m=0}^{k-1}(-1)^{mk}{p\choose m}L_{(p-2m)k} =\sum_{m=0}^{k-1}(-1)^{mk}{p\choose m}L_{(k-m)p-m}.\)

If *m* and *k* have opposite parities then

(-1)^{mk}*L*_{(k-m)p-m} = *L*_{(k-m)p-m} \(\displaystyle \equiv\)*L*_{p-m} (mod *L*_{p}).

Otherwise, if *k* and *m* have the same parity then

(-1)^{mk}*L*_{(k-m)p-m} \(\displaystyle \equiv\)(-1)^{m}*L*_{-m} = *L*_{m} (mod *L*_{p}).

Substituting these into (3),

\(\displaystyle 2L_k^p\equiv2\sum_{\begin{matrix}0\le m\le p\cr m\equiv k~(2)\cr\end{matrix}} {p\choose m}L_m= 2\sum_{\begin{matrix}0\le m\le p\cr m\equiv k~(2)\cr\end{matrix}} {p\choose m}(\alpha^m+\beta^m)=\)

=((\(\displaystyle \alpha\)+1)^{p}+(-1)^{k}(\(\displaystyle \alpha\)-1)^{p})+((\(\displaystyle \beta\)+1)^{p}+(-1)^{k}(\(\displaystyle \beta\)-1)^{p})=

=(\(\displaystyle \alpha\)^{2p}+\(\displaystyle \beta\)^{2p})+(-1)^{k}(\(\displaystyle \alpha\)^{-p}+\(\displaystyle \beta\)^{-p})=*L*_{2p}+(-1)^{k+p}*L*_{p}\(\displaystyle \equiv\)*L*_{0}=2 (mod *L*_{p}).

Since *L*_{p} is odd (*L*_{n} is even if and only if 3|*n*), this implies *L*_{k}^{p}\(\displaystyle \equiv\)1 (mod *L*_{p}).

**A. 331.** According to the records of the Bureau of Statistics in Quasiland, any pair of citizens who know each other have exactly one common acquaintance, while any two people who do not know each other have at least ten common acquaintances. Is it possible that the records are accurate?

**Solution.** We show an eample for such a graph.

Let *S* be a set of 3*n* elements where *n*\(\displaystyle \ge\)9. Let the vertices of the graph be the *n*-element subset. Let two vertices be connected if the corresponding subsets are disjoint. This system has the required properties.