MathDB

1

m skyscrapers in square grid nxn

Let a city be in the form of a square grid which has

n \times n

cells, each of which contain a skyscraper . At first the

m

skyscrapers burn, but the fire spreads: everyone skyscraper that has at least two burning neighboring houses (by neighboring houses we mean only houses that border the house along a street, not just at a corner) immediately gets fire. Prove that when in the end the whole city burns down, of must have been

m \ge n

.
[hide=original wording in German] Eine Stadt habe die Form eines quadratischen Gitters, welches n × n Zellen habe, von denen jede ein Hochhaus enthalte. Anfangs brennen m der Hochh¨auser, doch der Brand pflanzt sich fort: Jedes Hochhaus, das mindestens zwei brennende Nachbarh¨auser hat (unter Nachbarh¨ausern verstehen wir dabei nur H¨auser, die entlang einer Straße an das Haus angrenzen, nicht nur an einer Ecke), f¨angt sofort Feuer. Man beweise: Wenn am Ende die gesamte Stadt abgebrannt ist,muss m ≥ n gewesen sein.

8

1

a_\pi(1)/ b_\pi(1)} <a_\pi(2)/ b_\pi(2)} < ...< a_\pi(n)/ b_\pi(n)}

Let

(a_1, a_2,..., a_n)

and

(b_1, b_2, ..., b_n)

be two sequences of positive real numbers. Let

\pi

be a permutation of the set

\{1, 2, ..., n\}

, for which the sum

a_{\pi(1)}(b_{\pi(1)}+b_{\pi(2)}+...+b_{\pi(n)})+a_{\pi(2)}(b_{\pi(3)}+b_{\pi(3)}+...+b_{\pi(n)})+...+a_{\pi(n)}b_{\pi(n)}

is minimal. Proce for this permutation

\pi

, that

\frac{a_{\pi(1)}}{b_{\pi(1)}}\le \frac{a_{\pi(2})}{b_{\pi(2)}}\le ... \le \frac{a_{\pi(n)}}{b_{\pi(n)}}

Application: In an idealized role-playing game you fight against

n

opponents at the same time. In order to minimize the damage you suffer yourself, you should first take care of your opponent for the ratio of the time it takes to defeat him (if you only focus on him), and the damage it does per second is minimal; next, one should fight the opponent with the second smallest such ratio, and so on.

11

1

equal periodic sequences

Let

m

and

n

be two natural numbers and let

d = gcd (m, n)

their greatest common divisor. Let

a_1, a_2,...

and

b_1, b_2, ...

be two sequences of integers which are periodic with periods

m

and

n

respectively (this means that

a_{i + m} = a_i

and

b_{i + n} = b_i

for all natural numbers

i \ge 1

, note that there could be smaller periods). Prove that if the two sequences on the first

m + n - d

terms match (i.e.

a_i = b_i

for all

i \in \{1, 2, ..., m + n - d\}

), then they are the same (so

a_i = b_i

for all natural

i \ge 1

).

10

1

sum with permutations of 1,2.,...n

Let

a_1, a_2, ..., a_n

be positive real numbers. Furthermore, let

S_n

denote the set of all permutations of set

\{1, 2, ..., n\}

. Prove that

\sum_{\pi \in S_n} \frac{1}{a_{\pi(1)}(a_{\pi(1)}+a_{\pi(2)})...(a_{\pi(1)}+a_{\pi(2)}+...+a_{\pi(n)})}=\frac{1}{a_1 a_2 ... a_n}

9

1

(-1)^{ (p+1)/2 }+\sum {2n \choose n}c^n is divisible by p

Let

p

be an odd prime number and

c

an integer for which

2c -1

is divisible by

p

. Prove that

(-1)^{\frac{p+1}{2}}+\sum_{n=0}^{\frac{p-1}{2}} {2n \choose n}c^n

is divisible by

p

.

4

1

equal sum of areas, square inside a square

Let

ABCD

and

A'B'C'D'

be two squares, both are oriented clockwise. In addition, it is assumed that all points are arranged as shown in the figure.Then it has to be shown that the sum of the areas of the quadrilaterals

ABB'A'

and

CDD'C'

equal to the sum of the areas of the quadrilaterals

BCC'B'

and

DAA'D'

. https://cdn.artofproblemsolving.com/attachments/0/2/6f7f793ded22fe05a7b0a912ef6c4e132f963e.png

7

1

concurrent wanted, 6 circles, equal into 3 pairs, tangencies given

Let

ABC

be a triangle. Let

x_1

and

x_2

be two congruent circles, which touch each other and the segment

BC

, and which both lie within triangle

ABC

, and for which it also holds that

x_1

touches the segment

CA

, and that

x_2

is the segment

AB

. Let

X

be the contact point of these two circles

x_1

and

x_2

. Let

y_1

and

y_2

two congruent circles that touch each other and the segment

CA

, and both within of triangle

ABC

, and for which it also holds that

y_1

touches the segment

AB

, and that

y_2

the segment

BC

. Let

Y

be the contact point of these two circles

y_1

and

y_2

. Let

z_1

and

z_2

be two congruent circles that touch each other and the segment

AB

, and both within triangle

ABC

, and for which it also holds that

z_1

touches the segment

BC

, and that

z_2

the segment

CA

. Let

Z

be the contact point of these two circles

z_1

and

z_2

. Prove that the straight lines

AX, BY

and

CZ

intersect at a point.

12

1

AL _|_ BC wanted, altitudes, projections

Let

Y

and

Z

be the feet of the altitudes of a triangle

ABC

drawn from angles

B

and

C

, respectively. Let

U

and

V

be the feet of the perpendiculars from

Y

and

Z

on the straight line

BC

. The straight lines

YV

and

ZU

intersect at a point

L

. Prove that

AL \perp BC

.

5

1

sums with number of divisors

For a natural number

n

, let

D (n)

be the set of (positive integers) divisors of

n

. Furthermore let

d (n)

be the number of divisors of

n,

that is, the cardinality of

D (n)

. For each such

n

, prove the equality

\sum_{k\in D(n)} d(k)^3=\left( \sum_{k\in D(n)} d(k)\right) ^2.

3

1

words of max 3n letters in alphabet of n letters

An alphabet has

n

letters. A word is called differentiated if it has the following property fulfilled: No letter occurs more than once between two identical letters. For example with the alphabet

\{a, b, c, d\}

the word abbdacbdd is not, the word bbacbadcdd is differentiated. (a) Each differentiated word has a maximum of

3n

letters. (b) How many differentiated words with exactly

3n

letters are ther

2

1

c (a,b) c(b,a) = 1 = c(a,-a)

Let

c: Q-\{0\} \to Q-\{0\}

a function with the following properties (for all

x,y, a, b \in Q-\{0\}

and

x \ne 1

): a)

c (x, 1- x) = 1

b)

c (ab,y) = c (a,y)c(b, y)

c)

c (y,ab) = c (y, a)c(y,b)

Show that then

c (a,b) c(b,a) = 1 = c(a,-a)

also holds.

1

n^n + 1 and (2n)^{2n} + 1 are both primes

Find all natural numbers

n

for which both

n^n + 1

and

(2n)^{2n} + 1

are prime numbers.

2010 QEDMO 7th

Subcontests

m skyscrapers in square grid nxn

a_\pi(1)/ b_\pi(1)} <a_\pi(2)/ b_\pi(2)} < ...< a_\pi(n)/ b_\pi(n)}

equal periodic sequences

sum with permutations of 1,2.,...n

(-1)^{ (p+1)/2 }+\sum {2n \choose n}c^n is divisible by p

equal sum of areas, square inside a square

concurrent wanted, 6 circles, equal into 3 pairs, tangencies given

AL _|_ BC wanted, altitudes, projections

sums with number of divisors

words of max 3n letters in alphabet of n letters

c (a,b) c(b,a) = 1 = c(a,-a)

n^n + 1 and (2n)^{2n} + 1 are both primes

2010 QEDMO 7th

Subcontests

m skyscrapers in square grid nxn

a_\pi(1)/ b_\pi(1)} &lt;a_\pi(2)/ b_\pi(2)} &lt; ...&lt; a_\pi(n)/ b_\pi(n)}

equal periodic sequences

sum with permutations of 1,2.,...n

(-1)^{ (p+1)/2 }+\sum {2n \choose n}c^n is divisible by p

equal sum of areas, square inside a square

concurrent wanted, 6 circles, equal into 3 pairs, tangencies given

AL _|_ BC wanted, altitudes, projections

sums with number of divisors

words of max 3n letters in alphabet of n letters

c (a,b) c(b,a) = 1 = c(a,-a)

n^n + 1 and (2n)^{2n} + 1 are both primes

a_\pi(1)/ b_\pi(1)} <a_\pi(2)/ b_\pi(2)} < ...< a_\pi(n)/ b_\pi(n)}