Τεμνόμενες διαγώνιοι

#1

Φέρουμε ορισμένες από τις διαγωνίους ενός κυρτού

-γώνου. Ονομάζουμε μια από αυτές τις διαγωνίους καλή αν τέμνει (εσωτερικά του πολυγώνου) ακριβώς μία άλλη από τις διαγωνίους που σχεδιάσαμε. Να βρεθεί ο μέγιστος δυνατός αριθμός καλών διαγωνίων.

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

Mikesar · #2

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

Petros N. · #3

Έστω

ο μέγιστος αριθμός καλών διαγωνίων σε ένα κυρτό r-γωνο r>1

. Εύκολα

. θα δείξω με ισχυρη επαγωγή ότι
f(2k)=f(2k+1)=2k-2

. Έστω ισχύει για κάθε $0 \leq k < K$ . θα δείξω ότι ισχύει και για k=K

.

Έστω $A_1A_2...A_{2K}$ το κυρτό πολύγωνο, τότε φέρνοντας τις διαγωνίους: $A_{2K-l}A_{l+2},l=0,1,...,K-2$ , A_1A_3

,
$A_{2K-l}A_{l+4}, l=0,1,..,K-3$ εύκολα βλέπουμε ότι είναι όλες καλές άρα $f(2K) \geq 2K-2$ .
Έστω ότι υπήρχε σχηματισμός με παραπάνω απο 2K-2

καλές διαγωνίους τότε πρφανώς υπάρχουν 2 καλές διαγώνιοι που τέμνονται μέσα στο πολύγωνο, έστω AC,BD

. Τότε αυτές οι δύο το χωρίζουν σε 4 περιοχές σημείων, τις AB,BC,CD,DA

(περιλαμβάνοντας και τα ακριανά σημεία). Αφού οι AC,BD

καλές δεν υπάρχουν διαγώνιοι από μία περιοχή σε άλλη.
Έστω λοιπόν ότι οι περιοχές έχουν $a,b,c,d \geq 2$ σημεία, τότε προφανώς a+b+c+d=2K+4

και προφανώς ο μέγιστος αριθμός καλών διαγωνίων είναι f(a)+f(b)+f(c)+f(d)+2

. Για

απο επαγωγική υπόθεση $f(r) \leq r-2$ , άρα
$f(2K) \leq f(a)+f(b)+f(c)+f(d)+2 \leq a-2+b-2+c-2+d-2+2=2K-2$ , άτοπο. Άρα $f(2K) \leq 2K-2$ , οπότε f(2K)=2K-2

.

Έστω $A_1A_2...A_{2K+1}$ το κυρτό πολύγωνο, τότε φέρνοντας τις διαγωνίους: A_1A_l , l=3,4,...,2K

και $A_2A_{2K+1}$ βλέπουμε ότι υπάρχουν 2K-2 καλές διαγώνιοι, οπότε $f(2K+1) \geq 2K-2$ . Έστω ότι υπήρχε σχηματισμός με τουλάχιστον 2K-1

καλές διαγωνίους , τότε πάλι υπάρχουν 2 που τέμνονται στο πολύγωνο, έστω AC,BD

. Τότε αυτές οι δύο το χωρίζουν ξανά σε 4 περιοχές σημείων, τις AB,BC,CD,DA

με
$a,b,c,d \geq 2$ σημεία αντοίστιχα οπότε a+b+c+d=2K+5

. τουλάχιστον ένας από τους a,b,c,d

είναι περιττος, έστω ο

, τότε
(αφου a<2K

)

. Τότε έχουμε $f(2K+1) \leq f(a)+f(b)+f(c)+f(d)+2 \leq a-3+b-2+c-2+d-2+2=2K-2$ , άτοπο. Άρα
$f(2K+1) \leq 2K-2$ , οπότε f(2K+1)=2K-2

.

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

#4

Πέτρο πολύ καλά. Η λύση σου είναι κάπως πιο απλή από την δική μου. Είχα προσπαθήσει το ίδιο αλλά νόμιζα πως δεν θα δούλευε και έτσι κατέληξα σε μια λίγο διαφορετική λύση:

Ονομάζω μια από τις διαγωνίους που φέραμε εξαιρετική αν τέμνει το πολύ μία άλλη διαγώνιο. Έστω g(n)

ο μέγιστος αριθμός των εξαιρετικών διαγωνίων. Θα δείξω ότι g(n) = n-2

αν

άρτιος και g(n) = n-3

αν

περιττός.

Αν δεν υπάρχουν καλές διαγώνιοι τότε όντως υπάρχουν το πολύ n-3

εξαιρετικές. Έστω λοιπόν μια καλή διαγώνιος. Χωρίς βλάβη ενώνει τα A_1

και

. Οπότε χωρίζει το πολύγωνο στα πολύγωνα $A_1A_2\cdots A_mA_1$ και $A_m A_{m+1} \cdots A_1A_m$ . Γνωρίζουμε ότι υπάρχει ακριβώς μία διαγώνιος $\ell$ μεταξύ των δυο κομματιών. Αγνοώντας την, από την επαγωγική υπόθεση έχουμε το πολύ g(m)

εξαιρετικές διαγωνίους στο πρώτο πολύγωνο και g(n-m)

εξαιρετικές διαγωνίους στο δεύτερο πολύγωνο. Προσθέτωντας την $\ell$ ίσως καταστρέψουμε κάποιες από αυτές τις εξαιρετικές διαγωνίους αλλά δεν δημιουργούμε καινούργιες εκτός ίσως από την ίδια την $\ell$ . [Αυτός είναι και ο λόγος που χρειάστηκε τις εξαιρετικές διαγωνίους.] Οπότε έχουμε το πολύ g(m) + g(n-m) + 2

εξαιρετικές διαγωνίους. Για

άρτιο από την επαγωγική υπόθεση είναι $g(m) + g(n-m) + 2 \leqslant (m-2) + (n-m-2) + 2 = n-2$ . Για

περιττό τουλάχιστον ένα από τα m,n-m

είναι περιττό οπότε από την επαγωγική υπόθεση είναι $g(m) + g(n-m) + 2 \leqslant n-3$ .

Πέτρο συμφωνώ με την κρίση σου. Ίσως δεν είναι τόσο δύσκολο για medium πιστεύω όμως ότι είναι άνετα ένα easy πρόβλημα ΙΜΟ. Το πρόβλημα το πήρα από τον φετινό ρωσικό διαγωνισμό για grade 9, το οποίο νομίζω αντιστοιχεί σε Α' Λυκείου. (Δείτε εδώ. Η πρώτη λύση είναι ίδια με αυτήν του Πέτρου.) Για grade 9 το θεωρώ πως είναι πολύ δύσκολο (ιδίως αφού δεν δίνεται η τελική απάντηση) και ήθελα να σιγουρευτώ μήπως μου διαφεύγει κάτι απλό.

Τεμνόμενες διαγώνιοι

Τεμνόμενες διαγώνιοι

Re: Τεμνόμενες διαγώνιοι

Re: Τεμνόμενες διαγώνιοι

Re: Τεμνόμενες διαγώνιοι

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