mathematica.gr

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 2:58 pm**

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

Έστω m,n

θετικοί ακέραιοι και έστω:

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

και

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

$\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:Διορθώνω την εκφώνηση της άσκησης μετά από την σωστή παρατήρηση του Σιλουανού,τον οποίο και ευχαριστώ

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 3:28 pm**

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

)

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 3:33 pm**

Φίλε μου,

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

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

Δημοσιεύτηκε: **Κυρ Νοέμ 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}$

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 4:14 pm**

Yποθέτοντας ότι εννοείς ότι τα xi,j ανήκουν στο {0,1} δίνω μια πιθανή λύση(μην φωνάζετε αν έχω κάνει λάθος)

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

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 4:40 pm**

Άσχετο:

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

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

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 4:45 pm**

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

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

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

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 4:49 pm**

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

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

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

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 4:59 pm**

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

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

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

Η συμμετοχή είναι προαιρετική...Κάτι σαν test ικανοτήτων....

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 5:24 pm**

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

Φιλικά

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 5:52 pm**

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

Δημοσιεύτηκε: **Κυρ Νοέμ 07, 2010 7:31 pm**

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

$x_{i,j}\in [0,1]$ για και

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

$\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}}$ . Δώστε μια πιθανοθεωρητική εξήγηση της ζητούμενης ανισότητας.

Φιλικά,

Αχιλλέας

Δημοσιεύτηκε: **Κυρ Νοέμ 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]$ .

Δημοσιεύτηκε: **Δευ Νοέμ 08, 2010 9:57 am**

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

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

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

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

Δημοσιεύτηκε: **Δευ Νοέμ 08, 2010 11:44 am**

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

Δράμα, Harvard, έπρεπε να το υποψιαστώ. Νίκο, να του στείλεις πολλά χαιρετίσματα.

Δημοσιεύτηκε: **Πέμ Νοέμ 11, 2010 3:36 pm**

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

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

Δημοσιεύτηκε: **Πέμ Νοέμ 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)}$

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

mathematica.gr

Μεσογειάδα 2006

Μεσογειάδα 2006

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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