MathDB
Problems
Contests
International Contests
Austrian-Polish
1978 Austrian-Polish Competition
7
7
Part of
1978 Austrian-Polish Competition
Problems
(1)
Existence of domino tiling
Source: Austrian-Polish 1978, Problem 7
7/5/2015
Let
M
M
M
be the set of all lattice points in the plane (i.e. points with integer coordinates, in a fixed Cartesian coordinate system). For any point
P
=
(
x
,
y
)
∈
M
P=(x,y)\in M
P
=
(
x
,
y
)
∈
M
we call the points
(
x
−
1
,
y
)
(x-1,y)
(
x
−
1
,
y
)
,
(
x
+
1
,
y
)
(x+1,y)
(
x
+
1
,
y
)
,
(
x
,
y
−
1
)
(x,y-1)
(
x
,
y
−
1
)
,
(
x
,
y
+
1
)
(x,y+1)
(
x
,
y
+
1
)
neighbors of
P
P
P
. Let
S
S
S
be a finite subset of
M
M
M
. A one-to-one mapping
f
f
f
of
S
S
S
onto
S
S
S
is called perfect if
f
(
P
)
f(P)
f
(
P
)
is a neighbor of
P
P
P
, for any
P
∈
S
P\in S
P
∈
S
. Prove that if such a mapping exists, then there exists also a perfect mapping
g
:
S
→
S
g:S\to S
g
:
S
→
S
with the additional property
g
(
g
(
P
)
)
=
P
g(g(P))=P
g
(
g
(
P
))
=
P
for
P
∈
S
P\in S
P
∈
S
.
combinatorics