MIPT 2013/2/3

Mikesar · #1

Θεωρούμε μοναδιαίους κύβους στον $\mathbb{R}^n$ με πλευρές παράλληλες στους άξονες, τους οποίους θα ονομάζουμε απλώς κύβους. Δίνονται $2^{n-1}+1$ κύβοι οι οποίοι ανά δύο δεν τέμνονται. Να αποδειχθεί ότι είτε δεν υπάρχει κανένας κύβος που να τέμνει όλους τους δοθέντες κύβους, είτε όλοι οι κύβοι που τέμνουν τους δοθέντες κύβους έχουν κοινό σημείο.

#2

Σε κάθε κύβο

, αντιστοιχούμε το σημείο $(c_1,\ldots,c_n) \in C$ με κάθε c_i

να είναι το ελάχιστο δυνατό. (Το «κάτω αριστερά» σημείο στην περίπτωση n=2

.)

Για κάθε $1 \leqslant k \leqslant n$ ορίζουμε την μερική διάταξη <_k

στο σύνολο των κύβων ως εξής: C <_k C'

αν και μόνο αν c_k +1 < c_k'

.

Αν για κάποιο

έχουμε

, τότε

οπότε δεν μπορεί κανένας κύβος να τέμνει και τον

και τον

. Μπορούμε λοιπόν να υποθέσουμε ότι για κάθε

, κάθε αλυσίδα της διάταξης <_k

έχει το πολύ δύο στοιχεία.

Αν C <_k C'

, τότε είτε κανένας κύβος δεν τέμνει τους C,C'

, είτε όλοι οι κύβοι που τους τέμνουν έχουν κοινή

-συντεταγμένη. (Οποιαδήποτε τιμή ανάμεσα στα c_k

και

μας κάνει.) Μπορούμε λοιπόν να υποθέσουμε ότι υπάρχει $1 \leqslant k \leqslant n$ , έστω το k=n

, ώστε το σύνολο όλων των $2^{n-1}+1$ κύβων να είναι αντιαλυσίδα στην μερική διάταξη <_n

.

Επειδή $2^{n-1}+1 = 2 \cdot 2^{n-2}+1$ , και επειδή η $<_{n-1}$ δεν έχει αλυσίδα με 2+1

στοιχεία, από το θεώρημα Dilworth, η $<_{n-1}$ έχει αντιαλυσίδα με $2^{n-2}+1$ στοιχεία. Περιοριζόμαστε σε αυτούς τους κύβους και με παρόμοιο τρόπο βρίσκουμε αντιαλυσίδα με $2^{n-3}+1$ στοιχεία για την μερική διάταξη $<_{n-2}$ .

Επαγωγικά καταλήγουμε σε 2^0 + 1 = 2

κύβους, έστω τους C,C'

, ώστε να αποτελούν αντιαλυσίδα για κάθε διάταξη <_k

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

MIPT 2013/2/3

MIPT 2013/2/3

Re: MIPT 2013/2/3

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