Μεσογειάδα 2006

Συντονιστές: cretanman, Demetres, polysot, achilleas, socrates, silouan

nickthegreek
Δημοσιεύσεις: 401
Εγγραφή: Δευ Μαρ 01, 2010 2:07 pm
Τοποθεσία: Oxford

Μεσογειάδα 2006

#1

Μη αναγνωσμένη δημοσίευση από nickthegreek » Κυρ Νοέμ 07, 2010 2:58 pm

Το παρακάτω πρόβλημα ήταν το τέταρτο πρόβλημα του Μεσογειακού μαθηματικού διαγωνισμού 2006 και θεωρείται εξαιρετικά δύσκολη ανισότητα.Προσωπικά ούτε μπορώ να καταλάβω την εκφώνηση,και δεν με πειράζει να το παραδεχτώ.Ελπίζω κάποιος να μου εξηγήσει τι σημαίνουν τα διπλά αυτά γινόμενα.Το δίνω στο mathematica διότι έχει μια καταπληκτική λύση,την οποία έχει βρει ένας φίλος μου από τη Δράμα και σπουδαίος δάσκαλος,που αυτή την στιγμή βρίσκεται στο Harvard.Ιδού το πρόβλημα:

Έστω m,n θετικοί ακέραιοι και έστω:

x_{i,j}\in [0,1] για i=1,2,...,m και j=1,2,...,n

Να αποδείξετε ότι:

\prod_{j=1}^{n}(1-\prod_{i=1}^{m}{x_{i,j}})+\prod_{i=1}^{m}{(1-\prod_{j=1}^{n}{(1-x_{i,j}}}))\geq 1

Νομίζω πως αυτή η ανισότητα έχει πολλά πράγματα για τα οποία μπορούμε να συζητήσουμε,και για αυτό το λόγο την ανεβάζω.
Περιμένω τις λύσεις σας.

Φιλικά,
Νίκος

Εdit:Διορθώνω την εκφώνηση της άσκησης μετά από την σωστή παρατήρηση του Σιλουανού,τον οποίο και ευχαριστώ
τελευταία επεξεργασία από nickthegreek σε Κυρ Νοέμ 07, 2010 5:56 pm, έχει επεξεργασθεί 2 φορές συνολικά.


Νίκος Αθανασίου
gtk1994
Δημοσιεύσεις: 92
Εγγραφή: Τετ Απρ 14, 2010 5:04 pm
Τοποθεσία: Ιωάννινα

Re: Μεσογειάδα 2006

#2

Μη αναγνωσμένη δημοσίευση από gtk1994 » Κυρ Νοέμ 07, 2010 3:28 pm

Μπορείς να κοιτάξεις τη λύση αυτού του προβλήματος στο βιβλίο του κυρίου Φελλούρη " Οι Πανελλήνιοι Μαθηματικοί Διαγωνισμοί 1997-2007 " (σελ.313).
Αν προλάβω θα τη γράψω και εδώ σε περίπτωση που δε διαθέτεις το βιβλίο ( δε σου υπόσχομαι και πολλά ,όμως, γιατί διαβάζω και για ένα διαγώνισμα φυσικής :D )


nickthegreek
Δημοσιεύσεις: 401
Εγγραφή: Δευ Μαρ 01, 2010 2:07 pm
Τοποθεσία: Oxford

Re: Μεσογειάδα 2006

#3

Μη αναγνωσμένη δημοσίευση από nickthegreek » Κυρ Νοέμ 07, 2010 3:33 pm

Φίλε μου,

Την λύση την έχω.Αν θέλεις ανεβάζεις τη λύση που έχεις.Πληροφοριακά να πούμε ότι στο βιβλίο του κυρίου Φελλούρη η λύση χρησιμοποιεί διπλή επαγωγή.Υπάρχει και άλλη λύση,που είναι πολύ πιο όμορφη.
Περιμένω τις απόψεις σας.

Φιλικά,
Νίκος


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

Re: Μεσογειάδα 2006

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Νοέμ 07, 2010 4:05 pm

Η δυσκολία του προβλήματος βρίσκεται ακριβώς στην κατανόηση. Άμα κατανοηθεί τι ζητάει η λύση είναι ουσιαστικά δυο γραμμές. Γράφω την ζητούμενη ανισότητα για την περίπτωση n=2,m=3. (Φαντάζομαι ότι το δεδομένο είναι πως x_{i,j} \in \{0,1\})

\displaystyle{(1 - x_{1,1}x_{2,1}x_{3,1})(1 - x_{1,2}x_{2,2}x_{3,2}) + (1 - (1-x_{1,1})(1-x_{1,2}))(1 - (1-x_{2,1})(1-x_{2,2}))(1 - (1-x_{3,1})(1-x_{3,2})) \geqslant 1}


billy_scabilly
Δημοσιεύσεις: 25
Εγγραφή: Πέμ Μάιος 13, 2010 12:26 am

Re: Μεσογειάδα 2006

#5

Μη αναγνωσμένη δημοσίευση από billy_scabilly » Κυρ Νοέμ 07, 2010 4:14 pm

Yποθέτοντας ότι εννοείς ότι τα xi,j ανήκουν στο {0,1} δίνω μια πιθανή λύση(μην φωνάζετε αν έχω κάνει λάθος) :oops: :
Kατασκευάζουμε τον πίνακα Α με εγγραφές τo xi,j στην i,j εγγραφή.Βλέπουμε ότι κάθε ένα από τα δύο γινόμενα στο αριστερό μέλος μπορεί να είναι ή 0 ή 1. Έστω ότι και τα δύο είναι μηδέν.Τότε από το πρώτο γινόμενο έχουμε μια στήλη όλη 1 και από το δεύτερο γινόμενο μια γραμμή όλη 0.Αυτό είναι άτοπο όμως γιατί κάθε γραμμή και στήλη έχουν ένα κοινό στοιχείο. :oops:


nickthegreek
Δημοσιεύσεις: 401
Εγγραφή: Δευ Μαρ 01, 2010 2:07 pm
Τοποθεσία: Oxford

Re: Μεσογειάδα 2006

#6

Μη αναγνωσμένη δημοσίευση από nickthegreek » Κυρ Νοέμ 07, 2010 4:40 pm

Άσχετο:

Ο μεσογειακός μαθηματικός διαγωνισμός σταμάτησε να γίνεται;;;Γιατί δεν μπορώ να βρω θέματα μετά το 2007...

Φιλικά,
Νίκος


Νίκος Αθανασίου
kwstas12345
Δημοσιεύσεις: 1055
Εγγραφή: Δευ Ιαν 11, 2010 2:12 pm

Re: Μεσογειάδα 2006

#7

Μη αναγνωσμένη δημοσίευση από kwstas12345 » Κυρ Νοέμ 07, 2010 4:45 pm

Kαλησπέρα και από μένα!

Νίκο, όχι δεν έχει σταματησει ,τα θέματα δημοσιεύονται στο περιοδικό του ευκλείδη Β ....νομίζω πως τα θέματα μπορείς ενδεχομένως να τα βρείς και από την επίσημη σελίδα της μαθηματικής εταιρείας της Ισπανίας που είναι και διοργανώτρια από όσο ξέρω...

Φιλικά,
Κώστας


nickthegreek
Δημοσιεύσεις: 401
Εγγραφή: Δευ Μαρ 01, 2010 2:07 pm
Τοποθεσία: Oxford

Re: Μεσογειάδα 2006

#8

Μη αναγνωσμένη δημοσίευση από nickthegreek » Κυρ Νοέμ 07, 2010 4:49 pm

Σ'ευχαριστώ Κώστα!!!Παρόλ'αυτά όμως, οι Έλληνες δίνουν πια προκριματικό διαγωνισμό σε επίπεδο εθνικό και δεν συμμετέχουν στον Μεσογειακό Διαγωνισμό.Μήπως κάνω λάθος;;;

Φιλικά,
Νίκος

Υ.Γ.(Σόρι που ρωτάω πράγματα άσχετα με την άσκηση)


Νίκος Αθανασίου
Dimitris X
Δημοσιεύσεις: 243
Εγγραφή: Τρί Ιουν 23, 2009 10:51 pm

Re: Μεσογειάδα 2006

#9

Μη αναγνωσμένη δημοσίευση από Dimitris X » Κυρ Νοέμ 07, 2010 4:59 pm

nickthegreek έγραψε:Σ'ευχαριστώ Κώστα!!!Παρόλ'αυτά όμως, οι Έλληνες δίνουν πια προκριματικό διαγωνισμό σε επίπεδο εθνικό και δεν συμμετέχουν στον Μεσογειακό Διαγωνισμό.Μήπως κάνω λάθος;;;

Φιλικά,
Νίκος

Υ.Γ.(Σόρι που ρωτάω πράγματα άσχετα με την άσκηση)
Η συμμετοχή είναι προαιρετική...Κάτι σαν test ικανοτήτων.... ;)


nickthegreek
Δημοσιεύσεις: 401
Εγγραφή: Δευ Μαρ 01, 2010 2:07 pm
Τοποθεσία: Oxford

Re: Μεσογειάδα 2006

#10

Μη αναγνωσμένη δημοσίευση από nickthegreek » Κυρ Νοέμ 07, 2010 5:24 pm

Αφήνω το θέμα ανοιχτό κι αν δε βρεθεί η ίδια λύση με αυτήν που έχω υπ'όψην μου,θα την ανεβάσω σε μια-δυο μέρες.

Φιλικά


Νίκος Αθανασίου
Άβαταρ μέλους
silouan
Επιμελητής
Δημοσιεύσεις: 1282
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: Μεσογειάδα 2006

#11

Μη αναγνωσμένη δημοσίευση από silouan » Κυρ Νοέμ 07, 2010 5:52 pm

Η εκφώνηση έλεγε ότι x_{ij}\in [0,1] . Τελικά όμως αναγόμαστε στην περίπτωση που γράφτηκε αρχικά το πρόβλημα. Τυχαίο ; :P


Σιλουανός Μπραζιτίκος
achilleas
Γενικός Συντονιστής
Δημοσιεύσεις: 2735
Εγγραφή: Τρί Σεπ 15, 2009 3:32 pm

Re: Μεσογειάδα 2006

#12

Μη αναγνωσμένη δημοσίευση από achilleas » Κυρ Νοέμ 07, 2010 7:31 pm

nickthegreek έγραψε:....
Έστω m,n θετικοί ακέραιοι και έστω:

x_{i,j}\in [0,1] για i=1,2,...,m και j=1,2,...,n

Να αποδείξετε ότι:

\prod_{j=1}^{n}(1-\prod_{i=1}^{m}{x_{i,j}})+\prod_{i=1}^{m}{(1-\prod_{j=1}^{n}{(1-x_{i,j}}}))\geq 1
...
Το πρόβλημα αυτό το βρίσκουμε κι ως πρόβλημα 4.3 στο βιβλίο των P.Biler, Alfred Witkowski, Problems in Mathematical Analysis

Δεν αναφέρει την πηγή του, αλλά έχει την εξής υπόδειξη στη σελίδα 154:

Υπόδειξη: Παρατηρήστε ότι \displaystyle{\cup_j \cap_i A_{ij} \subseteq \cap_i \cup_j A_{ij}}. Δώστε μια πιθανοθεωρητική εξήγηση της ζητούμενης ανισότητας.

Φιλικά,

Αχιλλέας


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

Re: Μεσογειάδα 2006

#13

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Νοέμ 07, 2010 11:31 pm

Θα δώσω μια απάντηση διαφορετική από αυτή που προτείνει ο Αχιλλέας. Πάλι χρησιμοποιεί πιθανότητες (στα κρυφά) αλλά μέσω ενός αρκετά ισχυρού λήμματος που μας απαλλάσσει από το να ψάχνουμε κάθε φορά ποιο σύνολο περιέχεται σε ποιο άλλο σύνολο.

Κατ' αρχήν παρατηρούμε ότι η ανισότητα ισχύει αν x_{i,j} \in \{0,1\} για κάθε i,j. (Έχει ήδη εξηγήσει γιατί ο billy_scabilly)

Αρκεί να αποδείξουμε το ακόλουθο λήμμα

Λήμμα: Έστω P(y_1,\ldots,y_k) ένα πολυώνυμο το οποίο είναι γραμμικό σε κάθε ένα από τα y_i. Αν P(y_1,\ldots,y_k) \geqslant 0 για κάθε y_1,\ldots,y_k \in \{0,1\} τότε P(y_1,\ldots,y_k) \geqslant 0 για κάθε y_1,\ldots,y_k \in [0,1]

Για την απόδειξη του λήμματος ισχυρίζομαι ότι

\displaystyle{P(y_1,\ldots,y_k) = \sum_{A \subseteq \{1,\ldots,k\}} c_A\prod_{i \in A} y_i \prod_{j \notin A}(1-y_j) }

για κάποια c_A \in \mathbb{R}. Για την απόδειξη του ισχυρισμού αρκεί να δείξω ότι κάθε όρος του πολυωνύμου μπορεί να γραφτεί σε αυτήν την μορφή. Χωρίς βλάβη της γενικότητας αρκεί να δείξω ότι ο όρος y_1 \cdots y_{\ell} μπορεί να γραφεί σε αυτήν την μορφή. Όμως

\displaystyle{ y_1 \cdots y_{\ell} = \sum_{\{1,\ldots,\ell\} \subseteq A \subseteq \{1,\ldots,k\}}\prod_{i \in A} y_i \prod_{j \notin A}(1-y_j)}.

Η τελευταία ισότητα μπορεί να αποδειχθεί με επαγωγή στο k - \ell αν και ο πιο εύκολος τρόπος για να δει κάποιος ότι ισχύει είναι με χρήση πιθανοτήτων. (Πώς;)

Έχοντας τώρα στην διάθεσή μας αυτό το λήμμα, η απόδειξη είναι πλέον απλή. Για κάθε A \subseteq \{1,\ldots,k\} παίρνουμε y_i = \begin{cases} 1 & \alpha \nu \quad i \in A \\ 0 & \alpha\nu \quad i \notin A\end{cases}. Τότε 0 \leqslant P(y_1,\ldots, y_k) = c_A. Άρα c_A \geqslant 0 για κάθε A \subseteq \{1,\ldots, k\} και άρα

\displaystyle{ y_1 \cdots y_{\ell} = \sum_{\{1,\ldots,\ell\} \subseteq A \subseteq \{1,\ldots,k\}}\prod_{i \in A} y_i \prod_{j \notin A}(1-y_j)} \geqslant 0

για κάθε y_1,\ldots,y_k \in [0,1].


nickthegreek
Δημοσιεύσεις: 401
Εγγραφή: Δευ Μαρ 01, 2010 2:07 pm
Τοποθεσία: Oxford

Re: Μεσογειάδα 2006

#14

Μη αναγνωσμένη δημοσίευση από nickthegreek » Δευ Νοέμ 08, 2010 9:57 am

Ευχαριστώ πολύ τον Δημήτρη για τη λύση του!!!Από αυτήν θα ήθελα να κρατήσω το σημαντικό γεγονός-λήμμα ότι αν μια συνάρτηση είναι γραμμική ως προς κάθε της μεταβλητή τότε παίρνει τα ακρότατά της στα άκρα των διαστημάτων που ορίζεται.

Έτσι λοιπόν με βάση αυτό το λήμμα θα έχουμε ότι όλα τα x_{i,j} είναι ίσα με 0 ή 1, όταν έχουμε ελάχιστο.

Παρόμοια λύση με αυτή του Δημήτρη (αυτή που είχα εγώ υπ'όψιν μου) δόθηκε από τον Στέργιο Αντωνακούδη.

Φιλικά,
Νίκος


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

Re: Μεσογειάδα 2006

#15

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Νοέμ 08, 2010 11:44 am

nickthegreek έγραψε: Παρόμοια λύση με αυτή του Δημήτρη (αυτή που είχα εγώ υπ'όψιν μου) δόθηκε από τον Στέργιο Αντωνακούδη.
Δράμα, Harvard, έπρεπε να το υποψιαστώ. Νίκο, να του στείλεις πολλά χαιρετίσματα.


nickthegreek
Δημοσιεύσεις: 401
Εγγραφή: Δευ Μαρ 01, 2010 2:07 pm
Τοποθεσία: Oxford

Re: Μεσογειάδα 2006

#16

Μη αναγνωσμένη δημοσίευση από nickthegreek » Πέμ Νοέμ 11, 2010 3:36 pm

Μπορεί κάποιος να ανεβάσει τη λύση με τις πιθανότητες;;;

Ευχαριστώ εκ των προτέρων.


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

Re: Μεσογειάδα 2006

#17

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Νοέμ 11, 2010 4:43 pm

nickthegreek έγραψε:Μπορεί κάποιος να ανεβάσει τη λύση με τις πιθανότητες;;;

Ευχαριστώ εκ των προτέρων.
Έστω (A_{i,j})_{1 \leqslant i \leqslant m, 1 \leqslant j \leqslant m} ανεξάρτητα ενδεχόμενα με \Pr(A_{i,j}) = x_{i,j}.

Ας αποδείξουμε πρώτα την υπόδειξη του Αχιλλέα

\displaystyle{ \bigcup_{j=1}^n \bigcap_{i=1}^m A_{i,j} \subseteq \bigcap_{i=1}^m \bigcup_{j=1}^n  A_{i,j} }

Αν \displaystyle{ x \in \bigcup_{j=1}^n \bigcap_{i=1}^m A_{i,j}} τότε θα υπάρχει 1 \leqslant \hat{j} \leqslant n ώστε \displaystyle{ x \in A_{i,\hat{j}}} για κάθε 1 \leqslant i \leqslant m. Αλλά τότε \displaystyle{ x \in A_{i,\hat{j}} \subseteq \bigcup_{j=1}^n  A_{i,j} }} για κάθε \displaystyle{ 1 \leqslant i \leqslant m} και άρα \displaystyle{ x \in \bigcap_{i=1}^m \bigcup_{j=1}^n  A_{i,j}}

Άρα θα έχουμε

\displaystyle{ \Pr\left(\bigcup_{j=1}^n \bigcap_{i=1}^m A_{i,j} \right) \leqslant \Pr\left(\bigcap_{i=1}^m \bigcup_{j=1}^n  A_{i,j} \right)}

Αλλά

\displaystyle{ \Pr\left(\bigcup_{j=1}^n \bigcap_{i=1}^m A_{i,j} \right) = 1 - \Pr\left(\bigcap_{j=1}^n \left(\bigcap_{i=1}^m A_{i,j}\right)^c \right) = 1 - \prod_{j=1}^n \Pr\left( \left(\bigcap_{i=1}^m A_{i,j}\right)^c\right) = 1 -  \prod_{j=1}^n\left(1 - \Pr\left(\bigcap_{i=1}^m A_{i,j}\right)  \right) = 1 - \prod_{j=1}^n\left(1 - \prod_{i=1}^m x_{i,j} \right)}

και

\displaystyle{ \Pr\left(\bigcap_{i=1}^m \bigcup_{j=1}^n  A_{i,j} \right) = \prod_{i=1}^m \Pr\left( \bigcup_{j=1}^n  A_{i,j}\right) = \prod_{i=1}^m \left( 1 - \Pr\left( \bigcap_{j=1}^n  A_{i,j}^c\right)\right) = \prod_{i=1}^m \left( 1 - \prod_{j=1}^n(1 - x_{i,j})\right)}

Το ζητούμενο έπεται.


Απάντηση

Επιστροφή σε “Άλγεβρα - Θεωρία Αριθμών - Συνδυαστική (Seniors) - Παλαιότερες Συζητήσεις”

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

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