petros r έγραψε:
4)Πόσα τετράγωνα μπορούμε να επιλέξουμε σε ένα 1000Χ1000 τεραίν σκάκι,έτσι ώστε να μην υπάρχουν τρία τετράγωνα με δύο στην ίδια σειρά και δύο στην ίδια στήλη?
Θα δείξουμε ότι σε μια

σκακιέρα με

μπορούμε να επιλέξουμε το πολύ

τετράγωνα με την ζητούμενη ιδιότητα. Είναι εύκολο να επιλέξουμε τόσα τετράγωνα π.χ. παίρνοντας όλα τα τετράγωνα της πρώτης γραμμής, όλα τα τετράγωνα της πρώτης στήλης και αφαιρώντας το τετράγωνο που βρίσκεται και στην πρώτη γραμμή και στην πρώτη στήλη. Θα δείξουμε με επαγωγή στο

ότι αν επιλέξουμε

τετράγωνα τότε θα υπάρχουν τρία με δυο στην ίδια γραμμή και δυο στην ίδια στήλη. Για

είναι προφανές. Για το επαγωγικό βήμα, αν διαλέξουμε

τετράγωνα, επειδή

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

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

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

και άρα συνολικά είχαν επιλεγεί το πολύ

τετράγωνα, άτοπο. Τέλος αν σε αυτήν την σειρά έχουν επιλεγεί

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

υποσκακιέρα. Συνολικά όμως, από την επαγωγική υπόθεση θα έχουμε επιλέξει
![k + [(m-1) + (n-k) - 2] = m+n-3 k + [(m-1) + (n-k) - 2] = m+n-3](/forum/ext/geomar/texintegr/latexrender/pictures/9c627643f23a2e9e7f7a02fd2e4ec26c.png)
, πάλι άτοπο.