Päevaülesanne

Juhuslik

Harjutuskomplekt

Balti Tee 2018 · Ülesanne 10

Kombinatoorika

The integers from 1 to nn are written, one on each of nn cards. The first player removes one card. Then the second player removes two cards with consecutive integers. After that the first player removes three cards with consecutive integers. Finally, the second player removes four cards with consecutive integers. What is the smallest value of nn for which the second player can ensure that he completes both his moves?

Muuda valikut

Kui oled valmis

Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.

Ülevaade

Teemad

Mängud ja strateegiad · Algoritmid ja protsessid

Lahendused

Lahendus

Answer: n=14n = 14.

At first, let's show that for n=13n = 13 the first player can ensure that after his second move no 44 consecutive numbers are left. In the first move he can erase number 44 and in the second move he can ensure that numbers 88, 99 and 1010 are erased. No interval of length 44 is left.

If n=14n = 14 the second player can use the following strategy. Let the first player erase number kk in his first move, because of symmetry assume that k≤7k \le 7. If k≥5k \ge 5 then the second player can erase k+1k+1 and k+2k+2 and there are two intervals left of length at least 44: 1..(k−1)1..(k-1) and (k+3)..14(k+3)..14, but the first player can destroy at most one of them. But if k≤4k \le 4, then the second player can erase numbers 99 and 1010 in his first move and again there are two intervals left of length at least 44: (k+1)..8(k+1)..8 and 11..1411..14.

Võistluse kontekst

Balti Tee tulemused 2018

11 võistkonda

Keskmine tulemus
4,5 / 5
4 või 5 punkti
10 / 11
Eesti
5 / 5

Punktijaotus

01
10
20
30
40
510
Kõigi võistkondade punktid
VõistkondPunktid
Germany5 / 5
St. Petersburg5 / 5
Denmark5 / 5
Estonia5 / 5
Sweden5 / 5
Norway5 / 5
Lithuania5 / 5
Finland5 / 5
Latvia5 / 5
Poland5 / 5
Iceland0 / 5