Μεσογειάδα 2006

nickthegreek · #1

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

gtk1994 · #2

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

)

nickthegreek · #3

Φίλε μου,

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

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

#4

Η δυσκολία του προβλήματος βρίσκεται ακριβώς στην κατανόηση. Άμα κατανοηθεί τι ζητάει η λύση είναι ουσιαστικά δυο γραμμές. Γράφω την ζητούμενη ανισότητα για την περίπτωση 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 · #5

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

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

nickthegreek · #6

Άσχετο:

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

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

kwstas12345 · #7

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

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

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

nickthegreek · #8

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

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

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

Dimitris X · #9

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

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

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

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

nickthegreek · #10

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

Φιλικά

#11

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

#12

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

Φιλικά,

Αχιλλέας

#13

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

Κατ' αρχήν παρατηρούμε ότι η ανισότητα ισχύει αν $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 · #14

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

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

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

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

#15

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

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

nickthegreek · #16

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

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

#17

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)}$

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

Μεσογειάδα 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

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