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

Οκτωβρίου 19, 2012

Υπολογίστε γρήγορα τους αριθμούς Fibonacci

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

Αν θέλουμε να υπολογίσουμε γρήγορα τη δύναμη K^n ενός φυσικού αριθμού K (όπου ο εκθέτης n είναι ένας πολύ μεγάλος αριθμός) τότε δε χρειάζεται να κάνουμε n πολλαπλασιασμούς. Αρκούν O(\log n) αριθμητικές πράξεις (πάντα μεταξύ ακεραίων): η πιο απλή περίπτωση όπου αυτό φαίνεται είναι όταν n=2^r είναι δύναμη του 2. Τετραγωνίζοντας κάθε φορά το προηγούμενό μας αποτέλεσμα μπορούμε με r=O(\log n) πράξεις να πάρουμε το αποτέλεσμά μας.

Βρείτε ένα αντίστοιχα γρήγορο τρόπο υπολογισμού του n-οστού αριθμού Fibonacci F_n. Οι αριθμοί Fibonacci ορίζονται από τον αναδρομικό τύπο:

F_n = \begin{cases} 1 & (n=1,2)\\ F_{n-1}+F_{n-2} & (n\ge 3).\end{cases}

Μόνο πράξεις ανάμεσα σε ακεραίους είναι επιτρεπτές.

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

Σεπτεμβρίου 27, 2012

Περιστρεφόμενοι δίσκοι

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

Σε κάθε ακέραιο σημείο του επιπέδου (m,n), με m,n\in{\mathbb Z}, έχουμε κεντράρει ένα δίσκο ακτίνας \epsilon>0 γεμάτο με μπλε μελάνι. Έπειτα περιστρέφουμε όλους αυτούς τους δίσκους μαζί γύρω από την αρχή των αξόνων κατά μια ολόκληρη περιστροφή (ούτως ώστε κάθε δίσκος γράφει ένα κύκλο στο επίπεδο και επιστρέφει στην αρχική του θέση). Απ’ όπου περνάει ο κάθε δίσκος αφήνει ένα μπλε ίχνος όπου ακουμπήσει.

Δείξτε ότι υπάρχει κάποια πεπερασμένη ακτίνα R ούτως ώστε έξω από τον κύκλο με κέντρο το (0,0) και ακτίνα R τα πάντα είναι μπλέ.

Νοεμβρίου 24, 2011

Γινόμενα πινάκων

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

Ας είναι A, B \in {\mathbb C}^{n \times n} δύο n \times n πίνακες με μιγαδικά στοιχεία. Για ένα γινόμενο αυτών των πινάκων της μορφής

A^{a_1}B^{b_1}A^{a_2}B^{b_2}\cdots A^{a_r}B^{b_r}, με a_j, b_j \ge 0

ονομάζουμε την ποσότητα a_1+b_1+a_2+b_2+\cdots+a_r+b_r συνολικό εκθέτη του γινομένου.

Δείξτε ότι υπάρχει ένας φυσικός αριθμός N τέτοιος ώστε κάθε γινόμενο των πινάκων A, B όπως παραπάνω μπορεί να γραφεί σα γραμμικός συνδυασμός τέτοιων γινομένων που το κάθε ένα τους έχει συνολικό εκθέτη το πολύ N.

Νοεμβρίου 12, 2011

Έχουν σημασία οι διαστάσεις;

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

Είναι οι προσθετικές ομάδες {\mathbb Q} και {\mathbb Q}^2 ισόμορφες ή όχι; Οι {\mathbb R} και {\mathbb R}^2;

Σεπτεμβρίου 3, 2010

Καμπυλόγραμμα τρίγωνα

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — Michalis Loulakis @ 3:55 μμ

(Την άσκηση αυτή πρότεινε ο Βασίλης Βισκαδουράκης) Τρεις κύκλοι στο επίπεδο τέμνονται όπως στο παρακάτω σχήμα. Δείξτε ότι οι τρεις ευθείες ΑΑ’, ΒΒ’, CC’ που ορίζουν τα σημεία τομής κάθε ζευγαριού κύκλων συντρέχουν, και ότι όλα τα καμπυλόγραμμα τρίγωνα που σχηματίζονται έχουν άθροισμα γωνιών μεγαλύτερο από 2 ορθές.

Μπορείτε να αλλάξετε τη σχετική θέση των τριών κύκλων, έτσι ώστε όλα τα καμπυλόγραμμα τρίγωνα που σχηματίζονται να έχουν άθροισμα γωνιών μικρότερο από δύο ορθές;

Ιουλίου 17, 2010

Πυκνή τροχιά

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

Έστω X=\ell^2({\mathbb N}) ο γραμμικός χώρος όλων των πραγματικών ακολουθιών a=(a_1, a_2, \ldots) με

\|a\| := \sqrt{a_1^2+a_2^2+\cdots} < \infty.

Ο γραμμικός χώρος X είναι και μετρικός με τη μετρική d(a,b)=\|a-b\|. Ορίζουμε τη γραμμική απεικόνιση

T:X\to X,\ \ T(a) = (2a_2, 2a_3, 2a_4, \ldots)

(σπρώχνουμε όλες τις συντεταγμένες του διανύσματος μία θέση προς τα αριστερά και μετά τις πολλαπλασιάζουμε όλες επί 2).

Δείξτε ότι υπάρχει διάνυσμα a \in X τέτοιο ώστε το σύνολο (τροχιά)

a, T(a), T^2(a)=T(T(a)), T^3(a), \ldots

να είναι πυκνό στον X, δηλ. για κάθε σημείο x\in X υπάρχει υπακολουθία της τροχιάς του a που συγκλίνει στο x.

Ιουνίου 7, 2010

Πώς να βρείτε αν μια ομάδα δεν είναι αβελιανή (αντιμεταθετική)

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

Μια ομάδα G με N στοιχεία σας δίνεται μέσω του πίνακα πολλαπλασιασμού της M. Αν τα στοιχεία της ομάδας είναι τα g_1, g_2, \ldots, g_N τότε το (i,j) στοιχείο του N\times N πίνακα M είναι το k αν και μόνο αν g_i g_j = g_k.

Αν για κάποια i,j έχουμε M_{i,j} \neq M_{j,i} τότε προκύπτει φυσικά ότι η ομάδα δεν είναι αντιμεταθετική.

Αν σας δώσουν μια ομάδα με τεράστιο N και αν για κάθε φορά που ζητάτε να μάθετε το στοιχείο M_{i,j} πληρώνετε ένα ευρώ βρείτε ένα τρόπο να ελέγχετε αν η ομάδα είναι αντιμεταθετική χωρίς να κάνετε πολλούς ελέγχους.

Είναι αποδεκτό να κάνετε λάθος, το να συμπεράνετε δηλ. ότι η ομάδα είναι αβελιανή ενώ δεν είναι, αλλά αυτό πρέπει να συμβαίνει με πολύ μικρή πιθανότητα, ας πούμε 10^{-6}.

Η μέθοδός σας μπορεί να χρησιμοποιεί τυχαίους αριθμούς.

Μαΐου 9, 2010

Κόψτε τα όλα στη μέση

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

Δίνονται τρία σύνολα στον χώρο, και υποθέτουμε ότι έχουν πεπερασμένο όγκο. Είναι αλήθεια ότι υπάρχει ένα επίπεδο το οποίο να χωρίζει καθένα από τα σύνολα σε δυο υποσύνολα ίσου όγκου; Με άλλα λόγια, μπορείτε να τα κόψετε όλα στη μέση με μια μαχαιριά;

Απριλίου 21, 2010

Μόνο για μαζοχιστές

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

Υπολογίστε το όριο

\displaystyle\lim_{n\to+\infty}\frac{(n!)^2}{(2n)!}\sum_{k=1}^n\binom{n}{k}^2\frac{1}{k}.

Φεβρουαρίου 15, 2010

Διαταραχές πινάκων

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — Michalis Loulakis @ 7:56 μμ

Θεωρήστε δύο πραγματικούς συμμετρικούς n\times n πίνακες A, B με ιδιοτιμές \lambda_1\le\cdots\le\lambda_n και \mu_1\le\cdots\le\mu_n, αντίστοιχα. Ας συμβολίζουμε με \rho_i τις ιδιοτιμές του πίνακα A-B. Δείξτε ότι

\displaystyle \sum_{k=1}^n (\lambda_k-\mu_k)^2\le\sum_{k=1}^n\rho_k^2\le\sum_{k=1}^n(\lambda_k-\mu_{n-k})^2.

Ιανουαρίου 7, 2010

Φωτισμός δωματίου

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

Σ’ ένα νέο και μοντέρνο κτήριο μια αίθουσα έχει πολυγωνική κάτοψη (όχι κατ’ ανάγκη κυρτή). Η μοντέρνα αισθητική επιβάλλει τα φώτα να τοποθετηθούν στις γωνίες μόνο τις αίθουσας (κορυφές του πολυγώνου). Δείξτε ότι αν η αίθουσα έχει N γωνίες τότε αρκούν \lfloor N/3 \rfloor φώτα για το φωτισμό της αίθουσας.

Νοεμβρίου 11, 2009

Μη αρνητικά πολυώνυμα

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

Είναι εύκολο να δει κανείς (γιατί;) ότι οποιοδήποτε πολυώνυμο σε μια μεταβλητή με πραγματικούς συντελεστές f(x) \in {\mathbb R}[x] είναι μη αρνητικό για κάθε x \in {\mathbb R} γράφεται αναγκαστικά σα άθροισμα τετραγώνων πολυωνύμων

f(x) = \sum_{j=1}^N (p_j(x))^2, με p_j(x) \in {\mathbb R}[x].

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

Έστω F(x,y) = x^2y^2(x^2+y^2-3)+1. Δείξτε ότι το F(x, y) είναι πάντα μη αρνητικό αλλά δε μπορεί να γραφεί σα άθροισμα τετραγώνων πολυωνύμων σε x, y. Άρα η παραπάνω ισοδυναμία δεν ισχύει παρά μόνο για πολυώνυμα μιας μεταβλητής.

Νοεμβρίου 6, 2009

Οριακή κανονικότητα

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

Επιλέγουμε τυχαία ένα σημείο στην επιφάνεια της σφαίρας του \mathbb{R}^n με κέντρο το 0 και ακτίνα \sqrt{n}. Αν \mathbb{P}_n[a,b] είναι η πιθανότητα η πρώτη συντεταγμένη του σημείου να είναι στο διάστημα [a,b] δείξτε ότι

\displaystyle \mathbb{P}_n[a,b]\to\frac{1}{\sqrt{2\pi}}\int_a^b e^{-\frac{u^2}{2}} du.

Οκτωβρίου 10, 2009

Πώς να αλλάξετε τα πρόσημα

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

Έχουμε ένα m\times n πίνακα με στοιχεία πραγματικούς αριθμούς. Σας επιτρέπεται σε κάθε βήμα να πολλαπλασιάζετε κάθε γραμμή ή στήλη του πίνακα με -1 (να αλλάζετε δηλ. όλα τα πρόσημα σε αυτή τη γραμμή ή στήλη). Δείξτε ότι μπορείτε με αυτό τον τρόπο να πετύχετε κάθε γραμμή και κάθε στήλη του πίνακα να έχει άθροισμα \ge 0.

Σεπτεμβρίου 14, 2009

Σημεία και ευθείες

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

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

Αυγούστου 30, 2009

Πέντε σημεία

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — Michalis Loulakis @ 2:31 πμ

Είναι δυνατόν να βρούμε 5 σημεία στο χώρο, τέτοια ώστε οι όγκοι των 5 τετραέρδων που ορίζουν να είναι ίσοι και μη μηδενικοί;

Αυγούστου 6, 2009

Λίγο Απειροστικός

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

Έστω f:\mathbb{R}\mapsto\mathbb{R} μια συνάρτηση τέτοια ώστε για κάποιο φυσικό k

\displaystyle \lim_{x\to\infty}f(x)=\lim_{x\to\infty}f^{(k)}(x)=0.

Δείξτε ότι \displaystyle \lim_{x\to\infty}f^{'}(x)=\cdots=\lim_{x\to\infty}f^{(k-1)}(x)=0.

Αυγούστου 5, 2009

Το πέμπτο χαρτί

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

four-cards

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

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

Ιουλίου 21, 2009

Τομές συνόλων

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

Ας είναι A_j \subseteq X,\ j=1,2,\ldots,N, κάποια σύνολα μεγέθους k το καθένα, τέτοια ώστε η τομή οποιωνδήποτε k+1 από τα σύνολα A_j είναι μη κενή.

Τότε και η τομή όλων των A_j είναι μη κενή.

Μαΐου 16, 2009

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

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

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

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

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

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

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