Προβλήματα Μαθηματικών

Απριλίου 30, 2009

Σχέσεις

Κατηγορίες: Λυμένα Προβλήματα, Με επιπλέον ερωτήματα, Με υπόδειξη — Mihalis Kolountzakis @ 11:48 πμ

Αν είναι A ένας k \times k πραγματικός πίνακας και i, j δύο ακέραιοι από 1 έως και k, και ορίσουμε την ακολουθία

x_n = (A^n)_{i,j}  (το i,j στοιχείο της n-οστής δύναμης του A)

δείξτε ότι η ακολουθία x_n ικανοποιεί μια γραμμική αναδρομική σχέση:

x_n = a_1 x_{n-1} +\cdots +a_r x_{n-r}

όπου r είναι φυσικός αριθμός και a_1,\ldots,a_r πραγματικοί αριθμοί.

Απριλίου 29, 2009

Πεπερασμένο-προς-ένα

Κατηγορίες: Λυμένα Προβλήματα — Themis Mitsis @ 12:13 πμ

Υπάρχει ομαλή συνάρτηση f:\mathbb R^n\to\mathbb R η οποία να παίρνει κάθε τιμή της πεπερασμένο πλήθος φορές;

Απριλίου 26, 2009

Διαχωρισιμότητα

Κατηγορίες: Λυμένα Προβλήματα — Themis Mitsis @ 9:44 μμ

Ένας μετρικός χώρος λέγεται διαχωρίσιμος αν έχει αριθμήσιμο και πυκνό υποσύνολο. Για παράδειγμα, οι πραγματικοί και οι συνεχείς συναρτήσεις σ’ ένα κλειστό διάστημα είναι διαχωρίσιμοι χώροι. Οι φραγμένες ακολουθίες δεν είναι.
Είναι σχετικά εύκολο να δείξει κανείς ότι ένας διαχωρίσιμος χώρος έχει την ακόλουθη ιδιότητα την οποία, για μυστηριώδεις λόγους, θα ονομάσουμε ccc:

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

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

Το ερώτημα είναι αν ισχύει το αντίστροφο: Αν ένας χώρος έχει την ccc τότε είναι διαχωρίσιμος;

Απριλίου 25, 2009

Μονόδρομοι

Κατηγορίες: Άλυτα Προβλήματα, Με υπόδειξη — Michalis Loulakis @ 3:37 πμ

Θεωρήστε ένα πλήρες γράφημα (οποιεσδήποτε δυό κορυφές συνδέονται με ακμή.) Προσανατολίζουμε τις ακμές του γραφήματος επιτρέποντας την κίνηση ανάμεσα σε δύο κορυφές μόνο κατά τη μια φορά. Δείξτε ότι αν το πλήθος των κορυφών του γραφήματος n δεν είναι 2 ή 4 είναι δυνατό να προσανατολίσουμε τις ακμές έτσι ώστε να μπορεί κανείς να πάει από οποιαδήποτε κορυφή σε οποιαδήποτε άλλη περνώντας ενδιάμεσα από μια το πολύ άλλη κορυφή.

Σημείωση: Όποιος λύσει το πρόβλημα “Ικανοποίηση” σίγουρα δεν θα έχει πρόβλημα να λύσει και αυτό το πρόβλημα στην περίπτωση που n>20.

Απριλίου 16, 2009

Ικανοποίηση

Κατηγορίες: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 10:50 μμ

Έστω k ένας φυσικός αριθμός και μια λογική έκφραση

C_1 \wedge \cdots \wedge C_n

όπου κάθε ένα από τα C_i, i=1,\ldots,n, είναι της μορφής

y_1 \vee \cdots \vee y_k

όπου κάθε y_j είναι είτε x_\nu είτε \overline{x_\nu}. Τα x_\nu, \nu=1,2,\ldots, είναι λογικές μεταβλητές, είναι δηλ. είτε αληθείς είτε ψευδείς.

Παράδειγμα μιας τέτοιας έκφρασης με k=3 είναι η

(x_1 \vee \overline{x_2} \vee x_3) \wedge (\overline{x_1} \vee x_3 \vee x_4).

Αν n<2^k δείξτε ότι η λογική έκφραση είναι ικανοποιήσιμη, μπορούμε δηλ. να αναθέσουμε τιμές (αληθής ή ψευδής) σε κάθε μια από τις λογικές μεταβλητές x_\nu ώστε κάθε ένα από τα C_j να είναι αληθές.

Απριλίου 15, 2009

Ανισότητα αναδιάταξης

Κατηγορίες: Άλυτα Προβλήματα, Με υπόδειξη — Michalis Loulakis @ 10:33 πμ

Έστω P ένας n\times n πίνακας με μη αρνητικά στοιχεία (p_{ij})_{1\le i,j\le n} τέτοια ώστε

\displaystyle \sum_{i=1}^n p_{ij}=1 για κάθε j=1,2,...,n      και      \displaystyle \qquad \sum_{j=1}^n p_{ij}=1 για κάθε i=1,2,...,n.

Αν x\in\mathbb{R}^n συμβολίζουμε με x^{*} (αντίστοιχα x_*) το διάνυσμα που προκύπτει από το x αν αναδιατάξουμε τις συντεταγμένες του με αύξουσα (αντίστοιχα φθίνουσα) σειρά. Δείξτε ότι για κάθε x,y\in\mathbb{R}^n έχουμε

\displaystyle x^*\cdot y_*\le \sum_{i,j=1}^n p_{ij}x_iy_j\le x^{*}\cdot y^{*}.

Απριλίου 10, 2009

Τελωνειακός έλεγχος

Κατηγορίες: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 11:54 μμ

douane

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

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

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

Όμως δεν ξέρει. Κατά τη διάρκεια της ημέρας φθάνουν αντικείμενα για επεξεργασία στην υπηρεσία του απροειδοποίητα και δεν έχει χώρο να κρατήσει πάνω από 100 αντικείμενα στην αποθήκη του.

Τι θα πρέπει να κάνει;

Απριλίου 5, 2009

Σταθερά σημεία

Κατηγορίες: Λυμένα Προβλήματα — Themis Mitsis @ 10:37 μμ

Η ταυτοτική συνάρτηση f(z)=z είναι ένα (τετριμμένο) παράδειγμα μιας αναλυτικής (=παραγωγίσιμης=ολόμορφης) συνάρτησης από τον ανοιχτό μοναδιαίο δίσκο στον εαυτό του η οποία έχει περισσότερα από ένα σταθερά σημεία, δηλαδή σημεία με την ιδιότητα f(a)=a. Υπάρχει άλλη τέτοια συνάρτηση;

Απριλίου 4, 2009

Ομαλότητα και φορέας

Κατηγορίες: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 9:04 πμ

Αν F είναι ένα κλειστό σύνολο στο {\mathbb R}^n τότε η συνεχής συνάρτηση

f(x) = {\rm dist}(x, F)

μηδενίζεται ακριβώς πάνω στο F.

Υπάρχει πάντα μια ομαλή συνάρτηση f (δηλ. με άπειρες παραγώγους ως προς όλες τις μεταβλητές σε όλο το {\mathbb R}^n) που να μηδενίζεται ακριβώς στο F;

Blog στο WordPress.com.