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

Μαΐου 7, 2009

Μονά-ζυγά

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 10:10 μμ

Το παρακάτω πρόβλημα προτάθηκε από το Δημήτρη Χριστοφίδη:

Να βρεθεί το μέγιστο n ώστε να υπάρχουν σύνολα A_1,\ldots,A_n \subseteq \{1,2,\ldots,2009\} τέτοια ώστε

  • το κάθε ένα από αυτά να έχει περιττό μέγεθος, και
  • η τομή οποιωνδήποτε δύο διαφορετικών από αυτά να έχει άρτιο μέγεθος.
Advertisements

3 Σχόλια »

  1. Υπόδειξη:

    Γισ κάθε ένα από τα σύνολα A_j θεωρείστε το διάνυσμα x_j \in {\mathbb F}_2^{2009} που έχει x_{ji}=1 \leftrightarrow i \in A_j. (Εδώ {\mathbb F_2}=\{0,1\} είναι το σώμα των υπολοίπων mod 2.)

    Μεταφράστε τις συνθήκες για τα σύνολα A_j στη γλώσσα γραμμικής άλγεβρας για τα διανύσματα x_j και δείξτε ότι το πλήθος των x_j είναι το πολύ 2009.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 8, 2009 @ 11:01 πμ

  2. Νομίζω πως το 2009 δεν έχει κάτι μαγικό και μπορεί να αντικατασταθεί με m .

    Έστω M το μέγιστο πλήθος συνόλων που ικανοποιεί τις υποθέσεις,
    έστω \mathcal{F} η εν λόγω οικογένεια των συνόλων.
    Επιλέγοντας \mathcal{F} = \{ \{1\}, \{2\}, \ldots , \{m\} \} έχουμε ότι M \geq m .
    H υπόθεση μας δίδει πως τα διανύσματα x_j \in \mathbb{F}_{2}^{m} είναι ορθογώνια
    καθώς x_j \cdot x_k = |A_j \cap A_k| = 0 (\text{mod} 2) και x_j \cdot x_j = 1 (\text{mod} 1) .
    Επίσης τα x_j είναι γραμμικώς ανεξάρτητα. Αυτό ισχύει διότι αν
    \sum_{A_j \in \mathcal{F}} a_j x_j = 0 τότε θα ισχύει και
    \langle x_k , \sum_{A_j \in \mathcal{F}} a_j x_j \rangle = 0 και άρα a_k = 0 .
    Οπότε M \leq \text{dim}(\mathbb{F}_{2}^{m}) = m .

    Μου αρέσει!

    Σχόλιο από henk&christos — Ιανουαρίου 24, 2011 @ 10:27 μμ

  3. Πολύ σωστά.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιανουαρίου 24, 2011 @ 10:31 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: