Προβλήματα Μαθηματικών

4 Μαΐου, 2008

Ταιριάσματα

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 10:25 μμ

Ας είναι A, B \subseteq {\mathbb R}^2 δύο υποσύνολα του επιπέδου. Θα θέλαμε να βρούμε μια 1-1 και επί αντιστοιχία f:A \to B τέτοια ώστε, για κάποια σταθερά C<\infty να ισχύει

|a - f(a)| \le C,

για κάθε a \in A (|x-y| παριστάνει την απόσταση ανάμεσα στα σημεία x,y).

Ας υποθέσουμε ότι υπάρχει μια 1-1 συνάρτηση g:A \to B και μια 1-1 συνάρτηση h:B \to A, τέτοιες ώστε να ισχύει

|a - g(a)| \le C,\ \ |b - h(b)| \le C,\ \ \ \forall a \in A, b \in B.

Δείξτε ότι υπάρχει μια f με τις ιδιότητες που επιζητούμε παραπάνω.

Ομαδικός Γάμος

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 6:14 μμ

Έχουμε ένα σύνολο A από n άνδρες κι ένα σύνολο \Gamma από n γυναίκες. Κάθε άνδρας αποδέχεται ως σύζυγό του ακριβώς r από τις γυναίκες και κάθε γυναίκα αποδέχεται ως σύζυγό της ακριβώς r από τους άνδρες (r\ge 1 είναι ο ίδιος αριθμός για κάθε άτομο). Τα σύνολα των αποδεκτών συζύγων για κάθε άτομο είναι κατά τα άλλα τυχαία.

Θεωρούμε ότι κάθε αποδοχή είναι αμοιβαία: όταν λέμε ότι ο Χ αποδέχεται την Υ ως σύζυγό του θεωρούμε ότι και η Υ δέχεται τον Χ ως σύζυγό της (έχουν «μιλήσει» πριν).

Δείξτε ότι υπάρχει μια 1-1 και επί απεικόνιση

w:A\to \Gamma,

τέτοια ώστε για κάθε x \in A η γυναίκα w(x) είναι μια αποδεκτή σύζυγος για τον x και ο x είναι ένας αποδεκτός σύζυγος για την w(x).

Υπολογίστε το άθροισμα

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 5:46 μμ

Βρείτε ένα τύπο για το άθροισμα

\displaystyle \sum_{3 | k} {n \choose k}.

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.