Χρωματισμός πλέγματος

[sokpanvas]

Ο Γιώργος έχει ένα πλέγμα λευκών τετραγώνων και βάφει μερικά από αυτά μαύρα. Σε κάθε λευκό τετράγωνο ο Γιώργος γράφει τον αριθμό των μαύρων τετραγώνων τα οποία μοιράζονται μια πλευρά με αυτό. Να βρεθεί το μέγιστο άθροισμα των αριθμών που μπορεί να γράψει ο Γιώργος.

[Mihalis_Lambrou]

Ο Γιώργος έχει ένα πλέγμα λευκών τετραγώνων και βάφει μερικά από αυτά μαύρα. Σε κάθε λευκό τετράγωνο ο Γιώργος γράφει τον αριθμό των μαύρων τετραγώνων τα οποία μοιράζονται μια πλευρά με αυτό. Να βρεθεί το μέγιστο άθροισμα των αριθμών που μπορεί να γράψει ο Γιώργος.

H πολύ ωραία αυτή άσκηση (με πιο μικρά νούμερα αλλά η ουσία δεν αλλάζει) είχε πέσει σε πρόσφατο διαγωνισμό Καγκουρό. Αντιγράφω από εκεί την εκφώνηση και παραθέτω την λύση που είχα γράψει στο βιβλίο μου με τα θέματα συν λύσεις του διαγωνισμού.

(Άσκηση 27 για μαθητές Γ Γυμνασίου/ Α΄Λυκείου). Η Υπατία σχεδίασε ένα 3x4 ορθογώνιο παραλληλόγραμμο χωρισμένο σε τετράγωνα, μερικά από τα οποία τα έβαψε μαύρα. Σε κάθε λευκό τετράγωνο έγραψε τον αριθμό των μαύρων τετραγώνων με τα οποία το συγκεκριμένο τετράγωνο έχει κοινή πλευρά. Το σχήμα δείχνει ένα παράδειγμα. Μετά έκανε την ανάλογη εργασία σε ένα 2x10 ορθογώνιο. Αν προσθέσει τους αριθμούς στα λευκά τετράγωνα, ποιο είναι το μεγαλύτερο δυνατό άθροισμα που μπορεί να πάρει;

Λύση

Θεωρούμε το παραλληλόγραμμο ως ένα χωράφι το οποίο έχει φράχτη στην περίμετρό του και το οποίο είναι χωρισμένο σε τετράγωνα με πλευρά μία μονάδα το καθένα. Επίσης θεωρούμε ως εσωτερικούς κήπους όλες τις περιοχές που αποτελούνται από λευκά τετράγωνα τα οποία συνορεύουν μεταξύ τους. Θέλουμε τώρα να τοποθετήσουμε φράχτη γύρω από τους λευκούς κήπους. Ήδη έχουν φράχτη στο εξωτερικό τους μέρος, αλλά τώρα θέλουμε να τα ξεχωρίσουμε από τα μαύρα τετράγωνα, στο εσωτερικό μέρος του χωραφιού. Παρατηρούμε ότι ο αριθμός μέσα σε κάθε λευκό τετράγωνο δηλώνει πόσο φράχτη χρειαζόμαστε για το συγκεκριμένο τετράγωνο, αφού ο αριθμός αυτός δείχνει το μήκος του συνόρου με τα γειτονικά του μαύρα τετράγωνα. Είναι σαφές ότι το συνολικό μήκος των εσωτερικών φραχτών δεν μπορεί να ξεπερνά σε μήκος το άθροισμα όλων των δυνατών εσωτερικών διαχωριστικών συνόρων (οι κόκκινες γραμμές). Οι εσωτερικές (κόκκινες) γραμμές είναι «μία οριζόντια μήκους 10» και «9 κάθετες μήκους 2 η καθεμία», άρα το συνολικό τους μήκος είναι . Παρατηρούμε ότι το μέγιστο αυτό δυνατό μήκος μπορεί να προκύψει αν τα λευκά και τα μαύρα τετράγωνα επιλεγούν εναλλάξ σε διαδοχικές θέσεις που θυμίζουν μία σκακιέρα, όπως στο σχήμα. Στο συγκεκριμένο σχήμα όλες οι εσωτερικές πλευρές έχουν χρησιμοποιηθεί ως σύνορο, στον ένα ή στον άλλο κήπο. Άρα η απάντηση στο πρόβλημά μας είναι 28. Ας προσθέσουμε ότι περιττεύει να μετρήσουμε το εσωτερικό σύνορο στο σχήμα που προκύπτει, αφού ήδη το γνωρίζουμε! Για επιβεβαίωση και μόνο σημειώνουμε ότι το συνολικό σύνορο (άθροισμα από 2-αρια και 3-αρια όπως στο σχήμα) είναι , όπως πριν.

[sokpanvas]

Ο Γιώργος έχει ένα πλέγμα λευκών τετραγώνων και βάφει μερικά από αυτά μαύρα. Σε κάθε λευκό τετράγωνο ο Γιώργος γράφει τον αριθμό των μαύρων τετραγώνων τα οποία μοιράζονται μια πλευρά με αυτό. Να βρεθεί το μέγιστο άθροισμα των αριθμών που μπορεί να γράψει ο Γιώργος.

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

Είχε πέσει και στην διεθνή ασιατική ολυμπιάδα AIMO το 2016.