Παιχνίδια με πλακάκια

∫ot.T. · #1

Έχουμε

ορθογώνια με ακέραιου μήκους πλευρές. Τα τοποθετούμε στο επίπεδο ώστε να μην έχουμε επικάλυψη και οι πλευρές τους να είναι παράλληλες στους άξονες. Αν μερικές κορυφές ταυτιστούν τις μετράμε ως μία. Να αποδειχθεί ότι δεν μπορεί να προκύψουν λιγότερες από $n+ \left \lceil 2\sqrt{n}\right \rceil +1$ κορυφές.

αρψ2400 · #2

Η λιγότερες κορυφές εποτυγχάνονται όταν το κάθε νέο πλακάκι χρησιμοποιεί 3 κορυφές ήδη υπάρχουσες.Κάθε καινούρια γραμμή ή στήλη πλακιδίων απαιτεί 2 νέες κορυφές .Μετά κάθε νέο πλακάκι προσθέτει μία νέα κορυφή .Θα πρέπει να επιλέγεται κάθε φορά στήλη ή γραμμή με τα περισσότερα πλακάκια για να μπορούμε να προσθέσουμε περισσότερα πλακάκια με μια νέα κορυφή , κλείνοντας κάθε φορά το τετράγωνο.Αυτή είναι η κινητήριος ιδέα.Τώρα , η βέλτιστη διάταξη είναι αυτή που φαίνεται στο σχήμα.Κάθε άλλη ''υποψήφια'' πρόταση μπορεί να μετασχηματιστεί σε ορθογώνια με μία ( μόνο) ίσως , ημιτελή γραμμή ή στήλη και στη συνέχεια σε τετράγωνη με τροποποίηση διαστάσεων και μεταφορά πλακιδίου/ων.(Αναζητούμε τον ελάχιστο αριθμό κορυφών και μπορούμε να επιλέγουμε τα βέλτιστα πλακίδια).Έχουμε λοιπόν για τις δοιάφορες περιπτώσεις του n :
Έστω $n = \kappa^2 + \nu$ .
Αν $\nu = 0$ , τότε οι κορυφές είναι $(\kappa + 1)^2 = (\sqrt{n} + 1)^2$ .
Αν $1 \leq \nu \leq \kappa$ , τότε οι κορυφές είναι $n + 2\lfloor \sqrt{n} \rfloor + 2$ .
Αν $\kappa + 1 \leq \nu \leq 2\kappa$ , τότε οι κορυφές είναι $n + 2\lfloor \sqrt{n} \rfloor + 3$ .

Με λίγες ανισότητες και χρήση των συναρτήσεων floor και ceil, αυτά συνοψίζονται στον ζητούμενο τύπο.

Μάλλον θα υπάρχει και τρόπος να πάρει κανείς απευθείας το ζητούμενο ,αλλά για το πρόβλημα ακολούθησα μέχρι τέλους τον αρχικό δρόμο που είδα .

∫ot.T. · #3

αρψ2400 έγραψε: Πέμ Αύγ 07, 2025 12:15 am Η λιγότερες κορυφές εποτυγχάνονται όταν το κάθε νέο πλακάκι χρησιμοποιεί 3 κορυφές ήδη υπάρχουσες.Κάθε καινούρια γραμμή ή στήλη πλακιδίων απαιτεί 2 νέες κορυφές .Μετά κάθε νέο πλακάκι προσθέτει μία νέα κορυφή .Θα πρέπει να επιλέγεται κάθε φορά στήλη ή γραμμή με τα περισσότερα πλακάκια για να μπορούμε να προσθέσουμε περισσότερα πλακάκια με μια νέα κορυφή , κλείνοντας κάθε φορά το τετράγωνο.

Ομολογώ πως όταν είδα την έκταση της ανάρτησης εντυπωσιάστηκα γιατί στο μυαλό μου έχω κάτι «ελαφρώς» μεγαλύτερο. Αλλά θέλω να ρωτήσω πώς αποδεικνύεται η παραπάνω πρόταση. Δηλαδή πώς είμαστε σίγουροι ότι έτσι πρέπει να τοποθετηθούν τα πλακάκια για να έχουμε τις λιγότερες κορυφές; Εξάλλου υπάρχει περίπτωση να προσθέσουμε ορθογώνιο χωρίς να προσθέσουμε κορυφές και ενδεχομένως κάποιοι αλγόριθμοι να δίνουν «βραχυπρόθεσμα» πολλές κορυφές αλλά «μακροπρόθεσμα» να είναι αποτελεσματικοί. Θα χαρώ πολύ να δω μια αυστηρή απόδειξη αυτού του ισχυρισμού και έτσι να δωθεί μια συντομότερη λύση στο πρόβλημα.

αρψ2400 · #4

∫ot.T. έγραψε: Πέμ Αύγ 07, 2025 1:53 am
αρψ2400 έγραψε: Πέμ Αύγ 07, 2025 12:15 am Η λιγότερες κορυφές εποτυγχάνονται όταν το κάθε νέο πλακάκι χρησιμοποιεί 3 κορυφές ήδη υπάρχουσες.Κάθε καινούρια γραμμή ή στήλη πλακιδίων απαιτεί 2 νέες κορυφές .Μετά κάθε νέο πλακάκι προσθέτει μία νέα κορυφή .Θα πρέπει να επιλέγεται κάθε φορά στήλη ή γραμμή με τα περισσότερα πλακάκια για να μπορούμε να προσθέσουμε περισσότερα πλακάκια με μια νέα κορυφή , κλείνοντας κάθε φορά το τετράγωνο.
Ομολογώ πως όταν είδα την έκταση της ανάρτησης εντυπωσιάστηκα γιατί στο μυαλό μου έχω κάτι «ελαφρώς» μεγαλύτερο. Αλλά θέλω να ρωτήσω πώς αποδεικνύεται η παραπάνω πρόταση. Δηλαδή πώς είμαστε σίγουροι ότι έτσι πρέπει να τοποθετηθούν τα πλακάκια για να έχουμε τις λιγότερες κορυφές; Εξάλλου υπάρχει περίπτωση να προσθέσουμε ορθογώνιο χωρίς να προσθέσουμε κορυφές και ενδεχομένως κάποιοι αλγόριθμοι να δίνουν «βραχυπρόθεσμα» πολλές κορυφές αλλά «μακροπρόθεσμα» να είναι αποτελεσματικοί. Θα χαρώ πολύ να δω μια αυστηρή απόδειξη αυτού του ισχυρισμού και έτσι να δωθεί μια συντομότερη λύση στο πρόβλημα.

Η λιγότερες κορυφές εποτυγχάνονται όταν το κάθε νέο πλακάκι χρησιμοποιεί 3 κορυφές ήδη υπάρχουσες.Κάθε καινούρια γραμμή ή στήλη πλακιδίων απαιτεί 2 νέες κορυφές .Μετά κάθε νέο πλακάκι προσθέτει μία νέα κορυφή .Θα πρέπει να επιλέγεται κάθε φορά στήλη ή γραμμή με τα περισσότερα πλακάκια για να μπορούμε να προσθέσουμε περισσότερα πλακάκια με μια νέα κορυφή , κλείνοντας κάθε φορά το τετράγωνο.Αυτή είναι η κινητήριος ιδέα.(motivation)

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

Έρχεται κάποιος και λέει ''τα κατάφερα για n πλακίδια βρήκα τη διάταξη με τις λιγότερες κορυφές!'' .Και οι διάταξή του περιέχει τρύπες (ακάλυπτες κλειστές περιοχές σε ανάμεσα σε πλακίδια ).Οι τρύπες μπορουν να καλυφθούν από οποιαδήποτε εξωτερικά πλακάκια ,αφού τα εξωτερικά πλακάκια μοιράζοντα μία ή δύο κορυφές και τουλάχιστον το ίδιο θα συμβαίνει και στην τρύπα.Το τελευταίο πλακάκι (αν υπάρξει γιατί μπορεί στο μεταξύ η καινούρια διάταξη να σταματήσει να έχει τρύπα) )σίγουρα θα μειώσει το σύνολο των κορυφών.Τα πλακάκια μπορούν να μεταβάλλουν το μέγεθός τους κατά βούληση, φτάνει το πλήθος τους να παραμένει σταθερό και η διαδικασία μπορεί να συνεχιστεί μέχρι να πάψει να υπάρχει η τρύπα και με πλακάκια που στην πορεία γίνονται εξωτερικά.Πρόκειται για ένα μετασχηματισμό που δεν αθξάνει τις κορυφές .Φτάνουμε έτσι σε ένα συμπαγές χωρίς τρύπες πολυγωνικό σχήμα.Στη συνέχεια μετακινούμε εξωτερικά πλακάκια με κορυφή βαθμού 3 (εσοχές) σε κορυφές βαθμών 3 με μείωση τελικά εσοχών και συνολικού αριθμού κορυφών.Εχουμε έτσι ορθογώνιο παραλλήλόγραμμο με το πολύ μία ασυμπλήρωτη γραμμή ή στήλη , δηλαδή μόνο μία κορυφή βαθμού 3.Μετακινώντας στη συνέχεια εξ. πλακίδια κατά μήκος και τοποθετώντας τα κατά πλάτος στο σχήμα με ενδεχόμενη μείωση (αλλά ποτέ αύξηση κορυφών).Κανένας μετασχηματισμός δεν αυξάνει τον αριθμό των κορυφών διότι τα πλακάκια κατά την επανατοποθέτηση τροποποιούνται ώστε να ακουμπούν σε ίδιο τουλαχιστον αριθμό κορυφών με το σημείο αποκόλλησης. (Οι εσωτερικές κορυφές είναι κορυφές 4 πλακιδίων , διαφορετικά θα μπορούσαν να μειωθούν κατα μία μεγαλώνοντας τα γειτονικά πλακίδια μέχρι να συμπέσουν οι κορυφές τους.)Αυτές είναι πάνω κάτω οι τρέις σειρές στην αρχική ανάρτηση πιο αναλυτικα.(μετά το motivation που πολύ σωστά παρατήρησες δεν είναι καν απόπειρα απόδειξης αλλά απλά μια ματιά στην τελική λύση και με αυτό το πνεύμα αναφέρθηκε.Αυτό το νόημα είχε και η φράση ''κινητήριος ιδέα'' ).

∫ot.T. · #5

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

: Στιγμιότυπο οθόνης 2025-08-12, 13.55.06.png (27.92 KiB) Προβλήθηκε 1749 φορές

Για κάθε ομάδα υπάρχει πλέγμα που να περιέχει όλες τις κορυφές των ορθογωνίων της ομάδας. Αυτό συμβαίνει διότι τα ορθογώνια έχουν ακέραιες πλευρές, οπότε ένα πλέγμα μοναδιαίων τετραγώνων μήκους 1 που περιέχει τις κορυφές ενός εκ των ορθογωνίων της ομάδας θα περιέχει και όλες τις υπόλοιπες.

Άρα αν υπάρχουν παραπάνω από 2 ομάδες τότε επιλέγοντας τυχαία τις ομάδες

και

παρατηρούμε ότι είτε ανήκουν σε διαφορετικό πλέγμα, είτε στο ίδιο αλλά δεν μοιράζονται κάποια κορυφή. Συνεπώς όλες οι ομάδες ανά δύο δεν μοιράζονται κάποια κορυφή. Έτσι μπορώ να τις τοποθετήσω αρκετά μακρυά την μία από την άλλα χωρίς να μεταβληθεί το πλήθος των κορυφών και έπειτα να τις μετακινήσω ώστε όλες να ανήκουν στο ίδιο πλέγμα. Έτσι δεν μεταβλήθηκαν οι κορυφές. Με αυτόν τον τρόπο μπορεί να μειωθεί το πλήθος των κορυφών αν «ενώσω» τις ομάδες, δηλαδή από την στιγμή που ανήκουν στο ίδιο πλέγμα να τις μετακινήσω ώστε να μία ομάδα να μοιραστεί κάποια κορυφή με μία άλλη, οπότε να ενωθούν σε μία. Έτσι τελικά καταλήγω να έχω μία ομάδα με λιγότερες κορυφές, άρα έχω μία νέα τοποθέτηση με μειωμένο πλήθος κορυφών.

: Στιγμιότυπο οθόνης 2025-08-12, 14.08.21.png (46.76 KiB) Προβλήθηκε 1749 φορές

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

Λήμμα:

Έχουμε

ίσα τερτάγωνα όμοια προσανατολισμένα. Τα τοποθετούμε στο επίπεδο ώστε να μην έχουμε επικάλυψη. Αν μερικές κορυφές ταυτιστούν τις μετράμε ως μία. Τότε δεν μπορεί να προκύψουν λιγότερες από $n+ \left \lceil 2\sqrt{n}\right \rceil +1$ κορυφές.

Απόδειξη:

Στην βέλτιστη τοποθέτηση μπορώ να θεωρήσω ότι τα τετράγωνα ανήκουν σε πλέγμα και δημιουργούν μία ομάδα. Έστω μία τυχαία τέτοια τοποθέτηση. Αριθμούμε από αριστερά προς τα δεξιά τις στήλες του πλέγματος που περιέχουν κάποιο από τα τετράγωνα που τοποθέτησα. Αν

είναι η τελευταία στήλη τότε παρατηρούμε ότι μεταξύ της στήλης 1 και της

δεν υπάρχει κάποια στήλη του πλέγματος ώστε να μην περιέχει τετράωνο που τοποθετήθηκε, αλλιώς αυτή η κενή στήλη θα διαχώριζε το σχήμα δημιουργώντας παραπάνω από μία ομάδα, άτοπο. Έστω $a_{i}$ τοπλήθος τετραγώνων της στήλης

. Κάθε στήλη περικλύεται εντώς δύο κατακόρυφων ευθειών και κάθε μία από αυτές τις ευθείες περιέχει κορυφφές ορθογωνίων. Έστω $k_{i}$ το πλήθος των κορυφών στην αριστερή ευθεία της στήλης

και $k_{m+1}$ το πλήθος των κορυφών στην δεξιά ευθεία της στήλης

.
Εύκολα μπορούμε να διαπιστώσουμε ότι $k_{i} \geq max(a_{i-1},a_{i})+1$ , αφού οι κορυφές αυτής της ευθείας προέρχονται από τα τετράγωνα της στήλης i-1

και

και ουσιαστηκά αυτή που περιέχει τα περισσότερα τετράγωνα καθορίζει το ελάχιστο πλήθος (αφού τα τετράγωνα της άλλης στήλης μπορούν τα τοποθετηθούν αγγίζοντας τα υπόλοιπα, οπότε να μην προσθέσουν κορυφές). Στην βέλτιστη πείπτωση όπου έχουμε

τετράγωνα με το ένα να «κολλαέι» στο άλλο προκύπτουν στην ευθεία x+1

κορυφές, απ' όπου έπεται η προηγούμενη ανισότητα. Για διευκόλυνση γράφουμε την ανισότητα ως εξής:

$k_{i} \geq a_{i-1}+1$ αν $a_{i} - a_{i-1} \leq 0$

$k_{i} \geq a_{i-1}+1 + a_{i} - a_{i-1}$ αν $a_{i} - a_{i-1} > 0$

Τώρα το συνολικό πλήθος κορυφών είναι $\sum_{i=1}^{m+1}k_{i}\geq \sum_{i=1}^{m}(a_{i}+1) + a_{m}+1 + \sum_{i\in S}(a_{i}-a_{i+1})$

όπου $S=\left\{i / a_{i}-a_{i+1}>0\right\}$

Αρκεί $\sum_{i=1}^{m}(a_{i}+1) + a_{m}+1 + \sum_{i\in S}(a_{i}-a_{i+1}) \geq n+ \left \lceil 2\sqrt{n}\right \rceil +1$

Αρκεί $a_{m} + m + \sum_{i\in S}(a_{i}-a_{i+1}) \geq \left \lceil 2\sqrt{n}\right \rceil$

Αν $a_{N}=max(a_{i})$ , τότε $a_{N}\geq \dfrac{\sum_{i=1}^{m}a_{i}}{m}=\dfrac{n}{m}\geq 2\sqrt{n} - m\Rightarrow a_{N}\geq \left \lceil 2\sqrt{n}\right \rceil-m$

Άρα αρκεί $a_{m} + m + \sum_{i\in S}(a_{i}-a_{i+1}) \geq a_{N}+m$

Ή ισοδύναμα $\sum_{i\in S}(a_{i}-a_{i+1}) \geq a_{N}-a_{m}=(a_{N} -a_{N+1})+... +(a_{m-2}-a_{m-1})+(a_{m-1}-a_{m})$

που προφανώς ισχύει αφού το αριστερό μέρος της ανισότητας είναι άθροισμα θετικών όρων, ενώ το δεξί είναι άθροισμα όρων του αριστερού μέλους συν κάποιους αρνητικούς όρους (δηλαδή τα $a_{i}-a_{i-1}$ με $i\notin S$ ) $\square$

αρψ2400 · #6

∫ot.T. έγραψε: Τρί Αύγ 12, 2025 2:11 pm Πρώτα αποδεικνύουμε ότι τα ορθογώνια πρέπει να τοποθετηθούν σε πλέγμα.

Στην απόδειξη μου παρέλειψα αυτό το βήμα ως προφανές.Αρκεί οι κορυφές να μετακινηθούν σε ρητές συντεταγμένες , με μετακίνηση σε ρητό εγγύτερα της μικρότερης απόστασης μεταξύ δύο πλευρών όλων των πλακιδίων (που δεν είναι 0).Μετά αλλάζουμε κλίμακα (πολλαπλασιασμός με το ΕΚΠ), και απλώς μεγαλώνει ο ακέραιος του μήκους των πλευρών , ή και αλλάζουμε τη μονάδα μήκους αν θέλεις.(Δεν χρειάζεται το συστημα συντεταγμένων να είναι fix.)

∫ot.T. · #7

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

: Στιγμιότυπο οθόνης 2025-08-12, 14.42.52.png (32.56 KiB) Προβλήθηκε 1710 φορές

Τώρα θεωρούμε από πάνω προς τα κάτω όλες τις οριζόντιες ευθείες του πλέγματος που τέμνουν το περιγεγραμμένο ορθογώνιο (τις ευθείες της περιμέτρου δεν τις θεωρούμε)

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

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

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

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

Τώρα θεωρούμε υπακολουθίες σημείων της αρχικής ακολουθίας μίας ευθείας ώστε για κάθε υπακολουθία όλα τα σημεία της είναι διαδοχικά, τα εσωτερικά της σημεία είναι άσπρα και δεν είναι δυνατό να «επεκταθεί» αυτή η υπακολουθία διατηρώντας αυτήν την ιδιότητα. Έτσι έχουμε 2 περιπτώσεις για κάθε υπακολουθία.

Περίπτωση 1:

Τα ακραία σημεία μιας υπακολουθίας είναι μαύρα. Τότε για κάθε ζεύγος διαδοχικών σημείων τα βάφω μαύρα και το ευθύγραμμο τμήμα που δημιουργείται είτε χωρίζει το ορθογώνιο που περιέχει αυτό το τμήμα σε άλλα 2 (+1 ορθογώνιο) είτε χωρίζει την τρύπα που υπήρχε εκεί. Στην περίπτωση της τρύπας προσθέτω ένα ορθογώνιο στην πάνω στήλη του ευθύγραμμου τμήματος.

Περίπτωση 2:

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

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

: Στιγμιότυπο οθόνης 2025-08-12, 18.29.29.png (111.71 KiB) Προβλήθηκε 1710 φορές

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

: Στιγμιότυπο οθόνης 2025-08-12, 19.06.19.png (117.91 KiB) Προβλήθηκε 1710 φορές

- Στο σχήμα τα έντονα τμήματα αποτελούν την περίμετρο (είτε εσωτερική είτε εξωτερική) το «+» δηλώνει πως η άσπρη κορυφή θα βαφτεί μαύρη και το «Ο» δείχνει το νέο ορθογώνιο που προκύπτει μετά τις κινήσεις -

Στην πρώτη περίπτωση προσθέτουμε ένα παραπάνω ορθογώνιο από όσες κορυφές βάψαμε, ενώ στην δεύτερη περίπτωση οι δύο αυτές ποσότητες είναι ίσες. Τελικά καταλήγουμε να προσθέτουμε

ορθογώνια και

κορυφές με $x \geq y$ .

Όταν πια ολοκληρωθούν όλες οι κινήσεις έχω ένα σχήμα που αποτελείται μόνο από ίσα τετράγωνα, άρα από το λήμμα έχω τουλάχιστον $n+x+\left \lceil 2\sqrt{n+x}\right \rceil+1\geq n+y+\left \lceil 2\sqrt{n}\right \rceil+1$ κορυφές. Αφαιρώντας και τις

που έβαψα έπεται το ζητούμενο.

Παρατηρήσεις: Το δεδομένο των ακέραιων πλευρών ορθογωνίων μπορεί να γενικευτεί στους ρητούς όπου εύκολα με μία ομοιοθεσία επιστρέφει στην περίπτωση των ακέραιων.

∫ot.T. · #8

∫ot.T. έγραψε: Τρί Αύγ 12, 2025 2:11 pm
Λήμμα:

Έχουμε ίσα τερτάγωνα όμοια προσανατολισμένα. Τα τοποθετούμε στο επίπεδο ώστε να μην έχουμε επικάλυψη. Αν μερικές κορυφές ταυτιστούν τις μετράμε ως μία. Τότε δεν μπορεί να προκύψουν λιγότερες από $n+ \left \lceil 2\sqrt{n}\right \rceil +1$ κορυφές.

Απόδειξη του λήμματος από τον Κωνσταντίνο Αργυρόπουλο:

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

Καταλήγουμε έτσι με ένα σχήμα χωρίς τρύπες. Το εμβαδόν αυτού του σχήματος είναι

, αφού μπορούμε να θεωρήσουμε ότι όλα τα τετράγωνα έχουν εμβαδόν 1. Έστω

τα σημεία του πλέγματος που είναι στην περίμετρο του σχήματος και

τα εσωτερικά σημεία. Προφανώς επιθυμούμε να βρούμε το ελάχιστο του αθροίσματος x+y

, καθώς αυτά τα σημεία του πλέγματος αποτελούν και τις κορυφές των τετραγώνων.

Σύμφωνα με το θεώρημα του Pick έχουμε $E=\dfrac{x}{2} + y - 1$

Άρα αρκεί να ελαχιστοποιήσουμε το

, αφού $x+y=\dfrac{x}{2}+\dfrac{x}{2} + y= \dfrac{x}{2} +n+1$

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

Έστω

,

οι διαστάσεις του περιγεγραμμένου ορθογωνίου. Από τα προηγούνα έχουμε $\dfrac{x}{2} \geq a+b$
Επίσης το εμβαδόν του ορθογωνίου προφανώς δεν μπορεί να είναι μικρότερο του εμβαδού του εγγεγραμμένου σχήματος, άρα $ab \geq n$

Τελικά $\dfrac{x}{2} \geq a+b \geq 2\sqrt{ab} \geq 2\sqrt{n}$

Άρα συνολικά οι κορυφές είναι τουλάχιστον $n + 2\sqrt{n} +1$
Επειδή οι κορυφές είναι ακέραιος αριθμός παίρνουμε το ζητούμενο κάτω φράγμα.

∫ot.T. · #9

Το δεδομένο της μη επικάλυψης δεν είναι απαραίτητο. Το βασικό στοιχείο είναι πως οι κορυφές είναι τοποθετημένες σε πλέγμα. Άρα οποιαδήποτε τοποθέτηση

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

Παρατήρησα επίσης πως το πρόβλημα λύνεται χωρίς το λήμμα, χρησιμοποιώντας το πρόβλημα 6 από τον διαγωνισμό επιλογής της Εσθονίας 2007, σύμφωνα με το οποίο σε ένα $n \times n$ πλέγμα απαιτούνται το πολύ $(n-1)^{2}$ κινήσεις για να χρωματιστεί κάθε μοναδιαίο τετράγωνο του πλέγματος, όπου σε κάθε κίνηση χρωματίζονται

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

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

∫ot.T. · #10

∫ot.T. έγραψε: Τρί Αύγ 12, 2025 2:11 pm Λήμμα:

Έχουμε ίσα τερτάγωνα όμοια προσανατολισμένα. Τα τοποθετούμε στο επίπεδο ώστε να μην έχουμε επικάλυψη. Αν μερικές κορυφές ταυτιστούν τις μετράμε ως μία. Τότε δεν μπορεί να προκύψουν λιγότερες από $n+ \left \lceil 2\sqrt{n}\right \rceil +1$ κορυφές.

Μια λύση από το aops. Ουσιαστικά η ίδια ιδέα με το P6 της φετινής IMO.

Θεωρούμε τα κέντρα τους και μία μέγιστη αύξουσα ακολουθία αυτών των σημείων και μία μέγιστη φθίνουσα. Αν το μέγεθός τους είναι $s_{1}$ και $s_{2}$ αντίστοιχα τότε από θεώρημα Dilworth έχουμε ότι $s_{1}s_{2}\geq n$ με την ανισότητα να είναι αυστηρή αν οι δύο ακολουθίες δεν έχουν κοινό σημείο. Επιπλέον μία αύξουσα ακολουθία μπορεί να έχει οριζόντια τμήματα, αλλά μία φθίνουσα δεν μπορεί.

Ενώνουμε τα σημεία των δύο αυτών ακολουθιών οπότε χωρίζουν το επίπεδο σε 4 μέρη, τα πάνω, κάτω, δεξιά, αριστερά, για συντομία Π, Κ, Δ, Α.

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

Τέλος κάθε σημείο εκτός των ακολουθιών έχει επιλεχθεί μία φορά, το κοινό σημείο των ακολουθιών, αν υπάρχει, 4 φορές και τα υπόλοιπα 2 φορές. Άρα συνολικά έχουμε τουλάχιστον $n+s_{1}+s_{2}-1+2\geq n+2\sqrt{n}+1$ κορυφές όπως θέλαμε.
Αν δεν έχουν κοινό σημείο τότε $n+s_{1}+s_{2}\geq n+2\sqrt{n}+1$

∫ot.T. · #11

∫ot.T. έγραψε: Τρί Αύγ 12, 2025 2:11 pm
Λήμμα:

Έχουμε ίσα τερτάγωνα όμοια προσανατολισμένα. Τα τοποθετούμε στο επίπεδο ώστε να μην έχουμε επικάλυψη. Αν μερικές κορυφές ταυτιστούν τις μετράμε ως μία. Τότε δεν μπορεί να προκύψουν λιγότερες από $n+ \left \lceil 2\sqrt{n}\right \rceil +1$ κορυφές.

Απόδειξη:

Στην βέλτιστη τοποθέτηση μπορώ να θεωρήσω ότι τα τετράγωνα ανήκουν σε πλέγμα και δημιουργούν μία ομάδα. Έστω μία τυχαία τέτοια τοποθέτηση. Αριθμούμε από αριστερά προς τα δεξιά τις στήλες του πλέγματος που περιέχουν κάποιο από τα τετράγωνα που τοποθέτησα. Αν είναι η τελευταία στήλη τότε παρατηρούμε ότι μεταξύ της στήλης 1 και της δεν υπάρχει κάποια στήλη του πλέγματος ώστε να μην περιέχει τετράωνο που τοποθετήθηκε, αλλιώς αυτή η κενή στήλη θα διαχώριζε το σχήμα δημιουργώντας παραπάνω από μία ομάδα, άτοπο. Έστω $a_{i}$ τοπλήθος τετραγώνων της στήλης . Κάθε στήλη περικλύεται εντώς δύο κατακόρυφων ευθειών και κάθε μία από αυτές τις ευθείες περιέχει κορυφφές ορθογωνίων. Έστω $k_{i}$ το πλήθος των κορυφών στην αριστερή ευθεία της στήλης και $k_{m+1}$ το πλήθος των κορυφών στην δεξιά ευθεία της στήλης .
Εύκολα μπορούμε να διαπιστώσουμε ότι $k_{i} \geq max(a_{i-1},a_{i})+1$ , αφού οι κορυφές αυτής της ευθείας προέρχονται από τα τετράγωνα της στήλης και και ουσιαστηκά αυτή που περιέχει τα περισσότερα τετράγωνα καθορίζει το ελάχιστο πλήθος (αφού τα τετράγωνα της άλλης στήλης μπορούν τα τοποθετηθούν αγγίζοντας τα υπόλοιπα, οπότε να μην προσθέσουν κορυφές). Στην βέλτιστη πείπτωση όπου έχουμε τετράγωνα με το ένα να «κολλάει» στο άλλο προκύπτουν στην ευθεία κορυφές, απ' όπου έπεται η προηγούμενη ανισότητα. Για διευκόλυνση γράφουμε την ανισότητα ως εξής:

$k_{i} \geq a_{i-1}+1$ αν $a_{i} - a_{i-1} \leq 0$

$k_{i} \geq a_{i-1}+1 + a_{i} - a_{i-1}$ αν $a_{i} - a_{i-1} > 0$

Τώρα το συνολικό πλήθος κορυφών είναι $\sum_{i=1}^{m+1}k_{i}\geq \sum_{i=1}^{m}(a_{i}+1) + a_{m}+1 + \sum_{i\in S}(a_{i}-a_{i+1})$

όπου $S=\left\{i / a_{i}-a_{i+1}>0\right\}$

Αρκεί $\sum_{i=1}^{m}(a_{i}+1) + a_{m}+1 + \sum_{i\in S}(a_{i}-a_{i+1}) \geq n+ \left \lceil 2\sqrt{n}\right \rceil +1$

Αρκεί $a_{m} + m + \sum_{i\in S}(a_{i}-a_{i+1}) \geq \left \lceil 2\sqrt{n}\right \rceil$

Αν $a_{N}=max(a_{i})$ , τότε $a_{N}\geq \dfrac{\sum_{i=1}^{m}a_{i}}{m}=\dfrac{n}{m}\geq 2\sqrt{n} - m\Rightarrow a_{N}\geq \left \lceil 2\sqrt{n}\right \rceil-m$

Άρα αρκεί $a_{m} + m + \sum_{i\in S}(a_{i}-a_{i+1}) \geq a_{N}+m$

Ή ισοδύναμα $\sum_{i\in S}(a_{i}-a_{i+1}) \geq a_{N}-a_{m}=(a_{N} -a_{N+1})+... +(a_{m-2}-a_{m-1})+(a_{m-1}-a_{m})$

που προφανώς ισχύει αφού το αριστερό μέρος της ανισότητας είναι άθροισμα θετικών όρων, ενώ το δεξί είναι άθροισμα όρων του αριστερού μέλους συν κάποιους αρνητικούς όρους (δηλαδή τα $a_{i}-a_{i-1}$ με $i\notin S$ ) $\square$

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

Εφόσον $k_{i} \geq max(a_{i-1},a_{i})+1$ για $m \geq i \geq 2$ και $k_1 \geq a_1 +1$ και $k_{m+1} \geq a_{m}+1$ τότε μπορούμε να πούμε

$k_i \geq a_i +1$ για $i \leq N$

$k_i \geq a_{i-1}+1$ για $i \geq N+1$

οπότε έτσι στο δεξί μέρος των ανισοτήτων εμφανίζονται όλα τα a_i

ακριβώς μία φορά όμως το a_N

εμφανίζεται δύο φορές, άρα έχουμε:

$\sum_{i=1}^{m+1}k_{i}\geq \sum_{i=1}^{m}(a_{i}+1) + a_N +1 \geq n+m+ a_N +1 \geq n+ \left \lceil 2\sqrt{n}\right \rceil +1$

Η τελευταία ανισότητα ισχύει από την

$a_{N}\geq \left \lceil 2\sqrt{n}\right \rceil-m$

που είχαμε δείξει στην πρώτη λύση.

Παιχνίδια με πλακάκια

Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

Re: Παιχνίδια με πλακάκια

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