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

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

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

Κατηγορίες: Άλυτα Προβλήματα — 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

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

Κατηγορίες: Άλυτα Προβλήματα — 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.

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

Διπλασιασμός μέχρι τέλους

Κατηγορίες: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 12:12 πμ

Τρείς φίλοι ξεκινούν έχοντας ένα (ακέραιο, θετικό) χρηματικό ποσό ο καθένας.

Σε κάθε βήμα δύο από αυτούς μπορούν να τροποποιούν τα ποσά που έχουν ως εξής:

αν είναι x\le y τα δύο ποσά τότε αυτός που έχει τα περισσότερα δίνει στον άλλο όσα έχει ο άλλος. Τα δύο ποσά γίνονται δηλ. 2x και y-x.

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

Αυγούστου 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.

Μαΐου 24, 2009

Μηλιές και πορτοκαλιές

Κατηγορίες: Άλυτα Προβλήματα — Michalis Loulakis @ 10:52 πμ

Δύο αδέρφια κληρονομούν ένα κτήμα που έχει μέσα 2ν μηλιές και 2μ πορτοκαλιές. Μπορούν να το χωρίσουν με μια ευθεία έτσι ώστε ο καθένας να πάρει ακριβώς ν μηλιές και μ πορτοκαλιές;

Μαΐου 16, 2009

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

Κατηγορίες: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 8:05 πμ

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

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

Μαΐου 14, 2009

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

Κατηγορίες: Άλυτα Προβλήματα — Themis Mitsis @ 1:11 πμ

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

Μαΐου 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 @ 10:10 μμ

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

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

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

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

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

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

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

Απριλίου 25, 2009

Μονόδρομοι

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

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

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

Απριλίου 16, 2009

Ικανοποίηση

Κατηγορίες: Άλυτα Προβλήματα — 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 να είναι αληθές.

Απριλίου 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 μμ

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

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

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

Κατηγορίες: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 2:09 πμ

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

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

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

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

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

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

Άπειρο γινόμενο

Κατηγορίες: Άλυτα Προβλήματα — Michalis Loulakis @ 2:45 μμ

Ορίζουμε αναδρομικά την ακολουθία \{\alpha_n\} ως εξής:

\alpha_0\ge -1 και \alpha_n=\sqrt{\frac{1+\alpha_{n-1}}{2}}, για κάθε n\in\mathbb{N}. Υπολογίστε το όριο \displaystyle L(\alpha_0)=\lim_{n\to\infty}\prod_{j=1}^{n}\alpha_j.

 

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

Διαφορές προς αποφυγή

Κατηγορίες: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 1:22 πμ

Ας είναι { D=\{d_1<d_2<\cdots<d_k\} \subseteq {\mathbb N} = \{1,2,3,\ldots\} }. Κατασκευάστε σύνολο {\Lambda \subseteq {\mathbb N}} τέτοιο ώστε

{\lambda - \mu \notin D} για \lambda, \mu \in \Lambda

και

\displaystyle \frac{|\Lambda \cap [1,n]|}{n} \ge \frac{1}{k+1} για άπειρα n.

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

Καλύπτεται;

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

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

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

Blog στο WordPress.com.