EGMO 2018/4
Συντονιστές: cretanman, ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ, socrates
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
EGMO 2018/4
Ένα ντόμινο είναι ένα ή πλακάκι.
Έστω ακέραιος . Σε έναν πίνακα τοποθετούμε ντόμινο με τέτοιο τρόπο ώστε καθένα από αυτά να καλύπτει ακριβώς δύο κελιά του πίνακα και τα ντόμινο μεταξύ τους να μην αλληλοκαλύπτονται.
Ορίζουμε ως τιμή μιας γραμμής ή στήλης το πλήθος των ντόμινο που καλύπτουν τουλάχιστον ένα κελί αυτής της γραμμής ή της στήλης. Ονομάζουμε την τοποθέτηση των ντόμινο ισορροπημένη εάν υπάρχει κάποιος τέτοιος ώστε η τιμή κάθε γραμμής και κάθε στήλης να είναι .
Αποδείξτε πως για κάθε υπάρχει κάποια ισορροπημένη τοποθέτηση και βρείτε τον ελάχιστο αριθμό των ντόμινο που απαιτείται για μια τέτοια τοποθέτηση.
Έστω ακέραιος . Σε έναν πίνακα τοποθετούμε ντόμινο με τέτοιο τρόπο ώστε καθένα από αυτά να καλύπτει ακριβώς δύο κελιά του πίνακα και τα ντόμινο μεταξύ τους να μην αλληλοκαλύπτονται.
Ορίζουμε ως τιμή μιας γραμμής ή στήλης το πλήθος των ντόμινο που καλύπτουν τουλάχιστον ένα κελί αυτής της γραμμής ή της στήλης. Ονομάζουμε την τοποθέτηση των ντόμινο ισορροπημένη εάν υπάρχει κάποιος τέτοιος ώστε η τιμή κάθε γραμμής και κάθε στήλης να είναι .
Αποδείξτε πως για κάθε υπάρχει κάποια ισορροπημένη τοποθέτηση και βρείτε τον ελάχιστο αριθμό των ντόμινο που απαιτείται για μια τέτοια τοποθέτηση.
Λέξεις Κλειδιά:
Re: EGMO 2018/4
Ο συμβολισμός σημαίνει "πλακάκι με το ένα σημείο στο και το άλλο δεξιά του". Αντίστοιχα με σημαίνει "κάτω".
Έστω ότι η τιμή κάθε στήλης και γραμμής είναι . Τότε, αφού συνολικά υπάρχουν στήλες και γραμμές και κάθε πλακάκι καλύπτει μία από την μία κατηγορία και δύο από την άλλη, θα πρέπει να υπάρχουν πλακάκια. Επομένως .
Έτσι, αν , η ελάχιστη δυνατή τιμή είναι μεγαλύτερη ή ίση του . Αυτό μπορεί να επιτευχθεί γεμίζοντας τους υποπίνακες κατά μήκος της κύριας διαγωνίου με πλακάκια . Έτσι, χρειάζονται πλακάκια.
Αν τότε προφανώς η ελάχιστη δυνατή τιμή είναι μεγαλύτερη ή ίση του . Θα δείξουμε ότι είναι εφικτή.
Σε πίνακα βάζουμε πλακάκια .
Σε πίνακα βάζουμε πλακάκια .
Σε πίνακα βάζουμε πλακάκια
.
Στους υπόλοιπους πίνακες γεμίζουμε τους υποπίνακες κατά μήκος της κύριας διαγωνίου μέχρι να μας μείνει πίνακας ή . Αν μας μείνει , τότε ξεκινάμε με πίνακα και συνεχίζουμε με μέχρι να μας μείνει στο τέλος.Έτσι, χρειάζονται πλακάκια.
Έστω ότι η τιμή κάθε στήλης και γραμμής είναι . Τότε, αφού συνολικά υπάρχουν στήλες και γραμμές και κάθε πλακάκι καλύπτει μία από την μία κατηγορία και δύο από την άλλη, θα πρέπει να υπάρχουν πλακάκια. Επομένως .
Έτσι, αν , η ελάχιστη δυνατή τιμή είναι μεγαλύτερη ή ίση του . Αυτό μπορεί να επιτευχθεί γεμίζοντας τους υποπίνακες κατά μήκος της κύριας διαγωνίου με πλακάκια . Έτσι, χρειάζονται πλακάκια.
Αν τότε προφανώς η ελάχιστη δυνατή τιμή είναι μεγαλύτερη ή ίση του . Θα δείξουμε ότι είναι εφικτή.
Σε πίνακα βάζουμε πλακάκια .
Σε πίνακα βάζουμε πλακάκια .
Σε πίνακα βάζουμε πλακάκια
.
Στους υπόλοιπους πίνακες γεμίζουμε τους υποπίνακες κατά μήκος της κύριας διαγωνίου μέχρι να μας μείνει πίνακας ή . Αν μας μείνει , τότε ξεκινάμε με πίνακα και συνεχίζουμε με μέχρι να μας μείνει στο τέλος.Έτσι, χρειάζονται πλακάκια.
Δημήτρης Σκουτέρης
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Google [Bot] και 18 επισκέπτες