Κλασική σε σκακιέρα

Συντονιστές: Demetres, silouan

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

Κλασική σε σκακιέρα

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Απρ 23, 2017 8:41 pm

Σε μια n \times n σκακιέρα είναι τοποθετημένα κάποια πιόνια. Αν στο τετράγωνο που βρίσκεται στην σειρά i και στήλη j δεν υπάρχει κάποιο πιόνι, τότε σε αυτήν την σειρά και αυτήν την στήλη υπάρχουν συνολικά τουλάχιστον n πιόνια.

Να δειχθεί πως στην σκακιέρα υπάρχουν τουλάχιστον n^2/2 πιόνια.



Λέξεις Κλειδιά:
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1381
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Κλασική σε σκακιέρα

#2

Μη αναγνωσμένη δημοσίευση από dement » Τετ Απρ 26, 2017 3:20 am

Αριθμούμε τα N ζεύγη τετραγώνων που ανήκουν στην ίδια γραμμή ή στήλη και το ένα έχει πιόνι ενώ το άλλο όχι.

Έστω ότι η σκακιέρα έχει k πιόνια. Κάθε ένα από τα n^2 - k κενά τετράγωνα έχει τουλάχιστον n πιόνια στην ίδια γραμμή ή στήλη, οπότε N \geqslant n (n^2 - k)

Επιπλέον, σε μία δεδομένη γραμμή ή στήλη που περιέχει p πιόνια, ο αριθμός των ζευγών της είναι \displaystyle p (n-p) \leqslant \frac{n^2}{4}. Έτσι, λαμβάνοντας υπόψη κάθε γραμμή και κάθε στήλη έχουμε \displaystyle N \leqslant \frac{n^3}{2}

Συνδυάζοντας τις δύο ανισότητες έχουμε \displaystyle n (n^2 - k) \leqslant \frac{n^3}{2} \implies k \geqslant \frac{n^2}{2}


Δημήτρης Σκουτέρης

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

Re: Κλασική σε σκακιέρα

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Απρ 26, 2017 10:12 am

Πολύ ωραία!

Την πήρα από εδώ. Είναι αρκετά κλασική αλλά δεν γνωρίζω την αρχική πηγή.

Ένας άλλος τρόπος λύσης είναι με το extremum principle:

Παίρνουμε την σειρά η στήλη με τα λιγότερα πιόνια. Έστω χωρίς βλάβη της γενικότητας ότι είναι η πρώτη στήλη και ότι έχει k πιόνια. Χωρίς βλάβη της γενικότητας αυτά βρίσκονται στις γραμμές 1 έως k.

Κάθε μια από τις γραμμές 1 έως k έχει τουλάχιστον k πιόνια.
Κάθε μια από τις γραμμές k+1 έως n έχει τουλάχιστον n-k πιόνια.

Άρα συνολικά έχουμε τουλάχιστον \displaystyle{ k^2 + (n-k)^2 \leqslant 2(n/2)^2 = \frac{n^2}{2}} πιόνια.


Απάντηση

Επιστροφή σε “Συνδυαστική - Επίπεδο Αρχιμήδη (Seniors)”

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

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