Kezdőlap


Feladat:	B.4869	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	2018/január, 24 - 25. oldal		PDF \| MathML
Témakör(ök):	Feladat, Számhalmazok, Konstruktív megoldási módszer
Hivatkozás(ok):	Feladatok: 2017/április: B.4869

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az állítást úgy bizonyítjuk, hogy párokba soroljuk az $A$ parkettázásait. A következő jelölést használjuk: ha $X$ és $Y$ számhalmazok, akkor legyen

\begin{matrix} X + Y = {x + y ∣ x \in X és y \in Y} . \end{matrix}

Nyilván

X + Y = Y + X

, és az

X

halmaz

s

-sel való eltoltja ekkor

X + {s}

.
Legyen

\begin{matrix} A = (B + {c_{1}}) \cup (B + {c_{2}}) \cup (B + {c_{3}}) \cup ... \cup (B + {c_{k}}) \end{matrix}

A

halmaz parkettázása. Ekkor

A = B + C

, ahol

C = {c_{1}, c_{2}, c_{3}, ..., c_{k}}

; legyen továbbá

B = {b_{1}, b_{2}, ..., b_{n}}

. Így

\begin{matrix} A = C + B = (C + {b_{1}}) \cup (C + {b_{2}}) \cup (C + {b_{3}}) \cup ... \cup (C + {b_{n}}) . \end{matrix}

Megmutatjuk, hogy ez is parkettázása

A

-nak, és különbözik az előbbitől.
A

(C + {b_{i}})

halmazok egymás eltoltjai, közös elemszámuk

k

, ami az első parkettázásban szereplő részhalmazok számaként legalább kettő. E halmazok száma,

n

pedig az első parkettázásban szereplő halmazok közös elemszáma, így szintén legalább kettő. A diszjunktság igazolásához indirekten tegyük fel, hogy például

(C + {b_{1}})

-nek és

(C + {b_{2}})

-nek közös eleme

c_{i} + b_{1} = c_{j} + b_{2}

. Ekkor azonban ez a szám

(B + c_{i})

-nek és

(B + c_{j})

-nek is közös eleme; mivel e két halmaz az első parkettázásban szerepel, ez csak úgy lehetséges, hogy

(B + c_{i}) = (B + c_{j})

, azaz

i = j

, így

c_{i} = c_{j}

, akkor viszont

b_{1} = b_{2}

, ami ellentmondás. Nyilvánvaló, hogy miképpen e második parkettázást kaptuk az elsőből, ugyanazzal a megfeleltetéssel a másodikból visszakapjuk az elsőt.
Ahhoz, hogy a parkettázások párosításáról beszélhessünk, végül be kell látnunk, hogy a párban álló parkettázások különböznek egymástól. Tegyük fel ennek az ellenkezőjét; ekkor

n = k

, és a

B

elemeinek átszámozásával elérhető, hogy

(B + c_{v}) = (C + b_{v})

teljesül

v = 1,2, ..., n

-re. Tekintsük például

(B + c_{1}) = (C + b_{1})

-et:

c_{2} + b_{1} \in (C + b_{1})

miatt ekkor van olyan

b_{i}

eleme

B

-nek, amelyre

b_{i} + c_{1} = c_{2} + b_{1}

. Ez a szám viszont közös eleme

(B + c_{1})

-nek és

(B + c_{2})

-nek, ami ellentmondás.