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

Ιουλίου 13, 2009

Περιγραφή ενός συνόλου μέσω πολυωνυμικών εξισώσεων

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

Ένας τρόπος να περιγράψει κανείς ένα σύνολο σημείων A \subseteq {\mathbb R}^n είναι μέσω κάποιων πολυωνυμικών εξισώσεων που το ορίζουν:

A = \{x \in {\mathbb R}^n: f_i(x) = 0, \forall i=1,2,\ldots,k\}

όπου τα f_i(x) είναι κάποια πολυώνυμα ως προς τις μεταβλητές x=(x_1,\ldots,x_n).

Για παράδειγμα το παρακάτω πολυωνυμικό σύστημα στο {\mathbb R}^3 περιγράφει κάποιο κύκλο στο χώρο:

x^2+y^2+z^2-1 = 0,\ x+y+z = 0.

Φυσικά δεν περιγράφονται όλα τα σύνολα με αυτό τον τρόπο.

Δείξτε ότι αν τα σύνολα A, B \subseteq {\mathbb R}^n περιγράφονται με αυτό τον τρόπο (είναι δηλ. το καθένα από αυτά το σύνολο λύσεων κάποιου συστήματος πολυωνυμικών εξισώσεων) τότε και η ένωση

A \cup B

περιγράφεται κατ’ αυτό τον τρόπο. (Είναι πολύ ευκολότερο να δείτε ότι η τομή A \cap B περιγράφεται από κάποιο πολυωνυμικό σύστημα.)

Ιουνίου 29, 2009

L-πλακόστρωση

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

Δείξτε ότι με ένα πλακάκι σχήματος L

l-shape

μπορείτε να πλακοστρώσετε ένα δωμάτιο 2^n \times 2^n το οποίο έχει μέσα μια 1×1 κολώνα (το πλάτος του κάθε τετραγώνου στο πλακάκι είναι 1, και η κολώνα βρίσκεται σε κάποια ακέραια θέση στο δωμάτιο με κάτω αριστερά γωνία (i,j), i,j \in {\mathbf Z}).

Ιουνίου 21, 2009

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

Κατηγορίες: Άλυτα Προβλήματα — Michalis Loulakis @ 12:44 μμ

Το ορθογώνιο τρίγωνο με πλευρές 6,8 και 10 έχει περιμέτρο 24 και εμβαδόν 24. Υπάρχουν λίγα ακόμα τρίγωνα με πλευρές που έχουν ακέραιο μήκος και περίμετρο ίση με το εμβαδόν τους. Βρείτε τα.

Ιουνίου 11, 2009

Είναι η ταυτοτική;

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

Έστω f:\mathbb R\to\mathbb R μια συνάρτηση τέτοια ώστε f(1)=1 και f(x+y)=f(x)+f(y) για κάθε x,y. Τι μπορείτε να πείτε για την f;
Υπάρχει μια προφανής f με αυτές τις ιδιότητες. Είναι η μοναδική; Προσέξτε ότι δεν κάνουμε καμία άλλη υπόθεση για την f. Επομένως θα πρέπει εσείς να μαντέψετε τους ασθενέστερους δυνατούς περιορισμούς ώστε το πρόβλημα να έχει απάντηση (αν φυσικά πιστεύετε ότι χρειάζονται κάποιοι περιορισμοί).

Ιουνίου 2, 2009

Θερινό Σχολείο Μαθηματικών 2009, Ηράκλειο

Κατηγορίες: Γενικά Σχόλια — Themis Mitsis @ 9:42 μμ

Μαΐου 24, 2009

Μηλιές και πορτοκαλιές

Κατηγορίες: Άλυτα Προβλήματα — Michalis Loulakis @ 10:52 πμ

Δύο αδέρφια κληρονομούν ένα κτήμα που έχει μέσα 2ν μηλιές και 2μ πορτοκαλιές. Μπορούν να το χωρίσουν με μια ευθεία έτσι ώστε ο καθένας να πάρει ακριβώς ν μηλιές και μ πορτοκαλιές;

Μαΐου 17, 2009

Πάμε στοίχημα;

Κατηγορίες: Λυμένα Προβλήματα — Michalis Loulakis @ 5:51 μμ

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

olympiakos-panathinaikos-cup-final

(περισσότερα…)

Μαΐου 16, 2009

Δύο γυναίκες, δύο άνδρες

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

Στις κορυφές Α, B, C, D ενός τετραγώνου με πλευρά 10m βρίσκονται δύο άνδρες (στις θέσεις A, C) και δύο γυναίκες (στις θέσεις B, D). Την ίδια στιγμή όλοι αρχίζουν να κινούνται προς το μέλος του άλλου φύλου που βρίσκεται στην επόμενη κορυφή δεξιόστροφα, δηλ. ο A προς την B, η B προς τον C, ο C προς την D και η D προς τον A. Σε κάθε χρονική στιγμή το κάθε άτομο κινείται απ’ ευθείας προς τον στόχο του και όλοι κινούνται με την ίδια ταχύτητα.

Πόσο συνολικά μήκος θα καλύψει το κάθε άτομο μέχρι που να βρει το στόχο του;

Μαΐου 14, 2009

Μιγαδικά πολυώνυμα

Κατηγορίες: Άλυτα Προβλήματα — Themis Mitsis @ 1:11 πμ

Υπάρχει ακολουθία μιγαδικών πολυωνύμων η οποία συγκλίνει κατά σημείο σε ασυνεχή συνάρτηση;

Μαΐου 13, 2009

Αδύνατη παρεμβολή

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

Γνωρίζουμε ότι αν μας δώσουν n διαφορετικούς πραγματικούς αριθμούς x_1,\ldots,x_n και n πραγματικές τιμές v_1,\ldots,v_n τότε μπορούμε να βρούμε ένα πολυώνυμο βαθμού το πολύ n-1

p(x) = \lambda_0 + \lambda_1 x + \cdots + \lambda_{n-1} x^{n-1}

το οποίο παρεμβάλει τις τιμές v_i στα σημεία x_i:

p(x_i) = v_i,\ \ i=1,2,\ldots,n.

Ένας άλλος τρόπος να πούμε το ίδιο πράγμα είναι ότι πάντα (για κάθε x_i, v_i, x_i διαφορετικά) μπορούμε να βρούμε ένα γραμμικό συνδυασμό των συναρτήσεων

u_1(x)=1, u_2(x)=x, u_3(x)=x^2, \ldots, u_n(x)=x^{n-1}

που παίρνει τις τιμές v_i στα x_i.

Δείξτε ότι αυτό δεν είναι δυνατό στο επίπεδο: για n \ge 2 δεν υπάρχουν συνεχείς συναρτήσεις u_1, \ldots, u_n:{\mathbb R}^2 \to {\mathbb R} τέτοιες ώστε για κάθε n σημεία x_1,\ldots,x_n \in {\mathbb R}^2 και κάθε n τιμές v_1, \ldots, v_n \in {\mathbb R} να υπάρχει γραμμικός συνδυασμός

F(x) = \lambda_1 u_1(x) + \cdots + \lambda_n u_n(x)

που να παρεμβάλει: F(x_i) = v_i για i=1, 2, \ldots, n.

Μαΐου 9, 2009

Μονομαχία

Κατηγορίες: Λυμένα Προβλήματα — Michalis Loulakis @ 11:01 πμ

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

duel_Bloch

Ο μαθηματικός που δεν σκαμπάζει πολύ από όπλα έχει πιθανότητα 0,3 να πετύχει το στόχο του κάθε φορά που πυροβολεί, ο αριστοκράτης έχει πιθανότητα 0,5 και ο κυνηγός δεν αστοχεί ποτέ. Τι πρέπει να κάνει ο μαθηματικός μας;

Μαΐου 8, 2009

Τρίγωνα

Κατηγορίες: Άλυτα Προβλήματα, Με υπόδειξη — Themis Mitsis @ 1:41 πμ

Δείξτε ότι κάθε υποσύνολο τού επιπέδου με άπειρο εμβαδό περιέχει τις κορυφές κάποιου τριγώνου με εμβαδό 1.

Μαΐου 7, 2009

Μονά-ζυγά

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

Το παρακάτω πρόβλημα προτάθηκε από το Δημήτρη Χριστοφίδη:

Να βρεθεί το μέγιστο n ώστε να υπάρχουν σύνολα A_1,\ldots,A_n \subseteq \{1,2,\ldots,2009\} τέτοια ώστε

  • το κάθε ένα από αυτά να έχει περιττό μέγεθος, και
  • η τομή οποιωνδήποτε δύο διαφορετικών από αυτά να έχει άρτιο μέγεθος.

Κανονικά πολύγωνα

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

Οι κορυφές ενός κανονικού N-γώνου χρωματίζονται με διάφορα χρώματα με τρόπο τέτοιο ώστε για κάθε ένα από τα χρώματα που χρησιμοποιήθηκαν, έστω το χρώμα \chi, το σύνολο των κορυφών που είναι βαμμένες με το χρώμα \chi είναι επίσης ένα κανονικό πολύγωνο το οποίο συμβολίζουμε με P(\chi).

Δείξτε ότι υπάρχουν δύο χρώματα \chi και \psi τέτοια ώστε τα πολύγωνα P(\chi), P(\psi) είναι το ένα στροφή του άλλου (ισοδύναμα, έχουν το ίδιο πλήθος κορυφών).

Απριλίου 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^{*}.

Επόμενη σελίδα: »

Blog στο WordPress.com.