Μεσογειακά σύνολα

Συντονιστές: Demetres, silouan

socrates
Επιμελητής
Δημοσιεύσεις: 5778
Εγγραφή: Δευ Μαρ 09, 2009 1:47 pm
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

Μεσογειακά σύνολα

#1

Μη αναγνωσμένη δημοσίευση από socrates » Πέμ Ιουν 15, 2017 3:37 am

Ένα σύνολο S λέγεται βαλεαρικό, αν υπάρχουν a,b\in S, όχι απαραίτητα διαφορετικά, τέτοια ώστε ο αριθμός a+b να είναι δύναμη του 2.
Για ποιες τιμές του n υπάρχει υποσύνολο 99 στοιχείων του \{1,2,...,n\} το οποίο δεν είναι βαλεαρικό, αλλά κάθε υποσύνολο 100 στοιχείων του \{1,2,...,n\} είναι βαλεαρικό;


Θανάσης Κοντογεώργης

Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7852
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Μεσογειακά σύνολα

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιουν 15, 2017 10:31 am

Θα δείξω ότι αυτό ισχύει μόνο για n=203. Αυτό είναι άμεση συνέπεια των Λημμάτων 1-4

Λήμμα 1: Αν n \geqslant 204 τότε το \{1,2,\ldots,n\} έχει ένα υποσύνολο 100 στοιχείων που δεν είναι βαλεαρικό.

Απόδειξη: Μπορούμε να πάρουμε το A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup B όπου:

\displaystyle{A_1 = \{3\}, A_2 = \{6,7\}, A_3 = \{11,12,14,15\}, A_4 = \{19,22,23,24,27,28,30,31\},}

A_5 =\{35,38,39,43,44,46,47,48,51\} και B = \{129,\ldots,204\}.

Οι αριθμοί κάθε A_n ανήκουν στο διάστημα (2^n,2^{n+1}) και άρα το άθροισμα κάθε δύο αριθμών του A_n ανήκει στο διάστημα (2^{n+1},2^{n+2}) οπότε δεν είναι δύναμη του 2. Με παρόμοιο τρόπο βλέπουμε ότι το άθροισμα ενός αριθμού από το B και οποιουδήποτε άλλου αριθμού είναι μεγαλύτερο του 128 και μικρότερο του 204+51 = 255 άρα δεν είναι δύναμη του 2. Τέλος κάθε A_{n+1} επιλέχθηκε ώστε τα στοιχεία του να είναι μεγαλύτερα του 2^{n+1}, μικρότερα του 2^{n+1} αλλά το άθροισμά τους με οποιοδήποτε άλλο στοιχείο των A_1,\ldots,A_n να μην ισούται με 2^{n+2} και άρα να μην είναι δύναμη του 2.

Συνολικά έχουμε 1+2+4+8+9+76=100 στοιχεία με το σύνολο να μην είναι βαλεαρικό.

Λήμμα 2: Το \{1,2,\ldots,203\} έχει ένα υποσύνολο 99 στοιχείων που δεν είναι βαλεαρικό.

Απόδειξη: Απλά αφαιρούμε το 203 από το υποσύνολο της απόδειξης του λήμματος 1.


Λήμμα 3: Κάθε υποσύνολο 100 στοιχείων του \{1,2,\ldots,203\} είναι βαλεαρικό.

Απόδειξη: Διαμερίζουμε το σύνολο στα εξής υποσύνολα:
\{53,203\},\{54,202\}\ldots,\{127,129\},\{128\}
\{12,52\},\{13,51\}\ldots,\{31,33\},\{16\}
\{5,11\},\{6,10\},\{7,9\},\{8\}
\{1,3\}
\{2\},\{4\}.

Συνολικά καταγράψαμε 5 μονοσύνολα και 99 δισύνολα. Κάθε μη βαλεαρικό σύνολο περιέχει μόνο ένα στοιχείο από κάθε δισύνολο αφού το άθροισμα των δύο στοιχείων είναι δύναμη του 2. Επίσης δεν μπορεί να περιέχει κανένα στοιχείο μονοσυνόλου επειδή το άθροισμα με τον εαυτό του είναι δύναμη του 2.

Λήμμα 4: Κάθε υποσύνολο 99 στοιχείων του \{1,2,\ldots,202\} είναι βαλεαρικό.

Απόδειξη: Διαμερίζουμε το σύνολο στα εξής υποσύνολα:
\{54,202\}\ldots,\{127,129\},\{128\}
\{11,53\},\{12,52\}\ldots,\{31,33\},\{16\}
\{6,10\},\{7,9\},\{8\}
\{3,5\}
\{1\},\{2\},\{4\}.

Συνολικά καταγράψαμε 6 μονοσύνολα και 98 δισύνολα. Κάθε μη βαλεαρικό σύνολο περιέχει μόνο ένα στοιχείο από κάθε δισύνολο αφού το άθροισμα των δύο στοιχείων είναι δύναμη του 2. Επίσης δεν μπορεί να περιέχει κανένα στοιχείο μονοσυνόλου επειδή το άθροισμα με τον εαυτό του είναι δύναμη του 2.


Απάντηση

Επιστροφή σε “Συνδυαστική - Επίπεδο Αρχιμήδη (Seniors)”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης