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

Μαΐου 7, 2009

Μονά-ζυγά

Κατηγορίες: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 10:10 μμ

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

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

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

1 σχόλιο »

  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 πμ


Κανάλι RSS για τα σχόλια του άρθρου. TrackBack URI

Γράψτε ένα σχόλιο

Για να σχολιάσετε πρέπει να συνδεθείτε.

Blog στο WordPress.com.