Σε ένα μεγάλο πάρκο, 10.000 δέντρα είναι φυτεμένα σε διάταξη τετραγωνικού πλέγματος. Πόσα το πολύ δέντρα είναι δυνατό να κοπούν, ώστε από οποιαδήποτε θέση κομμένου δέντρου να μην είναι ορατή καμιά άλλη θέση κομμένου δέντρου.
(Οι διάμετροι των κορμών είναι αμελητέες σε σχέση με τις αποστάσεις των δέντρων και τα δέντρα αναπτύσσονται κατακόρυφα)
Αν θεωρήσουμε τη θέση κάθε δέντρου με συντεταγμένες ξεκινώντας από το (1,1) ως το (100,100), τότε ανάμεσα σε οποιαδήποτε δύο δέντρα με συντεταγμένες περιττούς αριθμούς θα παρεμβάλλεται ένα τουλάχιστον δέντρο με άρτιες συντεταγμένες (π.χ. το δέντρο που βρίσκεται στο μέσο του ευθυγράμμου τμήματος που ορίζουν τα δύο δέντρα).
Επομένως μπορούμε να κόψουμε τα δέντρα με περιττές συντεταγμένες (2.500 δέντρα).
Μπροστά μας έχουμε ένα τετράγωνο πλέγμα με 100 δέντρα η κάθε πλευρά. Από το κάθε δέντρο μπορούμε να κοιτάζουμε οριζόντια, κάθετα και διαγώνια. Μπορούμε να κόψουμε με ασφάλεια 2500 δέντρα ώστε να εξασφαλίσουμε το ζητούμενο. Αυτό μπορεί να γίνει αν στην κάθε μονή σειρά (πρώτη, τρίτη πέμπτη, έβδομη) θα κοπεί το 1,3,5,7…99ο δέντρο.
Αν αριθμήσουμε τις γραμμές και τις στήλες του πλέγματος με τους αριθμούς από 1 έως 100, τότε το μέγιστο πλήθος δέντρων που μπορούμε να κόψουμε προκύπτει κόβοντας όποια δέντρα βρίσκονται σε μονή σειρά και μονή στήλη. Άρα το μέγιστο πλήθος τους είναι 50*50 = 2500 δέντρα.
Πολύ σωστά, 2500 δέντρα!
Για να συμβαίνει το ζητούμενο, θα πρέπει σε κάθε ευθύγραμμο τμήμα που συνδέει δυο οποιαδήποτε κομμένα δέντρα να υπάρχει ενδιάμεσα άκοπο δέντρο. Αυτό σημαίνει ότι σε οποιοδήποτε στοιχειώδες τετράγωνο με κορυφές 4 γειτονικά δέντρα δεν είναι δυνατό να κοπούν περισσότερα από 1 δέντρο. Συνεπώς, ο ζητούμενος μέγιστος αριθμός δέντρων θα είναι το πολύ 10000/4=2500 δέντρα. Και το ότι μπορούμε κόβοντας ακριβώς 2.500 κομμένα δέντρα το δείξατε όλοι θαυμάσια!