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

Μαρτίου 31, 2008

Star Wars

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Themis Mitsis @ 11:31 πμ

Ο Luke Skywalker βρίσκεται σε μια κυκλική πισίνα διαμέτρου 20 μέτρων, ακουμπισμένος σε κάποιο σημείο της περιφέρειάς της. Είναι εξαντλημένος και έτσι όταν θέλει να κινηθεί είναι αναγκασμένος να κολυμπάει κολλητά με την περιφέρεια για να μπορεί να κρατιέται. Στο ίδιο σημείο έξω από την πισίνα στέκεται ο Darth Vader με ένα ψηφιακό μετρητή ταχύτητας και ένα όπλο εμβέλειας 19.99 μέτρων. Ο άκαρδος πατέρας θα πυροβολήσει μόλις ο γιος του πάει να βγει από την πισίνα. Όταν ο Luke κινείται (πάντα κατά μήκος της περιφέρειας) ο Vader αμέσως μετράει την ταχύτητά του και τον ακολουθεί «κατά πόδα» έξω από την πισίνα με την ταχύτητα που δείχνει ο μετρητής. Δείξτε ότι ο Luke μπορεί να βγει σώος από την πισίνα (το τί θα κάνει μετά είναι άλλο πρόβλημα). Η Αυτοκρατορία έχει πολύ υψηλή τεχνολογία, αλλά τα ψηφιακά όργανα παραμένουν ψηφιακά σε ολόκληρο το γαλαξία και έχουν ΠΕΠΕΡΑΣΜΕΝΗ ακρίβεια, ας πούμε 100 δεκαδικά ψηφία.

Μαρτίου 28, 2008

Συνεκτικότητα

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Themis Mitsis @ 10:44 μμ

Θέτουμε A=\mathbb R^2\smallsetminus\mathbb Q^2, δηλαδή από το επίπεδο αφαιρούμε τα σημεία των οποίων και οι δυο συντεταγμένες είναι ρητοί αριθμοί. Κατ’ αρχάς βεβαιωθείτε ότι κάθε δύο σημεία του A μπορούν να συνδεθούν με μια καμπύλη που βρίσκεται μέσα στο A και στη συνέχεια για κάθε x,y\in A υπολογίστε το infimum των μηκών των καμπύλων που συνδέουν τα x και y.

Μαρτίου 27, 2008

Μία ορθογώνια σοκολάτα

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 11:25 μμ

Έχουμε μια ορθογώνια σοκολάτα που αποτελείται από τετραγωνάκια τοποθετημένα σε m γραμμές και n στήλες. Το τετραγωνάκι όμως της πάνω αριστερά γωνίας (και μόνο αυτό) είναι φτιαγμένο από σαπούνι αντί για σοκολάτα.

Δύο παίκτες παίζουν το ακόλουθο παιχνίδι: Όταν έρθει η σειρά κάποιου παίκτη αυτός κόβει ένα κομμάτι σοκολάτα και το τρώει. Η m\times n σοκολάτα μπορεί να κοπεί είτε οριζόντια είτε κάθετα αλλά πλήρως, δηλ.\ αν η σοκολάτα κοπεί οριζόντια τότε αυτή χωρίζεται σε δύο ορθογώνιες σοκολάτες, μια k\times n και μια (m-k)\times n, και ο παίκτης διαλέγει και τρώει ένα από τα δύο ορθογώνια κομμάτια. Ομοίως, αν η σοκολάτα κοπεί κάθετα τότε χωρίζεται σε δυο κομμάτια, ένα m\times k και ένα m\times (n-k). Χάνει ο παίκτης που αναγκάζεται να φάει το τετραγωνάκι με το σαπούνι.

Θα θέλατε να παίζατε πρώτος ή δεύτερος; Η απάντηση εξαρτάται από τα m και n.

Μαρτίου 26, 2008

Όρια ορίων και η χαρακτηριστική των ρητών

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Themis Mitsis @ 1:27 μμ

Βρείτε απείρως παραγωγίσιμες συναρτήσεις f_{n,m}:\mathbb R\to\mathbb R, m,n\in\mathbb N, τέτοιες ώστε

\displaystyle\lim_{m\to\infty}\left[\lim_{n\to\infty}f_{n,m}(t)\right]=\chi_{\mathbb Q}(t),\quad\forall t\in\mathbb R,

όπου \chi_{\mathbb Q} είναι η χαρακτηριστική συνάρτηση του \mathbb Q, δηλαδή παίρνει την τιμή 1 σε κάθε ρητό και την τιμή 0 σε κάθε άρρητο. Τα διαδοχικά όρια δεν εμφανίζονται από «βίτσιο». Δεν υπάρχει ακολουθία συνεχών συναρτήσεων η οποία να συγκλίνει κατά σημείο στην \chi_{\mathbb Q}. Αυτό είναι άμεσο πόρισμα του Θεωρήματος xyz το οποίο μάλλον δεν το έχετε συναντήσει στις προπτυχιακές σας σπουδές, έτσι δεν έχει νόημα να το αναφέρω. Δεν έχω σκεφτεί αν υπάρχει κάποια στοιχειώδης απόδειξη. Το ότι δεν υπάρχει ακολουθία συνεχών συναρτήσεων η οποία να συγκλίνει ομοιόμορφα στην \chi_{\mathbb Q} είναι, φυσικά, προφανές

Πρόβλημα κάλυψης με διαστήματα

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 12:58 πμ

Δίνεται μια ακολουθία διαστημάτων I_j = (a_j, b_j), j=1,2,\cdots, και έστω

\displaystyle U = \bigcup_{j=1}^\infty I_j.

Υποθέστε επίσης ότι η ακολουθία b_j - a_j συγκλίνει στο 0 κατά φθίνοντα τρόπο.
Δείξτε ότι μπορεί κανείς να επιλέξει μια υπακολουθία από τα I_j που να είναι ξένα ανά δύο και που αν κανείς τα τριπλασιάσει (κρατήσει δηλ.\ το κέντρο ενός διαστήματος το ίδιο και τριπλασιάσει το μήκος του) καλύπτουν το U.

Μαρτίου 25, 2008

Τροχιά ακολουθίας

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 8:28 μμ

plot1

 

Στο παραπάνω σχήμα φαίνονται οι 31 πρώτοι όροι της μιγαδικής ακολουθίας

\displaystyle ne^{2\pi ien!},\quad n=0,1,2,\dots

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

 

plot2.jpg

Εδώ η κατάσταση δείχνει χαοτική. Αυτό που μοιάζει με καμπύλη περιέχει τους 31 όρους του πρώτου σχήματος (σε άλλη κλίμακα). Τί ακριβώς πάει στραβά;

Ώρα σε Λονδίνο, Νέα Υόρκη, Ζυρίχη, Τόκυο …

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 4:16 μμ

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

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

Περιφερειακός

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 4:13 μμ

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

Πόσο αρνητικό πρέπει να γίνει ένα άθροισμα συνημιτόνων

Έστω \lambda_1, \ldots, \lambda_N \in {\mathbf N} και υποθέστε ότι a, \epsilon>0, είναι τέτοια ώστε

\lambda_1, \ldots, \lambda_N \in ((1+\epsilon) a, 2 (1-\epsilon) a).

Ορίστε

f(x) = \sum_{j=1}^N \cos(\lambda_j x).

Δείξτε ότι υπάρχει συνάρτηση A(\epsilon)>0 τέτοια ώστε

\min_{x \in {\mathbf R}} f(x) \le -A(\epsilon) N.

Μαρτίου 24, 2008

Αθροίσματα και ολοκληρώματα

Ας ονομάσουμε μια συνάρτηση «στοιχειώδη» αν είναι πεπερασμένος συνδυασμός δυνάμεων, εκθετικών, λογαριθμικών ή τριγωνομετρικών συναρτήσεων. Για παράδειγμα οι
\displaystyle 2^{\sin x},\quad \frac{\ln x}{1+x^2}
είναι στοιχειώδεις. Βρείτε μια στοιχειώδη συνάρτηση f:[0,\infty)\to\mathbb R τέτοια ώστε:
\displaystyle\sum_{n=1}^\infty f(n)=\int_0^1f(x)\, dx.

Πόσους ελέγχους;

Filed under: Λυμένα Προβλήματα,Με επιπλέον ερωτήματα — Mihalis Kolountzakis @ 12:19 πμ

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

Γι’ αυτό το λόγο το εργαστήριο δημιουργεί N μίγματα από τα 100 μπουκάλια που θέλει να ελέγξει και στέλνει αυτά τα N δείγματα σε ένα εργαστήριο στην Αμερική το οποίο στέλνει πίσω τις απαντήσεις. (Τα ταχυδρομικά είναι επίσης πανάκριβα, οπότε το εργαστήριο στέλνει και τα N μίγματα με μια αποστολή.)

Αν κάποιο από αυτά τα μίγματα προκύψει θετικό αυτό σημαίνει ότι κάποιο από τα μπουκάλια που χρησιμοποιήθηκαν στο μίγμα αυτό είναι μολυσμένο.

Ποιος είναι ο ελάχιστος αριθμός μιγμάτων N που πρέπει να στείλει το εργαστήριο για να βρει τη μολυσμένη φιάλη;

Μαρτίου 20, 2008

Ποιο πολυώνυμο;

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 1:17 πμ

Ένα πολυώνυμο P(x) έχει μη αρνητικούς ακέραιους συντελεστές. Βρείτε ποιο είναι το πολυώνυμο αυτό ρωτώντας μόνο δύο ερωτήσεις του τύπου «Πόσο είναι το P(x), για όποιες δύο ακέραιες τιμές του x θέλετε; Δείξτε επίσης ότι μπορείτε να «αποφασίσετε¨ ποιο είναι το P(x) με μόνο μια ερώτηση «Πόσο είναι το P(x) αλλά με x όχι αναγκαστικά ρητό αριθμό.

Μαρτίου 16, 2008

Ν σωμάτια πάνω σε μια ράβδο

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 12:26 μμ

Σε μια ράβδο μήκους L βρίσκονται, τη χρονική στιγμή t=0, N σωμάτια καθένα από τα οποία κινείται ελεύθερα. Η ταχύτητα κάθε σωματίου είναι 1 ή -1. Αν ένα σωμάτιο φτάσει σε ένα από τα δύο άκρα της ράβδου τότε πέφτει και χάνεται. Αν δύο σωμάτια συγκρουστούν τότε το καθένα από τα δύο γυρνάει και κινείται ανάποδα απ’ ό,τι πριν, πάλι με ταχύτητα 1.

Ποιος είναι ο μέγιστος χρόνος που μπορεί να περάσει πριν πέσουν όλα τα σωμάτια από τη ράβδο;

Μαρτίου 12, 2008

Τύπος για Εμβαδό Πολυγώνου

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 8:08 μμ

Η παρακάτω είναι μια πραγματικά χρήσιμη άσκηση.

Ένα πολύγωνο P του επιπέδου περιγράφεται μέσω της ακολουθίας των κορυφών του

(x_0, y_0), \ldots, (x_{N-1}, y_{N-1}),

όπου κάθε κορυφή i συνδέεται με τις i\pm 1 \bmod N.

Βρείτε ένα τύπο για το εμβαδό του P μέσω των x_i, y_i, i=0,\ldots,N-1.

Κατόπιν βρείτε κι ένα τύπο για το κέντρο βάρους του πολυγώνου (όχι των κορυφών του).

Στρατηγική απελευθέρωσης

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 10:08 πμ

Σε μια φυλακή υπάρχουν 2n βαρυποινίτες (n μεγάλο).
Ο διευθυντής της φυλακής αποφασίζει να παίξει ένα σκληρό παιχνίδι μαζί τους:

Σ’ ένα δωμάτιο μέσα υπάρχουν 2n κλειστά κουτιά και μέσα στα κουτιά υπάρχουν τα ονόματα των 2n κρατουμένων, ένα όνομα σε κάθε κουτί, σε θέσεις που είναι άγνωστες στους κρατουμένους. Οι κρατούμενοι μπαίνουν ένας-ένας μέσα στο δωμάτιο, μόνοι τους, και ανοίγουν n κουτιά, τα οποία επιλέγουν αυτοί. Αν μέσα στα n αυτά κουτιά υπάρχει το όνομα του κρατουμένου που τα ανοίγει τότε αυτός, αφού ξανακλείσει όλα τα κουτιά χωρίς να πειράξει τα περιεχόμενά τους, βγαίνει έξω και μπαίνει ο επόμενος.

Αν βγει έξω και ο τελευταίος τότε όλοι οι κρατούμενοι απελευθερώνονται.

Αν όχι τότε το παιχνίδι σταματάει και όλοι οι κρατούμενοι εκτελούνται.

Οι κρατούμενοι μπορούν να συννενοηθούν για το ποια στρατηγική θα ακολουθήσουν πριν αρχίσει το παιχνίδι αλλά απαγορεύεται να ανταλλάξουν οποιαδήποτε πληροφορία αφού αρχίσει το παιχνίδι.

Είναι φανερό ότι αν κάθε κρατούμενος μπει μέσα και ανοίξει n κουτιά στην τύχη τότε η πιθανότητα να βρεί το δικό του όνομα είναι 1/2, άρα η πιθανότητα να επιζήσουν οι κρατούμενοι, αν παίζουν με αυτό τον τρόπο, είναι 2^{-n}, που πηγαίνει στο 0 απελπιστικά γρήγορα.

Δείξτε ότι οι κρατούμενοι μπορούν να επιλέξουν να παίξουν με μια στρατηγική που τους εγγυάται πιθανότητα επιβίωσης η οποία δε συγκλίνει στο 0 με το n \to \infty.

Πλήθος λέξεων από 0 και 1

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 10:08 πμ

Έστω f:{\mathbf Z}\to\{0,1\} και n\ge 1 φυσικός αριθμός τ.ώ. το πλήθος των λέξεων

f(x) f(x+1) \cdots f(x+n-1),\ \ \ x \in {\mathbf Z},

είναι \le n.
Δείξτε ότι η συνάρτηση f είναι περιοδική, ότι υπάρχει δηλαδή ακέραιος T\neq 0 ώστε
f(x+T) = f(x), για κάθε x\in {\mathbf Z}.

Κάλυψη ευθείας

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 9:51 πμ

Έστω \epsilon>0 και

A = {\bf Z}+(-\epsilon,\epsilon) = \bigcup_{n \in {\bf Z}} (n-\epsilon, n+\epsilon).

Υπάρχει πεπερασμένο σύνολο \Lambda=\{\lambda_1,\ldots,\lambda_k\} από θετικούς αριθμούς τέτοιο ώστε

{\bf R} \subset \bigcup_{j=1}^k \lambda_j A;

Συμβολίζουμε εδώ \lambda A = \{\lambda a: a \in A\}.

Μια στήλη από τούβλα

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 9:43 πμ

Σας δίνεται ένα άπειρο πλήθος από ίδια ορθογώνια τούβλα, διαστάσεων 30 \times 10 \times 10 cm.
Δείξτε ότι μπορείτε να φτιάξετε μία στήλη από αυτά η οποία

  1. να ισορροπεί,
  2. να έχει ένα τούβλο σε κάθε οριζόντιο επίπεδο και
  3. προβαλλόμενη κατακόρυφα κάτω να φτάνει 100 m μακριά.

Προσπαθείστε να δώσετε μια λύση χωρίς πράξεις, στηριζόμενοι σε «φυσικά» επιχειρήματα.

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: