Vojtech Jarnik 2017/3 Category I

[Demetres]

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

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

[ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ]

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

Εστω οι αριθμοί στις κορυφές.

Το ζητούμενο είναι μικρότερο η ίσο από

Επειδή και από C-S

έχουμε

Τελικά

αφου λόγω πολυέδρου

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

[Demetres]

Τελικά

αφου λόγω πολυέδρου

Σταύρο, η δεύτερη ανισότητα έχει λανθασμένη φορά. (Η τελική απάντηση είναι όντως .)

[Mikesar]

Τελικά πρόκειται για γνωστό πρόβλημα. Βάζω ένα hint-γενίκευση σε hide.

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Υπάρχει στο Problems from the Book στο κεφάλαιο με την extremal graph theory το ίδιο πρόβλημα για τυχαίο γράφημα . Η απάντηση είναι ότι αν είναι ο μέγιστος αριθμός ώστε το να έχει ως υπογράφημα το πλήρες γράφημα με κορυφές, τότε το ζητούμενο μέγιστο είναι . Στην προκειμένη .

[Demetres]

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

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

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



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



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