IMC 2014/2/4

[Demetres]

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

Ονομάζουμε ένα πεπερασμένο σύνολο σημείων -γενικό αν δεν υπάρχει υπερεπίπεδο που να το -σχεδόν περιέχει.

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

[GVlachos]

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

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



Κατασκευή:
Έστω η αρχή των αξόνων. Θεωρούμε σημεία σε κάθε άξονα, ώστε κανένα να μην ταυτίζεται με το . Για κάθε σημείο, το υπερεπίπεδο που περνά από το και περιέχει τους άξονες που δεν περιέχουν το σημείο χάνει ακριβώς σημεία. Οπότε

Άνω φράγμα:
Έστω ότι έχουμε σύνολο με στοιχεία που ικανοποιεί τη ζητούμενη ιδιότητα. Θα δουλέψουμε με απαγωγή σε άτοπο.
Επιλέγουμε ένα σημείο τυχαία. Θεωρούμε ένα υπερεπίπεδο που δεν το περιέχει και χάνει ακριβώς σημεία. Σημαδεύουμε αυτά τα σημεία.
Στη συνέχεια, επιλέγουμε ένα μη σημαδεμένο σημείο και επαναλαμβάνουμε. Αυτή τη φορά θα σημαδεύσουμε το πολύ σημεία.
Επαναλαμβάνοντας φορές, μας μένουν τουλάχιστον μη σημαδεμένα σημεία. Επειδή αυτά τα σημεία περιέχονται στα διαφορετικά υπερεπίπεδα των προηγουμένων βημάτων, θα βρίσκονται πάνω στην ίδια ευθεία. Οπότε οποιοδήποτε υπερεπίπεδο που περιέχει δύο εκ των σημείων, θα τα περιεχει όλα. Οπότε κάθε υπερεπίπεδο χάνει ένα το πολύ από τα σημεία, άρα τα σημεία είναι . Θεωρώντας ένα τελευταίο υπερεπίπεδο, μένουμε με ένα μόνο μη σημαδεμένο σημείο (αφού αν το τελευταίο υπερεπίπεδο περιείχε 2, θα τα περιείχε όλα), και είναι προφανές ότι σε κάθε ένα από τα προηγούμενα βήματα σημαδεύτηκαν ακριβώς σημεία.
Με την παραπάνω διαδικασία επιλέγαμε τα υπερεπίπεδα τυχαία. Αλλάζοντας τη σειρά επιλογής, μπορούμε να δούμε ότι κάθε μία από τις -άδες σημείων που αφήνεται από ένα από τα ημιεπίπεδα της διαδικασίας έχει τα σημεία της στην ίδια ευθεία, η οποία περνάει από το .
Θεωρούμε τώρα το υπερεπίπεδο που αφήνει το και σημεία ακόμη. Από τα παραπάνω, το υπερεπίπεδο αυτό μπορεί να τέμνει κάθε μία από τις ευθείες σε ένα το πολύ σημείο, οπότε μένουν το και τουλάχιστον σημεία ακόμη σε κάθε ευθεία ακάλυπτα. Οπότε πρέπει . Για οδηγούμαστε σε άτοπο, οπότε η απάντηση είναι σε αυτή την περίπτωση.

Για ή το πρόβλημα είναι τετριμμένο.

[Nick1990]

Όντως κακός διαγωνισμός φέτος. Και αν κρίνω από τα σκορ: 4 εύκολα έως τετριμμένα προβλήματα και 2 μικρής-μέσης δυσκολίας είναι αρκετά για χρυσό... Με τα 4 πανεύκολα δε, παίρνεις χάλκινο... Μου θύμισε τους προ του 2009 IMC που τα προβλήματα ήταν αρκετά πρόχειρα.