The ,,Math Stars Contest 89

THE ,,MATH STARS CONTEST

6-7 December 2008
1)
presented by Dan Schwarz

The contest was organized by the International Computer High School

from Bucharest, on the 6th and 7th of December 2008 and consisted of 6
IMO-style questions.
1. Prove that, for every positive integer m, the equation
n    
3
= n2 + n +1
m
has at least a positive integer solution nm .
C. Lupu & D. Schwarz
2. The 2N vertices of the N -dimensional hypercube {0, 1}N are labeled
with numbers from 0 to 2N 1 such that x = (x1 , x2 , . . . , xN ) gets the label
N

v(x) = xk 2k1 .
k=1

Find all n, 2 n 2N ,
so that the vertices from V = {v | 0 v n1}
can be visited in a circuit using only edges of the hypercube which connect
vertices of V (each vertex is visited exactly once).
E. Bazavan & C. Talau
3. Consider a convex quadrilateral and the incircles of the two triangles
obtained drawing one of its diagonals. Prove that the tangency points of these
two circles to the diagonal are symmetrical with respect to the midpoint of
the diagonal if and only if the centers of the circles and the meeting point of
the diagonals are collinear.
D. Schwarz 2)
4. Find the maximum number of consecutive integer values which can
be assumed by a polynomial P Z[X] of degree n > 1, for integer values of
the variable.
B. Berceanu
m
5. Suppose that 23 > , where m, n are positive integers.
n
m 3
i) Show that 23 > + .
n mn
m 4
ii) Show that 23 < + innitely many times and nd at least
n mn
three such cases. D. Schwarz
1) Teacher, International Computer High School of Bucharest.
2) See IMO 2008 Problem 6 in GM-B nr. 7-8 2008.
90 Examene si Concursuri

6. Consider the innite array consisting of the rst quadrant of the

plane divided into unit squares, each square containing a real number. The
array will be called kbalanced (where k > 1 is an integer) if not all its
numbers are equal and the sum of the elements of each of its k k subsquares
is the same vk . An array which is both pbalanced and qbalanced will be
called (p, q)balanced. If p, q are relatively prime, the array will be called
coprime.
We will call (M N )seed of a (p, q)balanced array a M N rectangle,
having its left corner in the origin and which, extended periodically in both
dimensions of the plane, generates the array.
(i) Prove that, in a (p, q)balanced array, q 2 vp = p2 vq .
(ii) Prove that a coprime (p, q)balanced array contains at least three
dierent numbers. Show that this is not necessarily true if the array is not
coprime ((p, q) > 1).
(iii) Prove that every coprime (p, q)balanced array has a seed.
(iv) Show that for every p, q there exists a (p, q)balanced array con-
taining only three dierent numbers.
(v) Prove that a kbalanced array and a (p, q)balanced array which
is not coprime (p, q > 1) do not necessarily have a seed.
(vi) Find the minimum T for which there exists a (T T )seed of a
given coprime (p, q)balanced array, when p, q are given primes.
(vii) Show that, for every relatively prime p, q, there exists a coprime
(p, q)balanced array which has a square (T T )seed and does not have
smaller (M N )seeds (M T , N T and M N < T 2 ).
D. Schwarz

Solutions
3
1. The sequence an =  n2  +  n + 1 is made of positive integers
n
and non-decreasing. For n (2m)6 we clearly have an < , since
m

3  
an n2 + n + 1 1 1 1 1 1 1 1 1
2
+ 3
+ 6
+ + < ,
n n 4m 8m 64m m 4 8 64 m
n
so take k the largest n for which an (clearly this occurs for n = 1,
m
k
so the set is not empty). Assume ak > ; then mak+1 mak > k, so
m
k+1
mak+1 k + 1, hence ak+1 , in contradiction with the maximality of
m
k
k. Therefore we must have ak = and we may take
m
n!
nm = max n N | an .
m
 The ,,Math Stars Contest 91

2. Consider the Hamming distance between N -vectors, given by the

number of diering coordinates between the two vectors. In our case this is
given by
 N
d(x, y) = |xk yk |,
k=1
and since all edges are hypercube edges, distances between adjacent vertices
are all 1. Assume a Hamiltonian circuit (x0 , x1 , . . . , xn1 , xn = x0 ) exists.
Notice that modulo 2 we have
n1
 n1
 N N n1
 
d(xv , xv+1 ) = |xv,k xv+1,k | (xv,k xv+1,k ) = 0,
v=0 v=0 k=1 k=1 v=0
and since
n1
 n1

d(xv , xv+1 ) = 1 = n,
v=0 v=0
in order for a Hamiltonian circuit to exist, n must be even.
To show that for any even n there exists a Hamiltonian circuit, we
start by building one for n = 2M , 1 M N . Consider the mapping
(a1 , a2 , . . . , am ) = am , . . . , a2 , a1 which reverses the order of symbols in a
sequence, and the translation t which adds t to each term of a numeric
sequence. Build now the iterative sequences W0 = 0, Wk+1 = Wk , (2k (Wk )
for k 0. For instance, W4 = 0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8.
It is obvious that WM , 0 is a Hamiltonian circuit. Moreover, notice that
any pair {2k, 2k + 1}, with 0 k 2M 1 1, appears as adjacent terms in
the above circuit. Take M = log2 n. Since n 2M is even, it adds pairs of
vertices to be considered in the circuit. Now, any pair {2M +2k, 2M +2k +1},
with 0 k 2M 1 1, may be injected within the above sequence WM , 0,
inside the {2k, 2k + 1} pair, such that the even, respectively odd, terms are
adjacent, and so that the new sequence still observes the requirement that
adjacent terms are connected by edges in the hypercube.
3. Denote by ABCD the quadrilateral, with [AC] being the diagonal
in question, and by P , respectively Q, the tangency points with AC of the
incircle B of the triangle ABC, respectively of the incircle D of the triangle
ADC.
If BC and AD are parallel, and BA and CD are also parallel, then
ABCD is a parallelogram, with central symmetry, and all is clear. We thus
may assume (AD and (BC are crossing, beyond D, respectively C (otherwise
we either swap the pair of labels B and D, or the pair A and C, or both pairs
while these moves invariate both stated conditions). Consider the circle
tangent to (AD and (CD beyond D, and (BC beyond C. Let us also denote
by H2 1 (X) the homothety of center X which transforms a circle 1 into
another circle 2 , bearing the sign of the homothety ratio at superscript.
92 Examene si Concursuri

For the direct, we are told that |AP | = |CQ|. We have

1 1
|AP | = (|AC| + |AB| |BC|) and |CQ| = (|AC| + |CD| |AD|),
2 2
so |AP | = |CQ| is equivalent to |AB| + |AD| = |CB| + |CD|. The other
tangent from B to than BC meets AD at A
. Then a variant to Pithots
Theorem yields |A
B| + |A
D| = |CB| + |CD|, so |AB| = |A
B| |AA
|, hence
the triangle ABA
is degenerated, and so A
must coincide with A (in fact a
proof of the converse to Pithot). This means that is also tangent to (BA
beyond A.
Then, with R the center of the negative ratio homothety between B
and D (i.e. the crossing point of their internal common tangents), we have
H+B (B) = HB D (R) HD (D),
so D, R and B are collinear, hence R BD. But AC is one of the internal
common tangents of B and D , so R AC. Finally, R = AC BD is on
the line of the incenters.
For the reciprocal, we are told that R = AC BD. Then, with B
the
center of the positive ratio homothety between B and (i.e. the crossing
point of their external common tangents), we have
H+B (B
) = HB D (R) HD (D),
so D, R and B
are collinear, hence B
RD = BD. But BC is one of the
external common tangents of B and , so B
BC, hence B
must coincide
with B. This means that is also tangent to (BA beyond A.
Finally, applying the variant to Pithots Theorem, we get |AB|+|AD| =
|CB| + |CD|, equivalent to |AP | = |CQ|.
Remark. The same result is valid for the excircles (with respect to
AC) of the triangles ABC and ADC, with analogous proof, since a known
fact yields that their tangency points with AC are symmetrical with respect
to the midpoint of [AC] with those of the incircles, which are given so.
4. Let ak , 1 k m, ak+1 = ak + 1 for 1 k m 1, be m
consecutive integer values taken for P (xk ) = ak , with xk Z. It is easy to
prove that b a | P (b) P (a) for a, b Z.
Then xk+1 xk | P (xk+1 ) P (xk ) = ak+1 ak = 1, so |xk+1 xk | = 1
for 1 k m 1, therefore (xk )1km is an arithmetic progression of ratio
r = 1 (since the values of xk need be distinct).
But the polynomial Q(x) = r(x x1 ) + a1 also satises Q(xk ) = ak
for 1 k m, so m n, otherwise P Q vanishes in more than deg P
arguments, therefore P Q, absurd, since n > 1.
On the other hand, the polynomials
n1
  
P (x) = x (a + k) x + b
k=0
 The ,,Math Stars Contest 93

with , a, b Z, take values P (a + k) = (b a) k for 0 k n 1, which

are consecutive, therefore the maximal value n is reached (and in fact this is
the general form of polynomials reaching the maximal possible value).
m
5. From 23 > follows 23n2 m2 + 1. But the quadratic residues
n
modulo 23 are 0, 1, 25 2, 49 3, 4, 121 6, 100 8, 9, 81 11, 36
10, 16 7 and 64 5, so the tightest inequality available would seem to
be 23n2 m2 +5, only that modulo 5 we have 23 3, and 3 is not a quadratic
residue modulo 5. Therefore the tightest inequality is 23n2 m2 + 7, for
which there exists the principal solution 23 12 = 42 + 7.
i) Hence 23n2 m2 + 7, or
 m 2  
7 m 3 2 1 9
23 + 2 = + + 2 2 2,
n n n mn n m n
1 9 m2 9
while 2 2 2 = > 0, as long as m > 3.
n m n m2 n 2  
m 3 2 16
Now, for m = 1 or 3, + = 2 16 < 23; while for m = 2,
n mn n
 2
m 3 49 49
+ = 2 < 23.
n mn 4n 4
m 3
Therefore in all cases 23 > + .
n mn
2 2
ii) For 23n = m + 7 we have
 m 2    
7 m 4 2 1 16 m 4 2
23 = + 2 = + 2 2 2 < + ,
n n n mn n m n n mn
m 4
hence 23 < + , with the example (m, n) = (4, 1) provided by the
n mn
principal solution above.
It remains to show that we innitely often may have 23n2 = m2 + 7 (1),
a Pell equation. Since the classical Pell equation 23y 2 = x2 1 has the
principal solution (24, 5), the solutions for (1) are given by

m + n 23 = (4 23)(24 + 5 23)s , s N,
enough for exhibiting the required examples.
6. Lemma. If a sequence (xn )n0 is both p-periodic and q-periodic,
with p, q relatively prime, then it must be constant.
Proof. There exist positive integers u, v such that 1 = up vq. Then,
for all n 0, xn = xn+up = x(n+up)vq = xn+(upvq) = xn+1 , hence (xn )n0
is of period 1, therefore the sequence is constant.
As an extension, if d = (p, q) > 1, the result is that the sequence
must be d-periodic. This follows from the proof above, by grouping together
,,molecules of d consecutive atom terms. Now for p = dp
and q = dq
we
have (p
, q
) = 1 and we apply the Lemma. This means the molecules are
equal, i.e. the sequence is d-periodic.
94 Examene si Concursuri

We will now present some mostly trivial consequences of the denitions.

If an array is k-balanced, then it is mk-balanced for any positive integer m.
Hence, if it is (p, q)-balanced, then it is (mp, nq)-balanced for any positive
integers m, n.
The set L of all (M N )-seeds for a (p, q)-balanced array is a lattice.
If there exists a (M N )-seed, then it canonically yields a (mM nN )-seed,
by extension through periodicity, therefore a square ([M, N ] [M, N ])-seed
does exist. If there exists both a (M N )-seed and a (M
N
)-seed, then
there exist a ([M, M
] [N, N
])-seed, and a ((M, M
) (N, N
))-seed (by the
extension to the Lemma). Finally, if L is not empty, there exists a minimal
(M0 N0 )-seed, in the sense that for any other (M N )-seed we have M0 |M
and N0 |N , and a minimal square ([M0 , N0 ] [M0 , N0 ])-seed.
(i) Clearly the k-balanced property is hereditary to any rectangular
m n sub-array. Consider any pq pq square sub-array. A little bit of
double counting shows that the sum of its elements is both q 2 vp (partition
it in p p sub-squares), and p2 vq (partition it in q q sub-squares), hence
q 2 vp = p2 vq .
(ii) Assume only two real values x = y are used. Let us transform a
vx
value v into , which turns x into 0 and y into 1. The sums of elements
yx
of k k sub-squares (for k equal to p or q) remain constant, in fact vk turns
vk k2 x
into , the number of ys in the k k sub-square. Now, the formula
yx
from point (a) implies that p2 |vp and q 2 |vq , but the array being non-constant
we must have 0 < vp < p2 and 0 < vq < q 2 , contradiction.
If (p, q) > 1, build the array by using as seed any (p, q) (p, q) square
block made of two values only (of course the array will be constant at the
coarser level of granularity of these blocks, but non-constant at the level of
granularity of unit squares).
(iii) We will show that a square (pq pq)-seed will do, therefore L =  .
k1

Denote k ri,j := ai,j+ , the sum of k consecutive elements on row i,
=0
k1

starting from column j. Similarly, denote k ci,j := ai+,j , the sum of k
=0
consecutive elements on column j, starting from row i.
We have p ri,k = p ri+p,k for any non-negative integers i, j, and k j,
because of the p-balanced property. By iterating, this yields
p ri,k = p ri+qp,k .
p1
 q1

Denote xn := ai,n ai+qp,n , hence xk+ = 0. Similarly xk+ = 0.
=0 =0
 The ,,Math Stars Contest 95

But this means the sequence (xk )kj is both p-periodic and q-periodic,
so according to the Lemma it must be constant. Now, that constant must
p1

be 0, since xj+ = 0. So xj = 0, hence ai,j = ai+qp,j for all non-negative
=0
integers i, j.
In a totally similar manner (working along the other dimension) we get
ai,j = ai,j+pq for all non-negative integers i, j, and therefore we have proven
the array originates from a square (pq pq)-seed.
(iv) Let us present a model of a (p q)-seed using only three dierent
values, which results into a (p, q)-balanced array with vp = vq = 0.

0 0 0 0
.. .. .. . . .
. . . . ..
0 0 0 0
-1 1 0 0
1 -1 0 0
Table 1. A general (p q)-seed.

(v) We can build a k-balanced array starting with two orthogonal strips
of width k1 made of arbitrary values, having the origin as lower left crossing
point, choosing an arbitrary value for vk , and lling up the rest of the array,
step by step, in the uniquely possible manner. For (p, q) > 1 just take
k = (p, q); the p p and q q sub-squares are made of k k sub-squares, so
2 2
the array is doubly-balanced, with vp = kp2 vk and vq = kq 2 vk . Then L = .

.. .. ..
.. ..
. . .
. .
ak1,0
ak1,k2 up to vk
ak2,0
ak2,k2 ak2,k1
.. .. .. .. ..
. . . . .
a0,0 a0,k2 a0,k1
Table 2. A general k-balanced array starting from (k 1)-
wide strips.

(vi) We have seen at point (iii) that T = pq yields a square seed. Any
least value will have to be a divisor of pq.
Let us prove that for (p, q) = 1, p > q 2, there can never exist a
(q q)-seed. Assume the converse; then p ri,j = p ri+mq,j and p ci,j = p ci,j+p ,
for any positive integer m, from periodicity. But in a (p, q)-balanced array
we need have p ri,j = p ri+mp,j and p ci,j = p ci,j+mp . Since (p, q) = 1, there
exist positive integers u, v such that 1 = up vq. Then p ri,j = p ri+up,j =
p r(i+up)vq,j = p ri+1,j , hence, by iteration, all p ri+m,j are equal, for m 0.
96 Examene si Concursuri

p1
 p1

But (p ri+k,j+1 p ri+k,j ) = (p ri,j+1 p ri,j ) = p(p ri,j+1 p ri,j ),
k=0 k=0
and this is p ci,j+p p ci,j = 0, hence we will have all p ri,j+m equal, for m 0,
by iteration. This means that any row i is both q-periodic and p-periodic,
hence, according to the Lemma, constant, so there exists a (q 1)-seed. But
then any column j will be both q-periodic and p-periodic, hence, according
again to the Lemma, constant, so there exists a (1 1)-seed, i.e. the array
would be constant, absurd.
Similarly, there can never exist a (p p)-seed. Take p
= (p 1)q > p =
= q
, so (q
, p
) = 1, and clearly a q-balanced array is also (p 1)q-balanced,
hence the array would be (p
, q
)-balanced, so we can apply the above result.
Therefore T = pq is minimal for p, q both primes.
Otherwise take Q|q. If a (Q Q)-seed would exist, then a (q q)-
seed would exist, absurd. Similarly for P |p. Therefore a least square seed
need contain factors P , Q from both p, respectively q, and we have seen at
point (iv) how to build a (P Q)-seed resulting in a (P, Q)-balanced array,
which will also be (p, q)-balanced, so this shows there exist co-prime (p, q)-
balanced arrays originating from (P Q)-seeds, hence from a (P QP Q)-seed.
The minimal value is achieved when P , Q are the least prime factors of p,
respectively q.
(vii) Let us exhibit the general structure of a minimal square (6 6)-
seed for a (2, 3)-balanced array with v2 = v3 = 0. We use arbitrary real a, b,
1
c and x, with = (a + b + c) (of course, we can add any value v to all cells).
3
A general minimal (2 3)-seed is obtained for a = b = c = . A general
minimal (3 2)-seed is obtained for = x = 0.
b 2 b x + 2 b+x b bx b + x +
c c + x cx c + 2 c + x 2 c x +
a 2 a x + 2 a+x a ax a + x +
b b + x bx b + 2 b + x 2 b x +
c 2 c x + 2 c+x c cx c + x +
a a + x ax a + 2 a + x 2 a x +
Table 3. The minimal square (6 6)-seed for a (2, 3)-balanced array.
This suggests there exist co-prime (p, q)-balanced arrays for which the
minimal seed is the square (pqpq)-seed prescribed at point (iii). Moreover, it
was obvious already from the result at point (iii) that the number of dierent
values such an array uses is at most p2 q 2 , and from the result at point (iv)
that it is at least 3. (For the particular case, one can see that the number of
dierent values can indeed be 22 32 = 36.)
Indeed, the conjecture formulated in the above turns to be true! The
linear combination, with = 0, of the array A generated by the (p q)-seed
at point (d), and the array tA generated by the transposed (q p)-seed, is
 Probleme propuse 97

an array B = A + tA, clearly (p, q)-balanced, and with minimal seed the
square (pq pq)-seed thus obtained.

PROBLEME

PROBLEME PENTRU CICLUL PRIMAR1)

P:121. Care este diferenta dintre cel mai mare si cel mai mic numar
natural de trei cifre daca ambele numere ndeplinesc simultan urmatoarele
conditii:
i) diferenta dintre cifra sutelor si cifra zecilor este egala cu 3;
ii) diferenta dintre cifra zecilor si cifra unitatilor este egala cu 2 ?
Iuliana Dragan, Bucuresti
P:122. Insumand jumatatea, sfertul si optimea unui numar se obtine
diferenta dintre cel mai mare numar natural de patru cifre distincte si cel
mai mare numar natural par de trei cifre distincte. Care este numarul?
Iuliana Dragan, Bucuresti
P:123. Care este cel mai mic numar natural de forma abcdef , scris cu
cifre diferite, stiind ca a + f = b + e = c + d ?
Iuliana Dragan, Bucuresti
P:124. Un producator a vandut la piata 1800 kg de mere de trei calitati
avand preturile: 2 lei pe kg; 3 lei pe kg si 4 lei pe kg. Pentru marfa vanduta
a ncasat 5200 lei. Cantitatea de mere cu pretul de 3 lei pe kg a fost dublul
cantitatii de mere cu pretul de 2 lei pe kg. Determinati cantitatile de mere
din ecare sortiment vandut.
D.M. Batinetu-Giurgiu, Bucuresti
P:125. Peste 4 ani, Ionel ar avea o treime din varsta de acum a tatalui
sau. Acum, au mpreuna 52 de ani. Cati ani va avea tatal lui Ionel cand
acesta va avea varsta de acum a tatalui sau ?
Ana Popa, 23 August, Constanta
P:126. Un grup de turisti intetioneaza sa ia pranzul la o cantina
forestiera. Daca s-ar aseza cate 3 persoane la masa, ar ramane 9 persoane n
picioare, iar asezandu-se cate 4, la ultima masa ar ramane un singur turist.
Cati turisti si cate mese are cantina?
Ana Popa, 23 August, Constanta
P:127. Trie stilouri costa cat patru pixuri, iar mpreuna valoarea lor
este de 48 de lei. Aati cu cati lei costa mai mult 6 stilouri decat 4 pixuri.
Ana Popa, 23 August, Constanta
1) Se primesc solutii pana la 30 iunie 2009 (data postei). (N.R.)