Μη ξένα σύνολα

#1

Δίνεται το σύνολο $K=\{1,2,3,...,2012\},$ και έστω A,B

δύο υποσύνολα του

. Συμβολίζουμε με |A |

και

τον αριθμό των στοιχείων του

και

αντίστοιχα.
Υποθέτουμε ότι $|A |\cdot |B |\geq 4023$ .
Να αποδείξετε ότι τα σύνολα A-A

και

περιέχουν ένα τουλάχιστον κοινό στοιχείο.
Σημειώνουμε ότι το X-X

συμβολίζει το σύνολο $\{k-r: k,r\in X, k\ne r \}$

#2

Κοιτάμε όλα τα ζεύγη (a,b)

με $a\in A$ και $b \in B$ . Υπάρχουν 4023

τέτοια ζεύγη. Επίσης για κάθε ζεύγος (a,b)

έχουμε $a-b \in \{-2011,-2010,\ldots,2011\}$ , δηλαδή η διαφορά μπορεί να πάρει μόνο 4022

τιμές. Επομένως υπάρχουν δυο διαφορετικά ζεύγη (a,b)

και

με

. Τότε $0 \neq a-a' = b-b' \in (A-A)\cap (B-B)$ όπως θέλαμε.

- Το φράγμα δεν βελτιώνεται. Π.χ. αν $A = \{1,2012\}$ και $B = \{2,3,\ldots,2012\}$ τότε |A||B| = 4022

αλλά $(A-A)\cap(B-B) = \emptyset$ .

- Συνήθως στον συμβολισμό X-X

επιτρέπουμε και το

να ανήκει στο σύνολο (για

μη κενό).

Μη ξένα σύνολα

Μη ξένα σύνολα

Re: Μη ξένα σύνολα

Μέλη σε σύνδεση