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

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

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

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

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

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

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

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

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

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

Πέντε σημεία

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

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

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

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

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

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

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

four-cards

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

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

Ιουλίου 21, 2009

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

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

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

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

Μαΐου 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.

Μαΐου 8, 2009

Τρίγωνα

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

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

Μαΐου 7, 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 πραγματικοί αριθμοί.

Απριλίου 25, 2009

Μονόδρομοι

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

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

Σημείωση: Όποιος λύσει το πρόβλημα “Ικανοποίηση” σίγουρα δεν θα έχει πρόβλημα να λύσει και αυτό το πρόβλημα στην περίπτωση που n>20.

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

Μαρτίου 5, 2009

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

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

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

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

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

Κατηγορίες: Λυμένα Προβλήματα, Με επιπλέον ερωτήματα, Με υπόδειξη — Michalis Loulakis @ 6:27 μμ

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

triangulation1

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

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

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

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

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

queue

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

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

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

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

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

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

Καλύπτεται;

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

Γύρω από κάθε ρητό αριθμό \frac{p}{q}\in (0,1] θεωρήστε συμμετρικά ένα κλειστό διάστημα εύρους \frac{1}{2q^2}. Καλύπτει η ένωση όλων αυτών των διαστημάτων το (0,1];

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

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

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

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

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

{A x \ge b}

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

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

Peer to peer

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

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

Νοεμβρίου 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 υπάρχει συνεπώς αν και μόνο αν η (*) δεν έχει λύση.

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

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

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

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

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

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

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

Blog στο WordPress.com.