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

#1

Σε μια $n \times n$ σκακιέρα είναι τοποθετημένα κάποια πιόνια. Αν στο τετράγωνο που βρίσκεται στην σειρά

και στήλη

δεν υπάρχει κάποιο πιόνι, τότε σε αυτήν την σειρά και αυτήν την στήλη υπάρχουν συνολικά τουλάχιστον

πιόνια.

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

πιόνια.

dement · #2

Αριθμούμε τα

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

Έστω ότι η σκακιέρα έχει

πιόνια. Κάθε ένα από τα n^2 - k

κενά τετράγωνα έχει τουλάχιστον

πιόνια στην ίδια γραμμή ή στήλη, οπότε $N \geqslant n (n^2 - k)$

Επιπλέον, σε μία δεδομένη γραμμή ή στήλη που περιέχει

πιόνια, ο αριθμός των ζευγών της είναι $\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}$

#3

Πολύ ωραία!

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

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

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

πιόνια. Χωρίς βλάβη της γενικότητας αυτά βρίσκονται στις γραμμές

έως

.

Κάθε μια από τις γραμμές

έως

έχει τουλάχιστον

πιόνια.
Κάθε μια από τις γραμμές k+1

έως

έχει τουλάχιστον n-k

πιόνια.

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

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

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

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

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

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