Vojtech Jarnik 2017/3 Category I

Συντονιστής: Demetres

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

Vojtech Jarnik 2017/3 Category I

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Μάιος 10, 2017 11:53 am

Έστω κυρτό πολύεδρο P. Ο Jaroslav γράφει έναν μη αρνητικό πραγματικό σε κάθε κορυφή του P με τέτοιον τρόπο ώστε το άθροισμα των αριθμών να ισούται με 1. Έπειτα, σε κάθε ακμή γράφει το γινόμενο των δύο αριθμών στα άκρα της.

Να αποδειχθεί ότι το άθροισμα των αριθμών στις ακμές είναι το πολύ 3/8.



Λέξεις Κλειδιά:
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2678
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

Re: Vojtech Jarnik 2017/3 Category I

#2

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Παρ Ιούλ 07, 2017 5:37 pm

Πως ξέφυγε αυτό.Οπως γράφει και ο Δημήτρης παρακάτω η λύση είναι ΛΑΘΟΣ

Εστω a_{i} i=1,2,....n οι αριθμοί στις κορυφές.

Το ζητούμενο είναι μικρότερο η ίσο από A=\sum _{i\neq j}a_{i}a_{j}

Επειδή \sum a_{i}=1 και από C-S \sum a_{i}^{2}\geq \frac{1}{n}

έχουμε 2A=1-\sum a_{i}^{2}\leq 1-\frac{1}{n}

Τελικά A\leq \frac{1}{2}-\frac{1}{2n}\leq \frac{3}{8}

αφου λόγω πολυέδρου n\geq 4

Η ισότητα ισχύει μόνο για τετράεδρο στο οποίο όλοι οι αριθμοί στις κορυφές είναι ίσοι.
τελευταία επεξεργασία από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ σε Παρ Ιούλ 07, 2017 10:10 pm, έχει επεξεργασθεί 1 φορά συνολικά.


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

Re: Vojtech Jarnik 2017/3 Category I

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιούλ 07, 2017 10:00 pm

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: Τελικά A\leq \frac{1}{2}-\frac{1}{2n}\leq \frac{3}{8}

αφου λόγω πολυέδρου n\geq 4
Σταύρο, η δεύτερη ανισότητα έχει λανθασμένη φορά. (Η τελική απάντηση είναι όντως 3/8.)


Mikesar
Δημοσιεύσεις: 139
Εγγραφή: Σάβ Ιούλ 30, 2011 8:29 pm
Τοποθεσία: Αθήνα

Re: Vojtech Jarnik 2017/3 Category I

#4

Μη αναγνωσμένη δημοσίευση από Mikesar » Σάβ Ιούλ 29, 2017 6:09 pm

Τελικά πρόκειται για γνωστό πρόβλημα. Βάζω ένα hint-γενίκευση σε hide.
Υπάρχει στο Problems from the Book στο κεφάλαιο με την extremal graph theory το ίδιο πρόβλημα για τυχαίο γράφημα G. Η απάντηση είναι ότι αν k είναι ο μέγιστος αριθμός ώστε το G να έχει ως υπογράφημα το πλήρες γράφημα με k κορυφές, τότε το ζητούμενο μέγιστο είναι \displaystyle\frac{1}{2}(1-\frac{1}{k}). Στην προκειμένη k=4.


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

Re: Vojtech Jarnik 2017/3 Category I

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Ιούλ 29, 2017 7:43 pm

Ας γράψω μια πλήρη λύση με βάση την υπόδειξη του Μιχάλη. Δεν θα χρησιμοποιήσω απευθείας το αποτέλεσμα μιας και αποδυκνύεται εύκολα με Cauchy-Schwarz.

Το P δίνει ένα επίπεδο γράφημα G. Από το θεώρημα τεσσάρων χρωμάτων, μπορώ να χωρίσω τις κορυφές του G σε τέσσερα σύνολα ώστε να μην υπάρχουν ακμέςμεταξύ κορυφών του ιδίου συνόλου. Έστω a,b,c,d τα αθροίσματα των αριθμών στις κορυφές εντός των συνόλων.

Τότε το άθροισμα των αριθμών στις ακμές είναι το πολύ

\displaystyle{ \begin{aligned} 
ab+ac+ad+bc+bd+cd &= \frac{(a+b+c+d)^2 - (a^2+b^2+c^2+d^2)}{2} \\ 
&\leqslant \frac{(a+b+c+d)^2 - \frac{1}{4}(a+b+c+d)^2}{2} = \frac{3}{8}. 
\end{aligned}}

Η ισότητα ισχύει π.χ. αν το P είναι ένα τετράεδρο και βάλουμε βάρος 1/4 σε κάθε κορυφή.

\rule{500pt}{0.5pt}

Υπάρχει και λύση που αποφεύγει την χρήση του θεωρήματος των τεσσάρων χρωμάτων.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

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