forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 21 Σεπ 2017, 17:55

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 12 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 14 Οκτ 2012, 19:23 
Χωρίς σύνδεση

Εγγραφη: 18 Ιαν 2011, 13:54
Δημοσ.: 81
Έστω ένα σύνολο S, με |S|=n και μια οικογένεια υποσυνόλων του {A_1,A_2,..,A_m} . Αν για κάθε δύο διαφορετικά στοιχεία x,y τουS υπάρχει A_i τέτοιο ώστε είτε x\in A_i και y\in \overline A_i είτε y\in A_iκαι x\in \overline A_i . Mπορείτε να βρείτε το ελαχιστο m ;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 14 Οκτ 2012, 23:57 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 22 Μαρ 2007, 22:17
Δημοσ.: 163
Τοποθεσια: Kallithea
Κάτω από ποιες προυποθέσεις π.χ ο ελάχιστος αριθμός θα ήταν m = 3;

Η ιδέα είναι να δημιουργήσουμε τα σύνολα A_1 , A_2, A_3ως εξής:

Παίρνουμε 2n στοιχεία (τα n διαφορετικά στοιχεία του S επί δύο-δηλάδη δύο αντίγραφα κάθε στοιχείου του S). Τοποθετούμε τα 2n στοιχεία ώστε κανένα από τα A_1 , A_2, A_3 να μην περιέχει n
διαφορετικά στοιχεία του S (αφού είναι υποσύνολα του S). Τότε για κάθε x,y \in S ,\exists~A_i τέτοιο ώστε x \in A_i και y \in \bar{A_i} = S \backslash A_i ή αντίστροφα.

Ένας απλός τρόπος κατασκευής των A_1 , A_2, A_3:

s_1 \in A_1\bigcap A_2
s_2 \in A_2\bigcap A_3
s_3 \in A_3\bigcap A_1
s_4 \in A_1\bigcap A_2
κτλ

Για παράδειγμα αν πάρουμε τα s_1 , s_2 \in S τότε s_1 \in A_1 και s_2 \in \bar{A_1} = S 
\backslash A_1 , αφού A_1 = \left\{s_1 , s_3 , s_4 , s_6 \ldots \right\}

Η ιδέα δουλεύει καλά για s_1 , s_2 , s_3 αλλά αποτυγχάνει για τα υπόλοιπα.

Για παράδειγμα αν πάρουμε τα s_1 , s_4 \in S όπως παραπάνω δεν μπορούμε να κάνουμε κάτι αντίστοιχο όπως με τα s_1 , s_2.

Άρα τα ζήτουμενα A_i είναι τελικά περισσότερα από 3 για n > 3. Όμως για n = 6 αρκούν μόνο 4 σύνολα A_1 , A_2 , A_3 , A_4(Οι απλοί συνδυσμοί των 4 ανά 2 μας δίνουν 6). Με την ίδια λογική κατασκευάζονται όπως πριν ως:

s_1 \in A_1\bigcap A_2
s_2 \in A_2\bigcap A_3
s_3 \in A_3\bigcap A_1
s_4 \in A_1\bigcap A_4
s_5 \in A_2\bigcap A_4
s_6 \in A_3\bigcap A_4

Μια επιπλέον παρατήρηση(δεν άλλαζει και πολύ τα πράγματα) είναι ότι το τελευταίο στοιχείο s_n δεν είναι ανάγκη να μπει σε A_i (γιατί;).

Άρα τελικά

\displaystyle  m = \min\left\{x : \left(\begin{array}{c} x \\ 2 \end{array}\right) \geq n-1 \right\}

ή αλλίως (πράξεις)

\displaystyle  m = \min\left\{x : x^2 - x \geq  2(n-1) \right\}

\displaystyle  m = 1 + \left[ \frac{1 + \sqrt{1 + 8(n-1)}}{2} \right]


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 15 Οκτ 2012, 17:31 
Χωρίς σύνδεση

Εγγραφη: 18 Ιαν 2011, 13:54
Δημοσ.: 81
nikolaos έγραψε:
Κάτω από ποιες προυποθέσεις π.χ ο ελάχιστος αριθμός θα ήταν m = 3;

Η ιδέα είναι να δημιουργήσουμε τα σύνολα A_1 , A_2, A_3ως εξής:

Παίρνουμε 2n στοιχεία (τα n διαφορετικά στοιχεία του S επί δύο-δηλάδη δύο αντίγραφα κάθε στοιχείου του S). Τοποθετούμε τα 2n στοιχεία ώστε κανένα από τα A_1 , A_2, A_3 να μην περιέχει n
διαφορετικά στοιχεία του S (αφού είναι υποσύνολα του S). Τότε για κάθε x,y \in S ,\exists~A_i τέτοιο ώστε x \in A_i και y \in \bar{A_i} = S \backslash A_i ή αντίστροφα.

Ένας απλός τρόπος κατασκευής των A_1 , A_2, A_3:

s_1 \in A_1\bigcap A_2
s_2 \in A_2\bigcap A_3
s_3 \in A_3\bigcap A_1
s_4 \in A_1\bigcap A_2
κτλ

Για παράδειγμα αν πάρουμε τα s_1 , s_2 \in S τότε s_1 \in A_1 και s_2 \in \bar{A_1} = S 
\backslash A_1 , αφού A_1 = \left\{s_1 , s_3 , s_4 , s_6 \ldots \right\}

Η ιδέα δουλεύει καλά για s_1 , s_2 , s_3 αλλά αποτυγχάνει για τα υπόλοιπα.

Για παράδειγμα αν πάρουμε τα s_1 , s_4 \in S όπως παραπάνω δεν μπορούμε να κάνουμε κάτι αντίστοιχο όπως με τα s_1 , s_2.

Άρα τα ζήτουμενα A_i είναι τελικά περισσότερα από 3 για n > 3. Όμως για n = 6 αρκούν μόνο 4 σύνολα A_1 , A_2 , A_3 , A_4(Οι απλοί συνδυσμοί των 4 ανά 2 μας δίνουν 6). Με την ίδια λογική κατασκευάζονται όπως πριν ως:

s_1 \in A_1\bigcap A_2
s_2 \in A_2\bigcap A_3
s_3 \in A_3\bigcap A_1
s_4 \in A_1\bigcap A_4
s_5 \in A_2\bigcap A_4
s_6 \in A_3\bigcap A_4

Μια επιπλέον παρατήρηση(δεν άλλαζει και πολύ τα πράγματα) είναι ότι το τελευταίο στοιχείο s_n δεν είναι ανάγκη να μπει σε A_i (γιατί;).

Άρα τελικά

\displaystyle  m = \min\left\{x : \left(\begin{array}{c} x \\ 2 \end{array}\right) \geq n-1 \right\}

ή αλλίως (πράξεις)

\displaystyle  m = \min\left\{x : x^2 - x \geq  2(n-1) \right\}

\displaystyle  m = 1 + \left[ \frac{1 + \sqrt{1 + 8(n-1)}}{2} \right]


γεια σου :).ωραια προσπαθεια, αλλα εχεις θεμελιωδες λαθος στην αρχη της σκεψης σου. Οι εννοιες x\in A_i και y\in \overline A_i , y\in A_iκαι x\in \overline A_i δεν ειναι αντιστροφες.

συνεπως χτιζεις με λαθος θεμελια.

για να σε πεισω.Αν n=7 και εστω S=\left\{1,2,...,7\right\} (απλα διακεκριμενα στοιχεια!) τοτε απο τον τυπο σου με την ριζα, εχουμε οτι το ελαχιστο m ειναι 5.
Ομως η οικογενεια με συνολα \left\{1,2,5\right\} ,\left\{1,3,4,6\right\} ,\left\{4,5,7\right\} ,\left\{6\right\} πληρουν τις προυποθεσεις και ειναι 4 το πληθος.

σε συμβουλευω να μην σκεφτεσαι πολυπλοκα. Δεν λεω οτι η λυση ειναι ευκολη αλλα συνηθως ειναι η πιο θεμελιωδης


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 15 Οκτ 2012, 17:42 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 22 Μαρ 2007, 22:17
Δημοσ.: 163
Τοποθεσια: Kallithea
Γεια επίσης! Το 'ή αντίστροφα' που έγραψα ίσως δεν ήταν η κατάλληλη λέξη αλλά εννοώ αυτό που έγραψες...

Ναι στον τύπο το 1 + []το έγραψα γιατί σκέφτηκα ότι θέλουμε το πάνω ακέραιο μέρος αν η ρίζα μας βγει μη ακέραιος.

Στο παράδειγμα που έθεσες βγαίνει ακέραιος όμως χωρίς να πάρουμε ακέραιο μέρος . Άρα το +1 μάλλον δεν χρειάζεται στον τύπο όταν
\displaystyle \frac{1 + \sqrt{1 + 8(n-1)}}{2} είναι ακέραιος .
Τι λες;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 15 Οκτ 2012, 18:10 
Χωρίς σύνδεση

Εγγραφη: 18 Ιαν 2011, 13:54
Δημοσ.: 81
nikolaos έγραψε:
Γεια επίσης! Το 'ή αντίστροφα' που έγραψα ίσως δεν ήταν η κατάλληλη λέξη αλλά εννοώ αυτό που έγραψες...

Ναι στον τύπο το 1 + []το έγραψα γιατί σκέφτηκα ότι θέλουμε το πάνω ακέραιο μέρος αν η ρίζα μας βγει μη ακέραιος.

Στο παράδειγμα που έθεσες βγαίνει ακέραιος όμως χωρίς να πάρουμε ακέραιο μέρος . Άρα το +1 μάλλον δεν χρειάζεται στον τύπο όταν
\displaystyle \frac{1 + \sqrt{1 + 8(n-1)}}{2} είναι ακέραιος .
Τι λες;


αυτο που λες πρεπει να βασιζεται σε καποια λογικη,δεν βγαζω ή βαζω στοιχεια απλως για να βγαλω το επιθυμητο το επιθυμητο αποτελεσμα. εαν θες δοκιμασε για n=9 εχω οτι το ελαχιστο m ειναι 5(δοκιμασε να βρεις συνολα που θα πληρουν τις ιδιοτητες).για μεγαλο αριθμο π.χ το 100 το
ελαχιστο ειναι 51 εννοω με το δικο σου βγαινει 397

εχει διαφορα!


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 15 Οκτ 2012, 18:21 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 22 Μαρ 2007, 22:17
Δημοσ.: 163
Τοποθεσια: Kallithea
metalman έγραψε:
nikolaos έγραψε:
Γεια επίσης! Το 'ή αντίστροφα' που έγραψα ίσως δεν ήταν η κατάλληλη λέξη αλλά εννοώ αυτό που έγραψες...

Ναι στον τύπο το 1 + []το έγραψα γιατί σκέφτηκα ότι θέλουμε το πάνω ακέραιο μέρος αν η ρίζα μας βγει μη ακέραιος.

Στο παράδειγμα που έθεσες βγαίνει ακέραιος όμως χωρίς να πάρουμε ακέραιο μέρος . Άρα το +1 μάλλον δεν χρειάζεται στον τύπο όταν
\displaystyle \frac{1 + \sqrt{1 + 8(n-1)}}{2} είναι ακέραιος .
Τι λες;


αυτο που λες πρεπει να βασιζεται σε καποια λογικη,δεν βγαζω ή βαζω στοιχεια απλως για να βγαλω το επιθυμητο το επιθυμητο αποτελεσμα. εαν θες δοκιμασε για n=9 εχω οτι το ελαχιστο m ειναι 5(δοκιμασε να βρεις συνολα που θα πληρουν τις ιδιοτητες).για μεγαλο αριθμο π.χ το 100 το
ελαχιστο ειναι 51 εννοω με το δικο σου βγαινει 397

εχει διαφορα!


Για n = 9

βγάζω 1 + \left[ \frac{1 + \sqrt{67}}{2} \right] = 1 + [4.59] = 1 + 4 = 5

Για n= 100

βγάζει

1 + \left[ \frac{1 + \sqrt{793}}{2} \right] = 1 + [14.58] = 15

Δεν ξέρω πως το έχεις λύσει γιατί δεν έχω παρακολουθήσει διακριτά. Αν διαβάσεις ξανά θα δεις ότι έχω περιγράψει ένα τρόπο κατασκεύης των A_i. Και πάλι ο συμβολισμός με την τομή που χρησιμοποιώ δεν είναι ο καλύτερος.
Εκεί εννοώ ότι βάζουμε π.χ το s_1στο A_1 και το A_2. Δεν βρίσκω κάπου λάθος εκτός από το να βγάλουμε το 1 αν βγει ακέραιος η ποσότητα που σου είπα και όντως έδωσες αντιπάραδειγμα για αυτό.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 15 Οκτ 2012, 18:44 
Χωρίς σύνδεση

Εγγραφη: 18 Ιαν 2011, 13:54
Δημοσ.: 81
nikolaos έγραψε:
metalman έγραψε:
nikolaos έγραψε:
Γεια επίσης! Το 'ή αντίστροφα' που έγραψα ίσως δεν ήταν η κατάλληλη λέξη αλλά εννοώ αυτό που έγραψες...

Ναι στον τύπο το 1 + []το έγραψα γιατί σκέφτηκα ότι θέλουμε το πάνω ακέραιο μέρος αν η ρίζα μας βγει μη ακέραιος.

Στο παράδειγμα που έθεσες βγαίνει ακέραιος όμως χωρίς να πάρουμε ακέραιο μέρος . Άρα το +1 μάλλον δεν χρειάζεται στον τύπο όταν
\displaystyle \frac{1 + \sqrt{1 + 8(n-1)}}{2} είναι ακέραιος .
Τι λες;


αυτο που λες πρεπει να βασιζεται σε καποια λογικη,δεν βγαζω ή βαζω στοιχεια απλως για να βγαλω το επιθυμητο το επιθυμητο αποτελεσμα. εαν θες δοκιμασε για n=9 εχω οτι το ελαχιστο m ειναι 5(δοκιμασε να βρεις συνολα που θα πληρουν τις ιδιοτητες).για μεγαλο αριθμο π.χ το 100 το
ελαχιστο ειναι 51 εννοω με το δικο σου βγαινει 397

εχει διαφορα!


Για n = 9

βγάζω 1 + \left[ \frac{1 + \sqrt{67}}{2} \right] = 1 + [4.59] = 1 + 4 = 5

Για n= 100

βγάζει

1 + \left[ \frac{1 + \sqrt{793}}{2} \right] = 1 + [14.58] = 15



συγγνωμη για το τελευταιο.λαθος μου :P .ξεχασα την ριζα.και παλι με 15 συνολα δεν μπορεις να το κανεις αυτο
15 συνολα ειναι λιγα.θα σου πω γιατι.

ο αλγοριθμος δημιουργιας των εξης συνολων ειναι ο παρακατω:

εχω ενα συνολο με 7 στοιχεια(για απλουστευση).
1)Διαλεγω [7/2] +1 (*θα σου πω γιατι) στοιχεια τυχαια. Εστω τα 1,4,5,6 και αφηνω τα 2,3,7.

2)Φτιαχνω υποσυνολα τετοια ωστε η ενωση των τομων τους ανα δυο να ειναι το συνολο\left\{1,4,5,6\right\} ,δηλαδη το συνολο αυτων που διαλεξα. Το κενο συνολο δεν μας ενδιαφερει

3)Αφου τα εχω φτιαξει, δηλαδη τα \left\{1,5\right\},\left\{1,4,6\right\},\left\{4,5\right\},\left\{6\right\}
βαζω αυτα που εχω αφησει ,δηλαδη το 2,3,7 μεσα σε ενα απο τα παραπανω συνολα.
Με αποδειξη λιγο πιο γενικη(που βαριεμαι να γραψω :P ) βλεπεις οτι ο αλγοριθμος σου δινει το ελαχιστο m.

Ως προς το * ,διαλεγω [n/2] +1 στοιχεια επειδη το [n/2] +1 ειναι ο ελαχιστος αριθμος υποσυνολων ωστε να ισχυει
η 2) σε γενικο πλαισιο.(θελει να κανεις ενα σχηματακι με τα στοιχεια αριστερα και τα συνολα δεξια και να φτιαξεις ενα διμερες γραφημα).

Αρα το ελαχιστο m ειναι το [n/2]+1


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 15 Οκτ 2012, 19:43 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 22 Μαρ 2007, 22:17
Δημοσ.: 163
Τοποθεσια: Kallithea
Το διάβασα στα γρήγορα αλλά δεν μπορώ να σου πω ότι έχω καταλάβει πλήρως το κομμάτι του γιατί αυτό είναι το ελάχιστο.
Αν αυτό είναι σωστό τότε κάπου έχω λάθος στον τρόπο κατασκευής των A_i (αφού βρίσκω μικρότερο ελάχιστο από σένα)

Θα ξαναγράψω μία τον τρόπο κατασκευής τον δικό μου να δεις αν υπάρχει κάπου λάθος...(δεν βρήκα κάτι λάθος)

s_1 \in A_1 \bigcap A_2
s_2 \in A_2 \bigcap A_3
s_3 \in A_3 \bigcap A_1
s_4 \in A_1 \bigcap A_4
s_5 \in A_2 \bigcap A_4
s_6 \in A_3 \bigcap A_4

κτλ

αυτό που κάνω είναι να προσθέτω στα σύνολα κάθε συνδυσμού (A_i , A_j) ένα s_k.

Το τελευταίο s_n αν κανουμε τη διαδικασία με σειρά δεικτών δεν χρειάζεται αντιστόιχιση και θα εξηγήσω γιατί *.

To σύνολο των στοιχείων (έχει μπει κάθε στοιχείο του S σε δύο μόνο υποσύνολα και τα τελεύταια το αφήσαμε εκτός διαδικασίας) τους αν τα μετρήσεις είναι 2(n-1) (δες τρόπο κατασκευής).


x είναι ότι ο αριθμός των υποσυνολών που μπορούν να ικανοποιήσουν την υποθεση τότε από τον τρόπο κατασκευής παίρνουμε \left( \begin{array}{c} x \\ 2 \end{array} \right) τους συνδυασμούς ανα δύο των συνόλων αφού έχουμε 1-1 αντιστοιχία στοιχείων του S με κάθε συνδυασμό των υποσυνολών απο τον τρόπο κατασκευής. Αυτός ο αριθμός δεν μπορεί να ξεπερνάει τον n-1. Αυτό γιατί μπορούμε να δημιουργήσουμε n-1 διακριτά μονοσύνολα που λύνουν το πρόβλημα. O ορισμός του ελάχιστου mως

m = \min\left\{x : ~\left( \begin{array}{c} x \\ 2 \end{array} \right) \geq n-1 \right\} προκύπτει φυσικολογικά.

Ο τύπος που έγραψα

\displaystyle m = 1 + \left[ \frac{1 +\sqrt{1 + 8(n-1)}}{2}\right]

είναι άμεσος...με την επιπλέον παρατήρηση οτι κόβουμε τον άσσο αν η ποσότητα

\frac{1 +\sqrt{1 + 8(n-1)}}{2} είναι καθαρός ακέραιος όπως π.x συμβαίνει όταν n = 7 , όπως είπες.

Ακόμα και να έχουμε παραπάνω συνδυασμούς από το n δεν μας πειράζει αφού θα πάρουμε n από αυτούς.
Ένα επιχείρημα που δείχνει ότι όσα και να περισσέψουν πάντα το m θα μείνει αναλλοίωτο είναι ότι:

1) To m είναι καλά ορισμένο.

m = 1 + \left[ \frac{1 +\sqrt{1 + 8(n-1)}}{2}\right]  \leq n

πράγματι

1 + \left[ \frac{1 +\sqrt{1 + 8(n-1)}}{2}\right]  <  n + 1 ~,~\Leftrightarrow~.

\left[ n - \frac{1 +\sqrt{1 + 8(n-1)}}{2}\right ] > 0 ~,~ \Leftrightarrow~.

2n > 1 +\sqrt{1 + 8(n-1)}~,~\Leftrightarrow  (2n - 3)^2 > 1

που ισχύει για n > 2

2) αναλλοίωτο και ελάχιστο (οσοί συνδυσμοί ανά δύο και να περισσέψουν)
επίσης ισχύει ότι \left( \begin{array}{c} m \\ 2 \end{array} \right) -  \left( \begin{array}{c} m-1 \\ 2 \end{array}\right) = m-1 \leq n -1~,~\Rightarrow.

(n-1) \leq \left( \begin{array}{c} m \\ 2 \end{array} \right) =   \left( \begin{array}{c} m-1 \\ 2 \end{array}\right) + m-1 < (n-1) + (m-1)~,~\Leftrightarrow.

0 \leq \left( \begin{array}{c} m \\ 2 \end{array} \right) - (n-1) < m-1 \leq n -1

Δηλαδή δεν μπορούν να περισσέψουν πάνω από n-1 συνδυσμοί ώστε να χάσουμε ένα σύνολο.



Το κομμάτι που θέλει έλεγχο είναι αν τα σύνολα που έχω δημιουργήσει ικανοποιούν την υπόθεση.



Θα γράψω μια απόδειξη.



Έστω s_i , s_j ~,~i \neq j

Περίπτωση (1)

s_i \in A_k \bigcap A_{\ell} και s_j \in A_p \bigcap A_q

με k , \ell , p , q διαφορετκά ανά δύο.

Τότε ισχύει ότι s_i \in  A_k~,~s_j \in \bar{A_k} =S \backslash A_k



Περίπτωση (2)

s_i \in A_k \bigcap A_{\ell} και s_j \in A_p \bigcap A_{\ell}

με k , \ell , p διαφορετκά ανά δύο.

Τότε πάλι ισχύει ότι s_i \in  A_k ~,~ s_j \in \bar{A_k} =S \backslash A_k

*Το κομμάτι που είπα ότι θα εξηγήσω μπορεί να γίνει καλύτερα κατανοητό στην περίπτωση των μονοσυνόλων. Π.χ δεν χρειαζόμαστε n διακριτά μονοσύνολα. Αν δημιουργήσουμε n-1 και ένα στοιχείο μέινει χωρίς να μπει κάπου (έστω το s_n ) τότε θα έχουμε για παράδειγμα:

s_1 \in A_1 και s_n \in \bar{A_1} = S \backslash A_1 = \left\{s_2,s_3 , \ldots , s_n \right\}


Τελευταία επεξεργασία απο nikolaos την 16 Οκτ 2012, 00:13, επεξεργάστηκε 1 φορές συνολικά.

Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 15 Οκτ 2012, 23:55 
Χωρίς σύνδεση

Εγγραφη: 18 Ιαν 2011, 13:54
Δημοσ.: 81
nikolaos έγραψε:
Το διάβασα στα γρήγορα αλλά δεν μπορώ να σου πω ότι έχω καταλάβει πλήρως το κομμάτι του γιατί αυτό είναι το ελάχιστο.
Αν αυτό είναι σωστό τότε κάπου έχω λάθος στον τρόπο κατασκευής των A_i (αφού βρίσκω μικρότερο ελάχιστο από σένα)

Θα ξαναγράψω μία τον τρόπο κατασκευής τον δικό μου να δεις αν υπάρχει κάπου λάθος...(δεν βρήκα κάτι λάθος)

s_1 \in A_1 \bigcap A_2
s_2 \in A_2 \bigcap A_3
s_3 \in A_3 \bigcap A_1
s_4 \in A_1 \bigcap A_4
s_5 \in A_2 \bigcap A_4
s_6 \in A_3 \bigcap A_4

κτλ

αυτό που κάνω είναι να προσθέτω στα σύνολα κάθε συνδυσμού (A_i , A_j) ένα s_k.

Το τελευταίο s_n αν κανουμε τη διαδικασία με σειρά δεικτών δεν χρειάζεται αντιστόιχιση και θα εξηγήσω γιατί *.

To σύνολο των στοιχείων (έχει μπει κάθε στοιχείο του S σε δύο μόνο υποσύνολα και τα τελεύταια το αφήσαμε εκτός διαδικασίας) τους αν τα μετρήσεις είναι 2(n-1) (δες τρόπο κατασκευής).


x είναι ότι ο αριθμός των υποσυνολών που μπορούν να ικανοποιήσουν την υποθεση τότε από τον τρόπο κατασκευής παίρνουμε \left( \begin{array}{c} x \\ 2 \end{array} \right) τους συνδυασμούς ανα δύο των συνόλων αφού έχουμε 1-1 αντιστοιχία στοιχείων του S με κάθε συνδυασμό των υποσυνολών απο τον τρόπο κατασκευής. Αυτός ο αριθμός δεν μπορεί να ξεπερνάει τον n-1. Αυτό γιατί μπορούμε να δημιουργήσουμε n-1 διακριτά μονοσύνολα που λύνουν το πρόβλημα. O ορισμός του ελάχιστου mως

m = \min\left\{x : ~\left( \begin{array}{c} x \\ 2 \end{array} \right) \geq n-1 \right\} προκύπτει φυσικολογικά.

Ο τύπος που έγραψα

\displaystyle m = 1 + \left[ \frac{1 +\sqrt{1 + 8(n-1)}}{2}\right]

είναι άμεσος...με την επιπλέον παρατήρηση οτι κόβουμε τον άσσο αν η ποσότητα

\frac{1 +\sqrt{1 + 8(n-1)}}{2} είναι καθαρός ακέραιος όπως π.x συμβαίνει όταν n = 7 , όπως είπες.

Ακόμα και να έχουμε παραπάνω συνδυασμούς από το n δεν μας πειράζει αφού θα πάρουμε n από αυτούς.
Ένα επιχείρημα που δείχνει ότι όσα και να περισσέψουν πάντα το m θα μείνει αναλλοίωτο είναι ότι:

m = 1 + \left[ \frac{1 +\sqrt{1 + 8(n-1)}}{2}\right]  \leq n

πράγματι

1 + \left[ \frac{1 +\sqrt{1 + 8(n-1)}}{2}\right]  <  n + 1 ~,~\Leftrightarrow~.

\left[ n - \frac{1 +\sqrt{1 + 8(n-1)}}{2}\right ] > 0 ~,~ \Leftrightarrow~.

2n > 1 +\sqrt{1 + 8(n-1)}~,~\Leftrightarrow  (2n - 3)^2 > 1

που ισχύει για n > 2


Άρα n-1 \leq \left( \begin{array}{c} m \\ 2 \end{array} \right) \leq  \left( \begin{array}{c} n \\ 2 \end{array} \right)

και ισχύει ότι \left( \begin{array}{c} m \\ 2 \end{array} \right) -  \left( \begin{array}{c} m-1 \\ 2 \end{array}\right) = m-1 \leq n -1~,~\Leftrightarrow.

(n-1) \leq \left( \begin{array}{c} m \\ 2 \end{array} \right) =   \left( \begin{array}{c} m-1 \\ 2 \end{array}\right) + m-1 < (n-1) + (m-1)~,~\Leftrightarrow.

0 \leq \left( \begin{array}{c} m \\ 2 \end{array} \right) - (n-1) < m-1 \leq n -1

Δηλαδή δεν μπορούν να περισσέψουν πάνω από n-1 συνδυσμοί ώστε να χάσουμε ένα σύνολο.



Το κομμάτι που θέλει έλεγχο είναι αν τα σύνολα που έχω δημιουργήσει ικανοποιούν την υπόθεση.



Θα γράψω μια απόδειξη.



Έστω s_i , s_j ~,~i \neq j

Περίπτωση (1)

s_i \in A_k \bigcap A_{\ell} και s_j \in A_p \bigcap A_q

με k , \ell , p , q διαφορετκά ανά δύο.

Τότε ισχύει ότι s_i \in  A_k~,~s_j \in \bar{A_k} =S \backslash A_k



Περίπτωση (2)

s_i \in A_k \bigcap A_{\ell} και s_j \in A_p \bigcap A_{\ell}

με k , \ell , p διαφορετκά ανά δύο.

Τότε πάλι ισχύει ότι s_i \in  A_k ~,~ s_j \in \bar{A_k} =S \backslash A_k

*Το κομμάτι που είπα ότι θα εξηγήσω γιατί μπορεί να γίνει καλύτερα κατανοητό στην περίπτωση των μονοσυνόλων. Π.χ δεν χρειαζόμαστε n διακριτά μονοσύνολα. Αν δημιουργήσουμε n-1 και ένα στοιχείο μέινει χωρίς να μπει κάπου (έστω το s_n ) τότε θα έχουμε για παράδειγμα:

s_1 \in A_1 και s_n \in \bar{A_1} = S \backslash A_1 = \left\{s_2,s_3 , \ldots , s_n \right\}



λοιπον η πρωτη περιπτωση χρειαζεται \left( \begin{array}{c} n \\ 2 \end{array} \right)^4 τουλαχιστον
υποσυνολα,αρα καηκαμε :P

η δευτερη ειναι εν μερη σωστη,αλλα χρειαζεσαι μονο το A_k ή το A_p.Υπαρχει πλεονασμος.

Ομως η τελευται παρατηρηση σου ειναι ολοσωστη,και συνεπως αλλαζει και το δικο μου αποτελεσμα.

Στο παραδειγμα που εκανα για n=7 μπορω να βγαλω ενα και μονο ενα στοιχειο λογω της τελευταιας γραμμης που γραφεις.Συνεπως,για n περιττο βγαζω το μονοσυνολο μου και εχω ελαχιστο το [n/2] και για n αρτιο τι και αν βγαλω ενα στοιχειο ,τι οχι,εχω ελαχιστο το [n/2]+1 επειδη στην ελαχιστη μορφη δεν εχω μονοσυνολο.

οι παρατηρησεις μου δεν ειναι για τους αρχικους αριθμους αλλα απο αποδειξη.Απλα σκεψου (απλα ομως!) ποσα συνολα χρειαζομαι ωστε να πληρω το βημα 2) στην αποδειξη μου.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 16 Οκτ 2012, 00:09 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 22 Μαρ 2007, 22:17
Δημοσ.: 163
Τοποθεσια: Kallithea
metalman έγραψε:
[quote =''metalman'']


λοιπον η πρωτη περιπτωση χρειαζεται \left( \begin{array}{c} n \\ 2 \end{array} \right)^4 τουλαχιστον
υποσυνολα,αρα καηκαμε :P

η δευτερη ειναι εν μερη σωστη,αλλα χρειαζεσαι μονο το A_k ή το A_p.Υπαρχει πλεονασμος.

Ομως η τελευται παρατηρηση σου ειναι ολοσωστη,και συνεπως αλλαζει και το δικο μου αποτελεσμα.

Στο παραδειγμα που εκανα για n=7 μπορω να βγαλω ενα και μονο ενα στοιχειο λογω της τελευταιας γραμμης που γραφεις.Συνεπως,για n περιττο βγαζω το μονοσυνολο μου και εχω ελαχιστο το [n/2] και για n αρτιο τι και αν βγαλω ενα στοιχειο ,τι οχι,εχω ελαχιστο το [n/2]+1 επειδη στην ελαχιστη μορφη δεν εχω μονοσυνολο.

οι παρατηρησεις μου δεν ειναι για τους αρχικους αριθμους αλλα απο αποδειξη.Απλα σκεψου (απλα ομως!) ποσα συνολα χρειαζομαι ωστε να πληρω το βημα 2) στην αποδειξη μου.


Κάτι δεν κατάλαβες σε αυτό που γράφω :) . Στην πρώτη περίπτωση δεν θέλουμε\left( \begin{array}{c} n \\ 2 \end{array} \right)^4 υποσύνολα. Εκεί εξετάζω αν τα υποσύνολα που όρισα ικανοποιούν την υπόθεσή σου (στις δύο δυνατές περιπτώσεις για πληρότητα). Ο αριθμός m των υποσυνόλων είναι αυτός που έγραψα στον τύπο δεν αλλάζει. Δες πως τα έχω ορίσει αυτό είναι το βασικό. Δε λεώ πως είναι απαραίτητα σωστό αλλά κάτι έχεις καταλάβει λάθος στην σκέψη μου...σου είχα στείλει νωρίτερα και ένα pm[/quote]


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 16 Οκτ 2012, 00:12 
Χωρίς σύνδεση

Εγγραφη: 18 Ιαν 2011, 13:54
Δημοσ.: 81
nikolaos έγραψε:
metalman έγραψε:
[quote =''metalman'']


λοιπον η πρωτη περιπτωση χρειαζεται \left( \begin{array}{c} n \\ 2 \end{array} \right)^4 τουλαχιστον
υποσυνολα,αρα καηκαμε :P

η δευτερη ειναι εν μερη σωστη,αλλα χρειαζεσαι μονο το A_k ή το A_p.Υπαρχει πλεονασμος.

Ομως η τελευται παρατηρηση σου ειναι ολοσωστη,και συνεπως αλλαζει και το δικο μου αποτελεσμα.

Στο παραδειγμα που εκανα για n=7 μπορω να βγαλω ενα και μονο ενα στοιχειο λογω της τελευταιας γραμμης που γραφεις.Συνεπως,για n περιττο βγαζω το μονοσυνολο μου και εχω ελαχιστο το [n/2] και για n αρτιο τι και αν βγαλω ενα στοιχειο ,τι οχι,εχω ελαχιστο το [n/2]+1 επειδη στην ελαχιστη μορφη δεν εχω μονοσυνολο.

οι παρατηρησεις μου δεν ειναι για τους αρχικους αριθμους αλλα απο αποδειξη.Απλα σκεψου (απλα ομως!) ποσα συνολα χρειαζομαι ωστε να πληρω το βημα 2) στην αποδειξη μου.


Κάτι δεν κατάλαβες σε αυτό που γράφω :) . Στην πρώτη περίπτωση δεν θέλουμε\left( \begin{array}{c} n \\ 2 \end{array} \right)^4 υποσύνολα. Εκεί εξετάζω αν τα υποσύνολα που όρισα ικανοποιούν την υπόθεσή σου (στις δύο δυνατές περιπτώσεις για πληρότητα). Ο αριθμός m των υποσυνόλων είναι αυτός που έγραψα στον τύπο δεν αλλάζει. Δες πως τα έχω ορίσει αυτό είναι το βασικό. Δε λεώ πως είναι απαραίτητα σωστό αλλά κάτι έχεις καταλάβει λάθος στην σκέψη μου...σου είχα στείλει νωρίτερα και ένα pm
[/quote]

τεσπα,ας το αφησουμε :P .απλως μην σκεφτεσαι πολυπλοκα.το ειχα και εγω πιο παλια και μετα αρχισα να σκεφτομαι
οσο πιο απλα μπορουσα.δοκιμασε να λυνεις ασκησεις οσο πιο απλα μπορεις.χωρις να χρησιμοποιεις θεωρηματα και προτασεις.δεν το λεω να σε προσβαλλω :)


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: προβλημα διακριτων
ΔημοσίευσηΔημοσιεύτηκε: 16 Οκτ 2012, 00:19 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 22 Μαρ 2007, 22:17
Δημοσ.: 163
Τοποθεσια: Kallithea
Συζήτηση κάνουμε , απλά αισθάνομαι ότι κάτι δεν έχεις καταλάβει στη σκέψη μου(δεν είναι και τόσο πολύπλοκο) είτε είναι σωστή είτε λάθος...Τέσπα αν μπορείς και έχεις χρόνο δίαβασε τη άλλη μια φορά πρέπει να βγω τώρα έχω κατι να κάνω. Αν απαντήσεις θα το δω αύριο...Ευχαριστώ!


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 12 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

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


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group