IMC 2014/2/4

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8587
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

IMC 2014/2/4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Αύγ 01, 2014 6:11 pm

Λέμε ότι ένα υποσύνολο του \mathbb{R}^n k-σχεδόν περιέχεται σε ένα υπερεπίπεδο, αν υπάρχουν λιγότερα από k σημεία σε αυτό το υποσύνολο που δεν ανήκουν στο υπερεπίπεδο.

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

Για κάθε ζεύγος θετικών ακεραίων k,n να βρεθεί ο ελάχιστος αριθμός d(k,n) έστω ώστε κάθε k-γενικό υποσύνολο του \mathbb{R}^n να περιέχει ένα k-γενικό υποσύνολο με το πολύ d(k,n) στοιχεία.


GVlachos
Δημοσιεύσεις: 126
Εγγραφή: Κυρ Μαρ 13, 2011 8:04 pm

Re: IMC 2014/2/4

#2

Μη αναγνωσμένη δημοσίευση από GVlachos » Σάβ Αύγ 02, 2014 2:54 am

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

Αρχικά, μας δίνεται μία αρκετά περίπλοκη εκφώνηση, οπότε βοηθάει πολύ να απλοποιήσουμε το ζητούμενο. Ισοδύναμα, ζητείται να:
Βρείτε το μέγιστο \delta(n,k), ώστε να υπάρχει σύνολο σημείων U\subset R^n με |U|=\delta(n,k), έτσι ώστε κάθε υπερεπίπεδο να τέμνει το U σε \delta(n,k)-k το πολύ σημεία και για κάθε v\in U, να υπάρχει υπερεπίπεδο P με v\notin P και |P\cap U|=\delta(n,k)-k (εύκολα βλέπουμε ότι \delta(n,k)=d(n,k))

\delta(n,k)=nk

Κατασκευή:
Έστω O η αρχή των n αξόνων. Θεωρούμε k σημεία σε κάθε άξονα, ώστε κανένα να μην ταυτίζεται με το O. Για κάθε σημείο, το υπερεπίπεδο που περνά από το O και περιέχει τους n-1 άξονες που δεν περιέχουν το σημείο χάνει ακριβώς k σημεία. Οπότε \delta(n,k) \geq nk

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

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


Άβαταρ μέλους
Nick1990
Δημοσιεύσεις: 659
Εγγραφή: Παρ Ιαν 23, 2009 3:15 pm
Τοποθεσία: Peking University, Πεκίνο

Re: IMC 2014/2/4

#3

Μη αναγνωσμένη δημοσίευση από Nick1990 » Σάβ Αύγ 02, 2014 2:09 pm

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


Κολλιοπουλος Νικος.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης