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

Νοεμβρίου 30, 2008

Αντι-παράγωγος

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

Είναι η χαρακτηριστική συνάρτηση των ρητών (1 στους ρητούς, 0 στους άρρητους) παράγωγος κάποιας συνάρτησης;

Νοεμβρίου 29, 2008

Γραμμικός προγραμματισμός

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

Ένα γραμμικό πρόγραμμα είναι ένα πρόβλημα βελτιστοποίησης του εξής τύπου:

Ελαχιστοποίηση του εσωτερικού γινομένου {c^\top x}, υπό τους περιορισμούς

{A x \ge b}

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

Νοεμβρίου 26, 2008

Peer to peer

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

Δέκα άνθρωποι σ’ ένα χωριό γνωρίζουν από ένα διαφορετικό κουτσομπολιό. Κάθε φορά που δύο από αυτούς επικοινωνούν μεταξύ τους τηλεφωνικά ανταλλάσουν τα κουτσομπολιά που ξέρουν. Ποιός είναι ο ελάχιστος αριθμός τηλεφωνημάτων που πρέπει να γίνουν ώστε όλοι να μάθουν όλα τα κουτσομπολιά;

Νοεμβρίου 21, 2008

Συναρτησιακή εξίσωση

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

Βρείτε όλες τις αναλυτικές (δηλαδή παραγωγίσιμες) συναρτήσεις f:\mathbb C\to\mathbb C που ικανοποιούν τη σχέση

f(zw)=f(z)f(w),

για κάθε z,w\in\mathbb C.

Νοεμβρίου 17, 2008

Σχεδόν ακέραιος

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

Δείξτε ότι για κάθε n\in\mathbb{N} η απόσταση του (1+\sqrt{2})^n από τον πλησιέστερό του ακέραιο είναι μικρότερη από \frac{1}{2^n}.

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

Γραμμικός συνδυασμός με μη αρνητικούς συντελεστές

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

Ας είναι {a_1, \ldots,a_n \in {\mathbb R}^m} και {b \in {\mathbb R}^m} δοσμένα διανύσματα. Μας ενδιαφέρει να γράψουμε το b ως γραμμικό συνδυασμό των {a_1,\ldots,a_n} όπου οι συντελεστές είναι μη αρνητικοί:

{b = x_1 a_1 + \cdots + x_n a_n}, με {x_1,\ldots,x_n \ge 0}      (*).

Δείξτε ότι αν αυτό είναι αδύνατο τότε υπάρχει ένα {y \in {\mathbb R}^m} τέτοιο ώστε τα εσωτερικά γινόμενα {y\cdot a_i}, {i=1,\ldots,n} είναι όλα {\ge 0} αλλά {y\cdot b < 0}.

Παρατηρείστε ότι αν υπάρχει τέτοιο διάνυσμα y τότε σίγουρα δε μπορούμε να γράψουμε το b σα μη αρνητικό συνδυασμό των a_i. Τέτοιο y υπάρχει συνεπώς αν και μόνο αν η (*) δεν έχει λύση.

Περίπλοκα σύνολα

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

Από τοπολογική άποψη, τα πιο απλά υποσύνολα του \mathbb R είναι τα ανοιχτά και τα κλειστά. Τα αμέσως πιο περίπλοκα είναι αυτά που μπορούν να γραφτούν σαν αριθμήσιμες ενώσεις κλειστών ή αριθμήσιμες τομές ανοιχτών. Αυτά λέγονται F_\sigma και G_\delta αντίστοιχα. Για παράδειγμα, το σύνολο των ρητών είναι F_\sigma και το σύνολο των άρρητων είναι G_\delta. Βρείτε ένα σύνολο το οποίο δεν είναι ούτε F_\sigma ούτε G_\delta.

Νοεμβρίου 10, 2008

Μαγικά με τα χαρτιά

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

card-magic

Ένας μάγος κάνει το εξής κόλπο με χαρτιά. (περισσότερα…)

Νοεμβρίου 3, 2008

Πώς να συνδέσουμε τα μηχανήματα;

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

Στο Τμήμα Μαθηματικών του Πανεπιστημίου Κρήτης κατασκευάζουμε μια αίθουσα με υπολογιστές. Αυτή έχει μέσα δύο πάγκους, τον Α και τον Β, και ο καθένας από αυτούς έχει επάνω κάποια μηχανήματα. Κάθε μηχάνημα έχει 4 τρόπους να συνδεθεί με άλλο μηχάνημα: USB, ethernet, serial και parallel. Για κάθε ένα από αυτούς τους τρόπους μπορεί να συνδεθεί με το πολύ ένα μηχάνημα (point to point).

O sysadmin μας έχει αποφασίσει ποια μηχανήματα του πάγκου Α θα πρέπει να συνδεθούν με ποια του πάγκου Β. Ξέρουμε δηλ. για κάθε μηχάνημα του πάγκου Α με ποια (το πολύ τέσσερα) μηχανήματα του πάγκου Β πρέπει να συνδεθεί και ομοίως για τα μηχανήματα του πάγκου Β. Δεν τον ενδιαφέρει με ποιο τρόπο από τους τέσσερεις επιτρεπτούς θα συνδεθεί το κάθε ζεύγος.

Δείξτε ότι οι απαιτήσεις αυτές του sysadmin μπορούν να ικανοποιηθούν.

Blog στο WordPress.com.