MathDB

Archipelago islands - TT 2009 Junior-A7 and SeniorA-6

Source:

9/3/2010

Anna and Ben decided to visit Archipelago with

2009

islands. Some pairs of islands are connected by boats which run both ways. Anna and Ben are playing during the trip:
Anna chooses the first island on which they arrive by plane. Then Ben chooses the next island which they could visit. Thereafter, the two take turns choosing an island which they have not yet visited. When they arrive at an island which is connected only to islands they had already visited, whoever's turn to choose next would be the loser. Prove that Anna could always win, regardless of the way Ben played and regardless of the way the islands were connected.
(12 points for Juniors and 10 points for Seniors)

Ali Baba - TT 2009 Senior-A7

Source:

9/3/2010

At the entrance to a cave is a rotating round table. On top of the table are

n

identical barrels, evenly spaced along its circumference. Inside each barrel is a herring either with its head up or its head down. In a move, Ali Baba chooses from

1

to

n

of the barrels and turns them upside down. Then the table spins around. When it stops, it is impossible to tell which barrels have been turned over. The cave will open if the heads of the herrings in all

n

barrels are up or are all down. Determine all values of

n

for which Ali Baba can open the cave in a finite number of moves.
(11 points)

algorithminduction

2009 ToT Spring Junior A P7 common divisors of binomials

Source:

3/7/2020

Let

{n \choose k}

be the number of ways that

k

objects can be chosen (regardless of order) from a set of

n

objects. Prove that if positive integers k and l are greater than

1

and less than

n

, then integers

{n \choose k}

and

{n \choose l}

have a common divisor greater than

1

.

Binomialcombinatorics

2009 ToT Spring Senior A P7 k is replaced by k+gcd(k,n)

Source:

3/7/2020

Initially a number

6

is written on a blackboard. At

n

-th step an integer

k

on the blackboard is replaced by

k+gcd(k,n)

. Prove that at each step the number on the blackboard increases either by

1

or by a prime number.

GCDnumber theoryprime

7

Problems(4)