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

Μαΐου 14, 2009

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

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

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

Μαΐου 13, 2009

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

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — 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.

Μαΐου 8, 2009

Τρίγωνα

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

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

Μαΐου 7, 2009

Μονά-ζυγά

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

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

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

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

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

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

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

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

Απριλίου 30, 2009

Σχέσεις

Αν είναι 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 πραγματικοί αριθμοί.

Απριλίου 16, 2009

Ικανοποίηση

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — 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 να είναι αληθές.

Μαρτίου 5, 2009

Μετρήσιμοι δίσκοι

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

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

Ιανουαρίου 23, 2009

Υπουργικό συμβούλιο

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

Ένας νεοεκλεγείς πρόεδρος σε μια μεγάλη χώρα με πληθυσμό από λευκούς και έγχρωμους (=όλοι οι μη λευκοί) θέλει να ορίσει το υπουργικό του συμβούλιο. Θέλει να χρησιμοποιήσει αυτή του την πράξη ώστε, μεταξύ άλλων, να προωθήσει τη συνεργασία λευκών και έγχρωμων στη χώρα του. Γι’ αυτό θεσπίζει τον εξής κανόνα:

κάθε λευκό μέλος του υπουργικού συμβουλίου θα πρέπει να έχει τουλάχιστον τόσους έγχρωμους συνεργάτες όσους και λευκούς και, ομοίως, κάθε έγχρωμο μέλος θα πρέπει να έχει τουλάχιστον τόσους λευκούς συνεργάτες όσους και έγχρωμους.

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

Ο ίδιος ο πρόεδρος είναι κι αυτός μέλος του υπουργικού συμβουλίου και είναι έγχρωμος.

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

Ιανουαρίου 3, 2009

Τρίγωνα και χρώματα

Θεωρούμε ένα τρίγωνο ΑΒΓ και διαιρούμε την επιφάνεια του τριγώνου σε μικρότερα τρίγωνα έτσι ώστε αυτά να έχουν είτε μια κοινή πλευρά, είτε μια κοινή κορυφή είτε κανένα κοινό σημείο, όπως π.χ. στο σχήμα.

triangulation1

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

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

Δεκεμβρίου 15, 2008

Μπείτε στη σειρά

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

queue

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

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

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

Ένας απλός τρόπος είναι ο 1ος να το πει στον 2ο, ο 2ος στον 3ο κ.ο.κ. Αυτός ο τρόπος παίρνει χρόνο ανάλογο του N για να υπολογίσει τη σειρά του καθενός.

Βρείτε ένα τρόπο να γίνει αυτός ο υπολογισμός πολύ πιο γρήγορα.

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

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

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

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

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

{A x \ge b}

(more…)

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

Peer to peer

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

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

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

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

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — 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 υπάρχει συνεπώς αν και μόνο αν η (*) δεν έχει λύση.

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

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

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

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

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

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

Οκτωβρίου 26, 2008

Αεροδρόμιο στη στέπα

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

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

Σεπτεμβρίου 17, 2008

Ποσοδείκτες

Αν σε μια πρόταση εναλλάξετε τις θέσεις δυο ποσοδεικτών, τότε συνήθως το νόημα αλλάζει δραματικά. Για παράδειγμα, αν σε κάποιο διαγώνισμα τον ορισμό της συγκλίνουσας ακολουθίας τον ξεκινήσετε ως εξής:

«Υπάρχει n_0\in\mathbb N τέτοιο ώστε για κάθε \varepsilon>0 μπλα μπλα μπλα»

τότε το πιο πιθανό είναι ότι θα εξασφαλίσετε την συμμετοχή σας στην επόμενη εξεταστική. Επίσης, οι προτάσεις

«Για κάθε γυναίκα υπάρχει άντρας έτσι ώστε μπλα μπλα μπλα»

και

«Υπάρχει άντρας έτσι ώστε για κάθε γυναίκα μπλα μπλα μπλα»

είναι μάλλον διαφορετικές, εκτός κι’ αν μιλάμε για τον Brad Pitt. Παρ’ όλα αυτά, βρείτε 4 συντακτικά σωστές μαθηματικές προτάσεις (μπλα μπλα)-1, (μπλα μπλα)-2, (μπλα μπλα)-3 και (μπλα μπλα)-4 έτσι ώστε οι παρακάτω δυο συνεπαγωγές να είναι αληθείς:

«Αν υπάρχει (μπλα μπλα)-1 έτσι ώστε για κάθε (μπλα μπλα)-2 να ισχύει (μπλα μπλα)-3, τότε (μπλα μπλα)-4»

και

«Αν για κάθε (μπλα μπλα)-2 υπάρχει (μπλα μπλα)-1 έτσι ώστε να ισχύει (μπλα μπλα)-3, τότε (μπλα μπλα)-4»

Σεπτεμβρίου 8, 2008

Πρώτη δύναμη

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

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

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

Πώς θα απελευθερωθούν;

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

Ένας διεθυντής φυλακής έχει 100 φυλακισμένους και θα παίξει μαζί τους το εξής παιχνίδι: Θα τους βάλει στη σειρά, τον ένα πίσω από τον άλλο, και θα φορέσει σε καθένα από ένα πράσινο, κόκκινο ή μπλέ καπέλο. Κατόπιν θα τους ρωτήσει έναν-έναν, αρχίζοντας από τον τελευταίο, τι χρώμα καπέλο φορούν. Όποιος βρίσκει τι χρώμα καπέλο φοράει θα απελευθερώνεται, αλλιώς όχι.

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

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

Διευκρινίζεται ότι ο τελευταίος της γραμμής (ο Νο 100), ο οποίος απαντάει πρώτος, βλέπει τα καπέλα όλων των άλλων, ο Νο 99 βλέπει τα καπέλα των Νο 98 έως Νο 1, κλπ. Ο Νο 1 (ο πρώτος στη γραμμή) δε βλέπει τίποτα (και απαντάει τελευταίος).

Το πρόβλημα αυτό το έμαθα από τον Παναγιώτη Παπάζογλου.

Ιουλίου 31, 2008

Η συνάρτηση δέλτα

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — Themis Mitsis @ 12:00 πμ

Οι φυσικοί και οι μηχανικοί μιλάνε συχνά για τη «συνάρτηση δέλτα». Υποτίθεται ότι είναι μια συνάρτηση \delta με την ιδιότητα

\displaystyle\int_0^1f(x)\delta(x)\, dx=f(0)

για κάθε f:[0,1]\to\mathbb R συνεχή. Υπάρχει αλήθεια τέτοια συνάρτηση; Αν απαντήσετε «ναι» πρέπει βέβαια να δώσετε έναν τύπο…

« Προηγούμενη σελίδαΕπόμενη σελίδα: »

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

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