MathDB

1

subsets with integer coordinates

a

and

b

be natural numbers. We consider the set

M

of the points of the plane with an integer

x

-coordinate from

1

to

a

and integer

y

-coordinate from

1

to

b

. For two points

P = (x, y)

and

Q = (\tilde x, \tilde y)

in M we write

P\le Q

if

x\le \tilde x

and

y \le \tilde y

, we say

P

is less than

Q

when

P\le Q

and

P \ne Q

. A subset

S

of

M

is now called cute if for every point

P \in S

it also contains all smaller points. From an arbitrary subset

S

of

M

we can now create new subsets in four ways to construct: (a) the complement

K (S) = \overline{S}

, (b) the subset

\min (S)

of its minima, i.e. those points for which there is no smaller in

S

occurs, (c) the cute set

P (S)

of all those points in M that are less than or equal to some point are from

S

, (d) you do all these things one after the other and get a set

Z (S) = P (\min (K (S)))

. Let

S

be cute. Prove that

\underset{a+b\,\, times\,\, Z}{Z(Z(...(Z(S))...))=S}

3

1

n sizes of presents and n packages for Santa Claus

Santa Claus wants to wrap presents. These are available in

n

sizes

A_1 <A_2 <...<A_n

, and analogously, there are

n

packaging sizes

B_1 <B_2 <...<B_n

, where

B_i

is enough to all gift sizes

A_j

can be grouped with

j\le i

, but too small for those with

j> i

. On the shelf to the right of Santa Claus are the gifts sorted by size, where the smallest are on the right, of course there can be several gifts of the same size, or none of a size at all. To his left is a shelf with packaging, and also these are sorted from small to large in the same direction. He's brooding in what way he should wrap the gifts and sees two methods for doing this, which depend on his thinking and laziness of movement have been optimized: a) He takes the present closest to him and puts it in the closest packaging, in which it fits in. b) He takes the packaging closest to him and packs in it the closest thing to him gift. In both cases he then does the same again, although of course the one he was using the gift and its packaging are missing, and so on. Once it is not large enough if the packaging or the present is not small enough, he / she will provide the present or the packaging back to its place on the shelf and takes the next-closest. Prove that both methods lead to the same result in the end, they are considered to be exactly the same gifts packed in the same packaging.

2

1

\sum_{m \in M} (-1) ^m (n m) is divisible by p^q

Let

p

be a prime number and

n, k

and

q

natural numbers, where

q\le \frac{n -1}{p-1}

should be. Let

M

be the set of all integers

m

from

0

to

n

, for which

m-k

is divisible by

p

. Show that

\sum_{m \in M} (-1) ^m {n \choose m}

is divisible by

p^q

.

10

1

x^p + px^n + px^m +1 not a product of 2 integer polynomials

Let

p

be a prime number gretater then

3

. What is the number of pairs

(m, n)

of integers with

0 <m <n <p

, for which the polynomial

x^p + px^n + px^m +1

is not a product of two non-constant polynomials with integer coefficients can be written?

9

1

finite primes of form a_1 + k; a_2 + k; a_3 + k,..

Are there infinitely many different natural numbers

a_1,a_2, a_3,...

so that for every integer

k

only finitely many of the numbers

a_1 + k

,

a_2 + k

,

a_3 + k

,

...

are numbers prime?

7

1

comb geo with distances among n points in plane

Let

X_1, X_2,...,X_n

be points in the plane. For every

i

, let

A_i

be the list of

n-1

distances from

X_i

to the remaining points. Find all arrangements of the

n

points such all of these lists are the same, except for the order.

4

1

periodic if f (x) + f (x + 2a) + f (x + 3a) + f (x + 5a) = 1

Let

a> 0

and

f: R\to R

a function such that

f (x) + f (x + 2a) + f (x + 3a) + f (x + 5a) = 1

for all

x\in R

. Show that

f

is periodic, that is, that there is some

b> 0

for which

f (x) = f (x + b)

for every

x \in R

holds. Find the smallest such

b

, which works for all these functions .

6

1

at most one of 2^{2^n}+ 1 and 6^{2^n}+ 1 is prime

A composite natural number

n

is called happy if at most one of the numbers

2^{2^n}+ 1

and

6^{2^n}+ 1

is prime. Show that there are infinitely many happy numbers.

5

1

16 pieces of 1x 3 on a 7x7 chessboard

16

pieces of the shape

1\times 3

are placed on a

7\times 7

chessboard, each of which is exactly three fields. One field remains free. Find all possible positions of this field.

1

lightly damaged rook on a mxn chessboard

A lightly damaged rook moves around on a

m \times n

chessboard by taking turns moves to a horizontal or vertical field. For which

m

and

n

, is it possible for him to have visited each field exactly once? The starting field counts as visited, squares skipped during a move, however, are not.

2013 QEDMO 13th or 12th

Subcontests

subsets with integer coordinates

n sizes of presents and n packages for Santa Claus

\sum_{m \in M} (-1) ^m (n m) is divisible by p^q

x^p + px^n + px^m +1 not a product of 2 integer polynomials

finite primes of form a_1 + k; a_2 + k; a_3 + k,..

comb geo with distances among n points in plane

periodic if f (x) + f (x + 2a) + f (x + 3a) + f (x + 5a) = 1

at most one of 2^{2^n}+ 1 and 6^{2^n}+ 1 is prime

16 pieces of 1x 3 on a 7x7 chessboard

lightly damaged rook on a mxn chessboard