
Solutions for advanced problems "A" in October, 2001

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. 272. The benches of the Great Hall of the
Parliament of Neverenough are arranged in a rectangle of 10 rows of 10
seats each. All the 100 MPs have different salaries. Each of them asks
all his neighbours (sitting next to, in front of, or behind him,
i.e. 4 members at most) how much they earn. They feel a lot of envy
towards each other: an MP is content with his salary only if he has at
most one neighbour who earns more than himself. What is the maximum
possible number of MPs who are satisfied with their salaries?
Adapted from Kvant
Solution. We shall show that at most 72 MP's are content
with their salaries. Let us represent the members of parliament with
a square grid of 10x10 points, and label each point with the salary of
the corresponding MP. Let us draw arrows between neighbouring points
such that the arrow is directed from the smaller to the larger number:
(Satisfied MP's are marked in green, and dissatisfied ones in red.)
Let a be the number of satisfied MP's sitting in the
corners, b the number of those sitting at the sides of the
square, and c the number of those sitting inside.
The number of arrows is 180. There is at most one arrow
originating at any satisfied MP, and there will be at least one point
where no arrow originates, the MP with the largest salary (obviously
satisfied). Hence the number of arrows originating at satisfied MP's
is at most a+b+c1.
There are at most (4a)^{.}2 arrows from the
4a dissatisfied MP's in the corners, at most
(32b)^{.}3 from the 32b dissatisfied MP's
along the sides, and at most (32b)^{.}3 from those
(64c)^{.}4 sitting inside. The total number of arrows
is thus
180\(\displaystyle le\)(a+b+c1)+(4a)^{.}2+(32b)^{.}3+(64c)^{.}4,
that is,
a+2b+3c\(\displaystyle le\)179.
The one with the lowest salary out of the 36 MP's around the
circumference is necessarily dissatisfied, thus a+b35. It is also
obvious that a\(\displaystyle le\)4. By adding the inequalities, we have
3(a+b+c)=(a+2b+3c)+(a+b)+a179+35+4=218,
that is, a+b+c\(\displaystyle le\)72. Hence, the number of satisfied MP's
cannot be greater than 72.
The diagram shows the case when there are exactly 72 MP's who are
content with their salaries.
A. 273. The inscribed circle of triangle
ABC touches the sides AB, BC, CA at the
points C_{1}, A_{1},
B_{1} respectively. Given vertex A, line
A_{1}B_{1}, and the line joining the
midpoint of segment B_{1}C_{1} to vertex
B, construct the triangle ABC with ruler and compasses.
Proposed by: T. Kálmán, Budapest
Solution. Let the angles of the triangle be , and , let the
centre of the inscribed circle be O, and let F be the
midpoint of the segment B_{1}C_{1}. Let
M denote the intersection of the lines BF and
A_{1}B_{1}, and let N denote the
intersection of line A_{1}B_{1} with the
angle bisector AF. First we shall prove that point M
lies on the exterior angle bisector from A, or what is
equivalent, that the segments AM and
B_{1}C_{1} are parallel.
By calculating the angles of the triangles
A_{1}B_{1}C and
AB_{1}N, we have that ANB_{1}=/2. As this is
equal to angle OBA_{1}, the quadrilateral
OBNA_{1} is cyclic, and BNO=BA_{1}O=90^{o}. As this is also equal to the angle
C_{1}FA, the segments BN and
B_{1}C_{1} are parallel.
It follows from the theorem on parallel transversals, that
AF:AN=C_{1}F:BN=FB_{1}:BN=MF:MB,
and hence AM és BN are also parallel.
Using this information, the steps of the construction are as
follows:
1. Construct point M, the intersection of lines AM és
BN.
2. Erect a perpendicular at point A to the line AM.
This will be the interior angle bisector that cuts the given lines
A_{1}B_{1} and BF at the points
N and F, respectively.
3. Erect a perpendicular at point N to the line AN.
This will intersect the line BF at B.
4. B_{1} is obtained as the intersection of line
A_{1}B_{1} with the perpendicular drawn
to AF at point F.
5. Draw a perpendicular to line AB_{1} at the point
B_{1}. This will intersect line AF at O.
6. By reflecting the line AB in the angle bisector
BO, obtain the line of side BC. Finally, get the vertex
C as the intersection of the line of side BC with the
line AB_{1}.
A. 274. Let a, b, c be
positive integers for which
ac=b^{2}+b+1. Prove that the equation
ax^{2}(2b+1)xy+cy^{2}=1
has an integer solution.
Polish competition problem
Solution 1. The statement of the problem is proved by
induction on b. It is allowed that b=0. In that case,
a=c=1, and x=y=1 is a solution.
Now suppose that b is positive, and the statement is true
for all smaller values of b. The numbers a and c
cannot be both greater than b, as when a,cb+1, ac(b+1)^{2}>b^{2}+b+1. As
the statement does not change by the interchanging of a and
c, we can assume, without restriction, that ab.
Let A=a, B=ba,
C=a2b+c1. These are integers, and it is
true for them that
B^{2}+B+1=(ba)^{2}+(ba)+1=
=(b^{2}+b+1)2ab+a^{2}a=
=ac2ab+a^{2}a=a(a2b+c1)=AC,
and furthermore, A>0, 0\(\displaystyle le\)B<b, and
C=(B^{2}+B+1)/A>0. Hence the
induction step can be applied to the numbers A, B,
C, which means that there exist the integers X and
Y, such that
AX^{2}(2B+1)XY+CY^{2}=1.
By substituting the definitions of A, B and
C, we get
1=AX^{2}(2B+1)XY+CY^{2}=
=aX^{2}(2b2a+1)XY+(a2b+c1)Y^{2}=
=a(X+Y)^{2}(2b+1)(X+Y)Y+cY^{2}.
Therefore, the number pair x=XY,
y=Y is a solution of the equation.
Solution 2. Consider the set of points in the Cartesian
coordinate plane for which
ax^{2}(2b+1)xy+cy^{2}<2.
It is easy to show by some calculation that they form an ellipse with
an area of \(\displaystyle {4\pi\over\sqrt3}\) units.
The elliptical disc is symmetric about the origin, it is convex,
and its area is greater than 4 units. Thus, according to Minkowski's
theorem there is a mesh point other than the origin in its interior.
At that mesh point, the value of
ax^{2}(2b+1)xy+cy^{2} is
between 0 and 2, therefore it is 1.
Remark. In solution 1, we are actually using the
transformation (x,y)\(\displaystyle mapsto\)(xy,y) to map the
elliptical disc onto another ellipse of equal area with smaller
coefficients. By repeating the transformation several times, we will
always obtain the ellipse
x^{2}xy+y^{2}<2. This
ellipse contains six mesh points different from the origin: the points
(\(\displaystyle pm\)1,0), (0,1) and (1,1). Therefore, the
equation always has six number pairs for solution.
