mathematica.gr

Δημοσιεύτηκε: **Δευ Μαρ 07, 2011 7:09 pm**

Να δειχθεί ότι υπάρχει c > 0

ώστε να ισχύει το ακόλουθο:

Για κάθε θετικό ακέραιο $n \geqslant 3$ υπάρχουν

σημεία στο $[0,1] \times [0,1]$ ώστε κάθε τρίγωνο που σχηματίζουν έχει εμβαδόν τουλάχιστον c/n^2

. (Θεωρούμε ότι ένα εκφυλισμένο τρίγωνο έχει εμβαδόν 0.)

Δημοσιεύτηκε: **Τετ Μαρ 09, 2011 5:09 pm**

Πολύ ωραίο πρόβλημα..
Είμαι αρκετά σίγουρος πως λύνεται και πιο απλά, αλλά είχα δει μια άλλη άσκηση θεωρίας γραφημάτων που θύμιζε γεωμετρία να λύνεται με την ίδια βασική (αλγοριθμική) ιδέα..
Η βασική ιδέα είναι να δείξουμε ότι υπάρχουν 2n σημεία μεταξύ των οποίων υπάρχουν το πολύ n τρίγωνα με εμβαδό μικρότερο του $\frac {c} {n^2}$ , οπότε αφαιρώντας ένα από κάθε τέτοιο τρίγωνο παίρνουμε ένα σύνολο με (πιθανώς περισσότερα από) n σημεία με τη ζητούμενη ιδιότητα.

Για να το κάνουμε αυτό θα φράξουμε την πιθανότητα ένα τρίγωνο στο μοναδιαίο τετράγωνο του οποίου οι τρεις κορυφές Α,Β,Γ είναι επιλεγμένες τυχαία να έχει εμβαδό μικρότερο του $\frac {c} {n^2}$ .
Σταθεροποιούμε πρώτα το μήκος της πλευράς AB. Τότε για να έχουμε εμβαδό μικρότερο του $\frac {c} {n^2}$ θα πρέπει το αντίστοιχο ύψος να ικανοποιεί την ανισότητα: $\displaystyle{\frac {h AB} {2} \leq \frac {c} {n^2} \Rightarrow h \leq \frac {2c} {AB n^2}}$ .
Άρα το Γ πρέπει να βρίσκεται σε μια λωρίδα πλάτους $\frac {2c} {AB n^2}$ εκατέρωθεν της AB και άρα με μέγιστο μήκος $\sqrt{2}$ για ΑΒ κάποια διαγώνιο του τετραγώνου. Η πιθανότητα να συμβεί αυτό είναι (αρκετά χαλαρά νομίζω αφού στη διαγώνιο η λωρίδα "εξέχει" του μοναδιαίου τετραγώνου) φραγμένη από το $\displaystyle{\frac {4c\sqrt{2}} {AB n^2}}$
Τώρα αρκεί να ολοκληρώσουμε πάνω σε όλα τα πιθανά μήκη ΑΒ, όπου κάθε ΑΒ=x έχει πιθανότητα $2 \pi x dx$ (αφού $Pr[x \leq AB \leq x+dx] = \pi (x+dx)^2 - \pi x^2 \simeq 2 \pi x dx$ , κρατώντας το ένα σημείο σταθερό και παίρνοντας το Β στον αντίστοιχο δακτύλιο).
Άρα παίρνουμε:
$\displaystyle{\int_0^{\sqrt{2}} 2 \pi x \frac {4c\sqrt{2}} {x n^2} dx = \frac {16 \pi c} {n^2}$

Διαλέγουμε τώρα τυχαία 2n σημεία στο μοναδιαίο τετράγωνο. Η πιθανότητα ένα τρίγωνο από όσα δημιουργούνται να έχει εμβαδό μικρότερο του $\frac {c} {n^2}$ είναι με βάση τα παραπάνω $\frac {16 \pi c} {n^2}$ . Άρα η αναμενόμενη τιμή του αριθμού των τριγώνων με εμβαδό μικρότερο του $\frac {c} {n^2}$ είναι μικρότερη ίση από:
$\displaystyle{\binom{2n}{3}}\frac {16 \pi c} {n^2} = \frac{2n(2n-1)(2n-2)16 \pi c}{2 \cdot 3n^2} < \frac {64 \pi c} {3} n$
Άρα αρκεί να πάρουμε κάποιο c αρκετά μικρό ώστε ο συντελεστής μπροστά στο n να είναι μικρότερος του 1. Τότε θα υπάρχει κάποιο σύνολο 2n σημείων στο μοναδιαίο τετράγωνο στο οποίο το σύνολο των τριγώνων με εμβαδό μικρότερο του $\frac {c} {n^2}$ θα είναι μικρότερο ίσο του n. Άρα με βάση όσα αναφέραμε στη βασική ιδέα πιο πάνω αφαιρούμε ένα σημείο από κάθε τέτοιο τρίγωνο και έχουμε το ζητούμενο..

(ελπίζω να μην έχω κάποιο λάθος σε πράξεις αν και νομίζω πως το λάθος απλά θα αλλάζει το εύρος τιμών του c)

Δημοσιεύτηκε: **Τετ Μαρ 09, 2011 11:12 pm**

lemonidas έγραψε: Η βασική ιδέα είναι να δείξουμε ότι υπάρχουν 2n σημεία μεταξύ των οποίων υπάρχουν το πολύ n τρίγωνα με εμβαδό μικρότερο του $\frac {c} {n^2}$ , οπότε αφαιρώντας ένα από κάθε τέτοιο τρίγωνο παίρνουμε ένα σύνολο με (πιθανώς περισσότερα από) n σημεία με τη ζητούμενη ιδιότητα.

Λεωνίδα αυτή είναι πράγματι η βασική ιδέα της μιας από τις δυο λύσεις που γνωρίζω. (Δεν έλεγξα τις πράξεις διότι τώρα δεν έχω χρόνο. Θα το δω από Παρασκευή.) Όπως όμως υποπτεύεσαι υπάρχει και πιο απλή λύση.

mathematica.gr

Τρίγωνα και εμβαδά

Τρίγωνα και εμβαδά

Re: Τρίγωνα και εμβαδά

Re: Τρίγωνα και εμβαδά