MathDB
Problems
Contests
International Contests
Austrian-Polish
1990 Austrian-Polish Competition
7
7
Part of
1990 Austrian-Polish Competition
Problems
(1)
sequences of dominoes
Source: Austrian - Polish 1990 APMC
5/7/2020
D
n
D_n
D
n
is a set of domino pieces. For each pair of non-negative integers
(
a
,
b
)
(a, b)
(
a
,
b
)
with
a
≤
b
≤
n
a \le b \le n
a
≤
b
≤
n
, there is one domino, denoted
[
a
,
b
]
[a, b]
[
a
,
b
]
or
[
b
,
a
]
[b, a]
[
b
,
a
]
in
D
n
D_n
D
n
. A ring is a sequence of dominoes
[
a
1
,
b
1
]
,
[
a
2
,
b
2
]
,
.
.
.
,
[
a
k
,
b
k
]
[a_1, b_1], [a_2, b_2], ... , [a_k, b_k]
[
a
1
,
b
1
]
,
[
a
2
,
b
2
]
,
...
,
[
a
k
,
b
k
]
such that
b
1
=
a
2
,
b
2
=
a
3
,
.
.
.
,
b
k
−
1
=
a
k
b_1 = a_2, b_2 = a_3, ... , b_{k-1} = a_k
b
1
=
a
2
,
b
2
=
a
3
,
...
,
b
k
−
1
=
a
k
and
b
k
=
a
1
b_k = a_1
b
k
=
a
1
. Show that if
n
n
n
is even there is a ring which uses all the pieces. Show that for n odd, at least
(
n
+
1
)
/
2
(n+1)/2
(
n
+
1
)
/2
pieces are not used in any ring. For
n
n
n
odd, how many different sets of
(
n
+
1
)
/
2
(n+1)/2
(
n
+
1
)
/2
are there, such that the pieces not in the set can form a ring?
combinatorics