MathDB
Problems
Contests
National and Regional Contests
Ukraine Contests
Other Ukrainian Contests
Kyiv Mathematical Festival
2020 Kyiv Mathematical Festival
2020 Kyiv Mathematical Festival
Part of
Kyiv Mathematical Festival
Subcontests
(5)
1.2
1
Hide problems
sum C_{n}^{k} (k/n -1/2)^2 1/2^n =1/4n, part b has a double sum
Prove that (a) for each
n
≥
1
n \ge 1
n
≥
1
∑
k
=
0
n
C
n
k
(
k
n
−
1
2
)
2
1
2
n
=
1
4
n
\sum_{k=0}^n C_{n}^{k} \left(\frac{k}{n}-\frac{1}{2} \right)^2 \frac{1}{2^n}=\frac{1}{4n}
k
=
0
∑
n
C
n
k
(
n
k
−
2
1
)
2
2
n
1
=
4
n
1
(b) for every n \ge m \ge 2
∑
ℓ
=
0
n
∑
k
1
+
.
.
.
+
k
n
=
ℓ
,
k
i
=
0
,
.
.
.
,
m
ℓ
!
k
1
!
.
.
.
k
n
!
1
(
m
+
1
)
n
(
ℓ
n
−
m
2
)
2
=
(
m
3
−
3
m
2
12
(
m
+
1
)
+
m
2
−
m
3
(
m
+
1
)
)
n
\sum_{\ell=0}^n \sum_{k_1+...+k_n=\ell,k_i=0,...,m} \frac{\ell!}{k_1!...k_n!} \frac{1}{(m+1)^n} \left(\frac{\ell}{n}-\frac{m}{2} \right)^2= \left(\frac{m^3-3m^2}{12(m+1)}+\frac{m}{2}-\frac{m}{3(m+1)}\right)n
ℓ
=
0
∑
n
k
1
+
...
+
k
n
=
ℓ
,
k
i
=
0
,
...
,
m
∑
k
1
!
...
k
n
!
ℓ
!
(
m
+
1
)
n
1
(
n
ℓ
−
2
m
)
2
=
(
12
(
m
+
1
)
m
3
−
3
m
2
+
2
m
−
3
(
m
+
1
)
m
)
n
5
1
Hide problems
delivery of n kg of wheat from n cities of country A to n cities of country B
The cities of countries
A
A
A
and
B
B
B
are marked on the map, which has the form of a square with vertices at points
(
0
,
0
)
(0, 0)
(
0
,
0
)
,
(
0
,
1
)
(0, 1)
(
0
,
1
)
,
(
1
,
1
)
(1, 1)
(
1
,
1
)
,
(
1
,
0
)
(1, 0)
(
1
,
0
)
of the plane. According to the trade agreement, country
A
A
A
must ensure the delivery of
n
n
n
kg of wheat to
n
n
n
cities of country
B
B
B
, located at the points of the square with coordinates
y
1
,
.
.
.
,
y
n
y_1,..., y_n
y
1
,
...
,
y
n
,
1
1
1
kg each city. Currently,
n
n
n
kg of wheat are distributed among
n
n
n
cities of country
A
A
A
, located at the points of the square with coordinates
x
1
,
.
.
.
,
x
n
x_1,... , x_n
x
1
,
...
,
x
n
,
1
1
1
kg in each city. From each city of country
A
A
A
to each city of the country
A
A
A
any amount of wheat can be transported (of course, not more than
1
1
1
kg). Transportation cost is for
t
t
t
kg of wheat from a city with coordinates
x
i
x_i
x
i
to a city with coordinates
y
j
y_j
y
j
is equal to
t
l
i
j
tl_{ij}
t
l
ij
, where
l
i
j
l_{ij }
l
ij
is the length of the segment connecting the points
x
i
x_i
x
i
and
y
j
y_j
y
j
. The government of country A is going to implement the optimal one (i,e. the cheapest) transportation plan.(a) Is it possible to implement the optimal transportation plan so that from each city of country
A
A
A
to transport wheat only to one city of country
B
B
B
?(b) Will the response change if country
A
A
A
is to deliver
n
+
1
n+1
n
+
1
kg of wheat, in city
x
1
x_1
x
1
is
2
2
2
kg of wheat, and
2
2
2
kg should be delivered to city
y
1
y_1
y
1
(when for other cities the conditions remain the same)?[hide=original wording] Мiста країн A та B позначенi на мапi, що має вигляд квадрату з вершинами в точках (0, 0), (0, 1), (1, 1), (1, 0) площини. Згiдно торгової угоди, країна A має забез- печити доставку n кг пшеницi в n мiст країни B, що розташованi в точках квадрату з координатами y1, . . . , yn, по 1 кг в кожне мiсто. Наразi n кг пшеницi розподiленi серед n мiст країни A, що розташованi в точках квадрату з координатами x1, . . . , xn, по 1 кг в кожному мiстi. З кожного мiста країни A в кожне мiсто країни B можна перевезти довiльну кiлькiсть пшеницi (звичайно, не бiльше 1 кг). Вартiсть переве- зення t кг пшеницi з мiста з координатами xi в мiсто з координатами yj дорiвнює tlij , де lij – довжина вiдрiзку, що сполучає точки xi та yj . Уряд країни A збирається реалiзувати оптимальний (тобто найдешевший) план перевезення. 1. Чи можна реалiзувати оптимальний план перевезення таким чином, щоби з кожного мiста країни A перевозити пшеницю тiльке в одне мiсто країни B? 2. Чи змiниться вiдповiдь, якщо країна A має забезпечити доставку n + 1 кг пше- ницi, в мiстi x1 знаходиться 2 кг пшеницi, i в мiсто y1 має бути доставлено 2 кг пшеницi (щодо iнших мiст умови лишаються такими ж)?
4
1
Hide problems
2 players m, 3 piles of different no of stones game
(a) Two players take turns taking
1
,
2
1, 2
1
,
2
or
3
3
3
stones at random from a given set of
3
3
3
piles, in which initially on
11
,
22
11, 22
11
,
22
and
33
33
33
stones. If after the move of one of the players in any two groups the same number of stones will remain, this player has won. Who will win with the right game of both players?(b) Two players take turns taking
1
1
1
or
2
2
2
stones from one pile, randomly selected from a given set of
3
3
3
ordered piles, in which at first
100
,
200
100, 200
100
,
200
and
300
300
300
stones, in order from left to right. Additionally it is forbidden to make a course at which, for some pair of the next handfuls, quantity of stones in the left will be more than the number of stones in the right. If after the move of one of the players of the stones in handfuls will not remain, then this player won. Who will win with the right game of both players?[hide=original wording] 1. Два гравця по черзi беруть 1, 2 чи 3 камiнця довiльним чином з заданого набору з 3 купок, в яких спочатку по 11, 22 i 33 камiнцiв. Якщо пiсля хода одного з гравцiв в якихось двух купках залишиться однакова кiлькiсть камiнцiв, то цей гравець виграв. Хто виграє при правильнiй грi обох гравцiв?2. Два гравця по черзi беруть 1 чи 2 камiнця з одної купки, довiльної вибраної з заданого набору з 3 впорядкованих купок, в яких спочатку по 100, 200 i 300 камiнцiв, в порядку злiва направо. Додатково забороняется робити ход при якому, для деякої пари сусiднiх купок, кiлькiсть камiнцiв в лiвiй стане бiльше нiж кiлькiсть камiнцiв в правiй. Якщо пiсля ходу одного з гравцiв камiнцiв в купках не залишиться, то цей гравець виграв. Хто виграє при правильнiй грi обох гравцiв?
2
2
Hide problems
routes for 2 person tossing a coin inside a right isosceles triangle
On the map, the Flower City has the form of a right triangle
A
B
C
ABC
A
BC
(see Fig.1). The length of each leg is
6
6
6
meters. All the streets of the city run parallel to one of the legs at a distance of
1
1
1
meter from each other. A river flows along the hypotenuse. From their houses that are located at points
V
V
V
and
S
S
S
, at the same time get the Cog and Tab. Each short moves to rivers according to the following rule: tosses his coin, and if the heads falls, he passes
1
1
1
meter parallel to the leg
A
B
AB
A
B
to the north (up), and if tails, then passes
1
1
1
meter parallel to the leg
A
C
AC
A
C
on east (right). If the Cog and the Tab meet at the same point, then they move together, tossing a coin.a) Which is more likely: Cog and Tab will meet on the way to the river, or will they come to different points on the shore?b) At what point near the river should the Stranger sit, if he wants the most did Gvintik and Shpuntik come to him together? https://cdn.artofproblemsolving.com/attachments/d/c/5d6f75d039e8f2dd6a0ddfe6c4cb046b83f24c.png [hide=original wording] На мапi Квiткове мiсто має вигляд прямокутного трикутника ABC (див. рисунок 1). Довжина кожного катету – 6 метрiв. Всi вулицi мiста проходять паралельно одному за катетiв на вiдстанi 1 метра одна вiд одної. Вздовж гiпотенузи тече рiка. Зi своїх будиночкiв, що знаходяться в точках V та S, одночасно виходять Гвинтик та Шпунтик. Кожен коротулька рухається до рiчки за таким правилом: пiдкидає свою монетку, та якщо випадає Орел, вiн проходить 1 метр паралельно катету AB на пiвнiч (вгору), а якщо Решка, то проходить 1 метр паралельно катету AC на схiд (вправо). Якщо Гвинтик та Шпунтик зустрiчаються в однiй точцi, то далi вони рушають разом, пiдкидаючи монетку Гвинтика.1. Що бiльш ймовiрно: Гвинтик та Шпунтик зустрiнуться на шляху до рiки, або вони прийдуть у рiзнi точки берега?2. В якiй точцi бiля рiки має сидiти Незнайка, якщо вiн хоче, щоб найбiльш ймовiрно до нього прийшли Гвинтик та Шпунтик разом?
m huts on a line, 3 stores to deliver chocolates, bread and water
Mummy-trolley huts are located on a straight line at points with coordinates
x
1
,
x
2
,
.
.
.
.
,
x
n
x_1, x_2,...., x_n
x
1
,
x
2
,
....
,
x
n
. In this village are going to build
3
3
3
stores
A
,
B
A, B
A
,
B
and
C
C
C
, of which will be brought every day to all Moomin-trolls chocolates, bread and water. For the delivery of chocolate, the store takes the distance from the store to the hut, raised to the square; for bread delivery , take the distance from the store to the hut; for water delivery take distance
1
1
1
, if the distance is greater than
1
1
1
km, but do not take anything otherwise.a) Where to build each of the stores so that the total cost of all Moomin-trolls for delivery wasthe smallest?b) Where to place the TV tower, if the fee for each Moomin-troll is the maximum distance from the TV tower to the farthest hut from it?c) How will the answer change if the Moomin-troll huts are not located in a straight line, and on the plane?[hide=original wording] На прямiй розташованi хатинки Мумi-тролей в точках з координатами x1, x2, . . . , xn. В цьому селi бираються побудувати 3 магазина A, B та C, з яких будуть кожен день привозити всiм Мумi-тролям шоколадки, хлiб та воду. За доставку шоколадки мага- зин бере вiдстань вiд магазину до хатинки, пiднесену до квадрату; за доставку хлiба – вiдстань вiд магазину до хатинки; за доставку води беруть 1, якщо вiдстань бiльша 1 км, та нiчого не беруть в супротивному випадку. 1. Де побудувати кожний з магазинiв, щоб загальнi витрати всiх Мумi-тролей на доставку були найменшими? 2. Де розташувати телевежу, якщо плата для кожного Мумi-троля – максимальна вiдстань вiд телевежi до самої вiддаленої вiд неї хатинки? 3. Як змiниться вiдповiдь, якщо хатинки Мумi-тролей розташованi не на прямiй, а на площинi?
1.1
1
Hide problems
a_k = 1+/1/2 a_{k- 1} + 1/2 a_{k+1 }
(a) Find the numbers
a
0
,
.
.
.
,
a
100
a_0,. . . , a_{100}
a
0
,
...
,
a
100
, such that
a
0
=
0
,
a
100
=
1
a_0 = 0, a_{100} = 1
a
0
=
0
,
a
100
=
1
and for all
k
=
1
,
.
.
.
,
99
k = 1,. . . , 99
k
=
1
,
...
,
99
:
a
k
=
1
2
a
k
−
1
+
1
2
a
k
+
1
a_k = \frac12 a_{k- 1} + \frac12 a_{k+1 }
a
k
=
2
1
a
k
−
1
+
2
1
a
k
+
1
(b) Find the numbers
a
0
,
.
.
.
,
a
100
a_0,. . . , a_{100}
a
0
,
...
,
a
100
, such that
a
0
=
0
,
a
100
=
1
a_0 = 0, a_{100} = 1
a
0
=
0
,
a
100
=
1
and for all
k
=
1
,
.
.
.
,
99
k = 1,. . . , 99
k
=
1
,
...
,
99
:
a
k
=
1
+
1
2
a
k
−
1
+
1
2
a
k
+
1
a_k = 1+\frac12 a_{k- 1} + \frac12 a_{k+1 }
a
k
=
1
+
2
1
a
k
−
1
+
2
1
a
k
+
1
.