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

31 Μαΐου, 2008

Ηλιοβασίλεμα στα νότια της Κρήτης

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 4:49 μμ

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

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

Η κοπέλα σπουδάζει μαθηματικά οπότε μετά τον ρωτάει:

Ποιο από τα δύο ποτά έχει μεγαλύτερο ποσοστό από το αρχικό του περιεχόμενο;

Πρέπει οπωσδήποτε να απαντήσει σωστά. Βοηθείστε τον.

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

30 Μαΐου, 2008

Πώς να βγάλετε κέρδος απ’ το μηδέν

Filed under: Λυμένα Προβλήματα,Με επιπλέον ερωτήματα — Mihalis Kolountzakis @ 12:55 μμ

Βρείτε ένα σύνολο A στο επίπεδο το οποίο να μπορεί να διαμεριστεί σε δύο ξένα μεταξύ τους σύνολα B και C τέτοια ώστε το B να είναι μεταφορά του A και το C να είναι μια στροφή του A.


Έμαθα αυτή την άσκηση από τον Αρίστο Συσκάκη.

28 Μαΐου, 2008

Άνετη σύγκλιση

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 1:56 πμ

Έστω \displaystyle \sum_{n=1}^\infty x_n μια συγκλίνουσα σειρά μη αρνητικών αριθμών. Δείξτε ότι υπάρχει μια ακολουθία y_n με y_n\to\infty τέτοια ώστε η σειρά \displaystyle \sum_{n=1}^\infty y_nx_n συγκλίνει.

27 Μαΐου, 2008

Στεφάνια

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

Έχουμε δύο κυκλικά στεφάνια, με ακτίνες R και 2R. Το μικρότερο στεφάνι είναι τοποθετημένο στο εσωτερικό του μεγαλύτερου ώστε να εφάπτονται σε κάποιο σημείο. 

Προσδένουμε μια γραφίδα στο μικρότερο στεφάνι στο σημείο που εφάπτεται με το μεγαλύτερο και αρχίζουμε να το κυλίουμε στο εσωτερικό του μεγαλύτερου στεφανιού (το οποίο κρατάμε σταθερό.) Τι σχήμα θα σχηματίσει το ίχνος της γραφίδας;

26 Μαΐου, 2008

Μικρή αλληλοεπικάλυψη

Filed under: Λυμένα Προβλήματα,Με επιπλέον ερωτήματα — Themis Mitsis @ 2:10 μμ

Έστω {\mathcal F} μια πεπερασμένη οικογένεια ανοιχτών διαστημάτων. Δείξτε ότι υπάρχει {\mathcal G\subset\mathcal F} τέτοια ώστε:

(1) \displaystyle\bigcup_{I\in\mathcal G}I=\bigcup_{I\in\mathcal F}I.

(2) Κάθε σημείο ανήκει το πολύ σε δυο διαστήματα της {\mathcal G}.

Δηλαδή η \mathcal G καλύπτει ό,τι καλύπτει και η \mathcal F, αλλά τα διαστήματά της έχουν μικρή αλληλοεπικάλυψη. Μικρότερη θα σήμαινε ότι είναι ξένα. Αυτό γενικά δεν είναι εφικτό. Κοιτάξτε το «Πρόβλημα κάλυψης με διαστήματα», για να δείτε πως πρέπει να τροποποιηθεί η (1) αν στην (2) απαιτήσουμε, σώνει και καλά, τα διαστήματα να είναι ξένα.

Δίσκοι και σφαίρες

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 12:22 πμ

Θεωρούμε τον κλειστό μοναδιαίο δίσκο στο επίπεδο

D=\{(x,y)\in\mathbb R^2:x^2+y^2\leq1\}

και την επιφάνεια της μοναδιαίας σφαίρας στον χώρο

S=\{(x,y,z)\in\mathbb R^3:x^2+y^2+z^2=1\}.

Υπάρχει h:D\to S συνεχής, 1-1 και επί; Υπάρχει f:D\to S συνεχής και επί;

25 Μαΐου, 2008

Στατιστικά περίεργα

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

Ας υποθέσουμε ότι έχουμε ένα μεγάλο πληθυσμό ανθρώπων του οποίου θέλουμε να εκτιμήσουμε το μέσο ύψος αλλά και το πόσο αυτό κυμαίνεται μέσα στον πληθυσμό. Λίγο πιο αυστηρά, θέλουμε να εκτιμήσουμε τη μέση τιμή {\mathbb E}X και τη διασπορά \sigma^2(X) της τυχαίας μεταβλητής X που προκύπτει αν επιλέξουμε ένα τυχαίο άτομο και μετρήσουμε το ύψος του, με όλα τα άτομα εξίσου πιθανά να επιλεγούν.

Ο τρόπος που το κάνουμε είναι να διαλέξουμε N φορές τυχαία (N μεγάλο) ένα άτομο και να μετρήσουμε το ύψος του, έστω x_i, i=1,\ldots,N. Έπειτα εκτιμούμε το μέσο ύψος του πληθυσμού από την ποσότητα

\displaystyle \overline{x} = \frac{1}{N} \sum_{i=1}^N x_i.

Θυμόμαστε τώρα το γενικό ορισμό \sigma^2(X) = {\mathbb E}(X - {\mathbb E}X)^2 και εκτιμούμε ανάλογα τη διασπορά του ύψους από την ποσότητα

\displaystyle S^2 = \frac{1}{N} \sum_{i=1}^N (x_i - \overline{x})^2.

Όμως ο στατιστικός φίλος μας, στον οποίο δείχνουμε τη μέθοδό μας, ισχυρίζεται ότι δεν πρέπει να το κάνουμε έτσι αλλά ως εξής:

\displaystyle S^2 = \frac{1}{N-1} \sum_{i=1}^N (x_i - \overline{x})^2.

Η αλήθεια είναι ότι αυτές οι δύο ποσότητες ελάχιστα διαφέρουν μεταξύ τους όταν το N είναι μεγάλο. Όμως ποιος έχει δίκιο;

– Το Μηδέν και το Άπειρο

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 1:30 πμ

Έστω X ένας απειροδιάστατος διανυσματικός χώρος επί του \mathbb R. Αυτό σημαίνει ότι ο X έχει μια βάση που αποτελείται από άπειρα στοιχεία (άρα όλες οι βάσεις του έχουν άπειρα στοιχεία). Δείξτε ότι αν

\Lambda_k:X\to\mathbb R, k=1,\dots,n,

είναι μια πεπερασμένη οικογένεια γραμμικών απεικονίσεων, τότε υπάρχει μη μηδενικό x\in X τέτοιο ώστε

\Lambda_k(x)=0

για κάθε k. Αυτό δεν ισχύει αν ο X έχει πεπερασμένη διάσταση. Παράδειγμα:

X=\mathbb R^2, \Lambda_1(x,y)=x, \Lambda_2(x,y)=y.

23 Μαΐου, 2008

– Τα μαθηματικά είναι ο φίλος σας

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

Πριν σας θέσω το νέο πρόβλημα θα σας πω μια ιστορία:

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

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

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

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

(Αυτός ο όγκος αναπαριστούσε την τρύπα μιας εκσκαφής και σκοπός του μαθήματος ήταν να υπολογίσουν πόσο χώμα θα βγάλουν.) Λοιπόν ο καθηγητής δίδασκε τους φοιτητές του να σπάνε το στερεό αυτό σε κομμάτια με οριζόντιες τομές και κατόπιν να υπολογίζουν τον όγκο κάθε κομματιού γράφοντάς το σα προσημασμένο άθροισμα κώνων και κυλίνδρων. Π.χ. στο σχήμα επάνω η «μύτη» είναι κώνος και το από πάνω κομμάτι είναι διαφορά δύο κώνων κ.ο.κ. Έπειτα χρησιμοποιούσαν γνωστούς τύπους για όγκο αυτών το σχημάτων. Πράγμα φυσικά σωστό αλλά που είναι αρκετά δύσκολο να υπολογιστεί αυτόματα ή να καλύψει κάπως γενικότερες καταστάσεις.

Σας δίνεται ένα πολυγωνικό χωρίο P που περιέχεται στο δεξί ημιεπίπεδο \{x\ge 0\}. Το πολύγωνο σας δίνεται με την ακολουθία (x_0, y_0), (x_1, y_1), \ldots , (x_{N-1}, y_{N-1}) των κορυφών του. Βρείτε ένα τύπο για τον όγκο του στερεού που προκύπτει αν περιστρέψουμε το P γύρω από τον άξονα y.

21 Μαΐου, 2008

Μέγιστο εκθετικών

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 2:22 πμ

Θεωρήστε μια ακολουθία X_1,X_2,... από ανεξάρτητες ισόνομες τυχαίες μεταβλητές με εκθετική κατανομή (με μέση τιμή 1). Ορίζουμε M_n=max\{X_1,...,X_n\}. Υπολογίστε το \displaystyle \lim_{n\to\infty} P\big[M_n\le \ln(n)+x\big] και χρησιμοποιήστε αυτό το αποτέλεσμα για να υπολογίσετε το ολοκλήρωμα \displaystyle \int_0^\infty 1-e^{-e^{-x}}-e^{-e^x} dx.

– Γιατί άτοπο;

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 12:53 πμ

Το θεώρημα του Steinhaus λέει ότι αν το A\subset\mathbb R^2 έχει θετικό εμβαδό τότε το σύνολο

A-A=\{a-b:a,b\in A\}

περιέχει ένα δίσκο με κέντρο την αρχή των αξόνων.

Βρείτε τώρα γιατί καταλήγουμε σε άτοπο στον παρακάτω συλλογισμό.

Στο \mathbb R^2 θεωρήστε τα σύνολα x+\mathbb Q^2, x\in\mathbb R^2, δηλαδή όλες τις μεταθέσεις του \mathbb Q^2. Δυο τέτοια σύνολα είτε ταυτίζονται είτε είναι ξένα. Επίσης

\displaystyle\bigcup_{x\in\mathbb R^2}\left(x+\mathbb Q^2\right)=\mathbb R^2.

Επομένως υπάρχει κάποιο A\subset\mathbb R^2 τέτοιο ώστε τα σύνολα a+\mathbb Q^2, a\in A, είναι ανά δυο ξένα και

\displaystyle\bigcup_{a\in\mathbb A}\left(a+\mathbb Q^2\right)=\mathbb R^2.

Άρα

\displaystyle\bigcup_{q\in\mathbb Q^2}\left(q+A\right)=\mathbb R^2.

Η προηγούμενη σχέση λέει ότι το A δεν μπορεί να έχει μηδενικό εμβαδό γιατί τότε όλα τα q+A θα είχαν μηδενικό εμβαδό, συνεπώς ολόκληρο το επίπεδο θα είχε μηδενικό εμβαδό σαν αριθμήσιμη ένωση συνόλων εμβαδού μηδέν. Αλλά το A δεν μπορεί να έχει ούτε θετικό εμβαδό διότι τότε, από το θεώρημα του Steinhaus, το A-A θα περιείχε κάποιον δίσκο, άρα και κάποιο σημείο με ρητές συντεταγμένες. Δηλαδή θα υπήρχαν q\in\mathbb Q^2, a,b\in A, έτσι ώστε q=a-b. Αυτό όμως είναι αδύνατο γιατί τα σύνολα a+\mathbb Q^2 και b+\mathbb Q^2 είναι ξένα.

19 Μαΐου, 2008

Αθροίσματα Δύο Τετραγώνων

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

Οι φυσικοί αριθμοί του τύπου n=x^2+y^2, όπου x, y ακέραιοι, είναι τόσο απλοί να τους ορίσεις όσο και μυστηριώδεις και αποτελούν ακόμη πηγή πολλών ανοιχτών προβλημάτων στη θεωρία Αριθμών. (Παρεπιπτόντως το ίδιο δε συμβαίνει με τα αθροίσματα τριών τετραγώνων ακεραίων, που είναι πολύ εύκολο να περιγραφούν.) Είναι εύκολο να δεί κανείς ότι δεν είναι όλοι οι φυσικοί αριθμοί άθροισμα δύο τετραγώνων (ενώ είναι άθροισμα τεσσάρων τετραγώνων–αυτό δεν είναι τόσο εύκολο) και το πόσο μεγάλα κενά αφήνουν ανάμεσά τους αποτελεί ακόμη μυστήριο.

Δείξτε ότι υπάρχει μια σταθερά C>0 τέτοια ώστε υπάρχει άθροισμα δύο τετραγώνων ακεραίων σε κάθε διάστημα της μορφής (x, x+Cx^{1/4}), για x\ge 1.

– Πώς να μην κρεμάσετε ένα κάδρο

Filed under: Λυμένα Προβλήματα,Με επιπλέον ερωτήματα — Mihalis Kolountzakis @ 12:57 πμ

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

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

(Images courtesy of DailyClipArt.net.)

17 Μαΐου, 2008

Κάρτα επιβίβασης

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 3:14 πμ

Περιμένετε υπομονετικά να επιβιβαστείτε σε ένα αεροπλάνο. Τα καθίσματα του αεροπλάνου είναι αριθμημένα από το 1 ως το 100, η πτήση είναι γεμάτη, και σύμφωνα με την κάρτα επιβίβασης που κρατάτε έχετε το κάθισμα με αριθμό 27. Όταν η επιβίβαση ξεκινά πρώτη μπαίνει μια γιαγιά που για να μην ταλαιπωρείται κάθεται στο κάθισμα με αριθμό 1 (παρότι έχει το κάθισμα με αριθμό 73.) Οι επόμενοι επιβάτες επιβιβάζονται με τυχαία σειρά και κάθονται ως εξής: αν βρούν άδειο το κάθισμά τους κάθονται σε αυτό, αν όχι κάθονται στο πρώτο κάθισμα με μεγαλύτερο αριθμό που θα βρούν διαθέσιμο. Εσείς επιβιβάζεστε τελευταίος/α. Που θα καθίσετε;

– Αθροίσματα συνημιτόνων

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

Αν n_1 < \cdots < n_k είναι φυσικοί αριθμοί δείξτε ότι

\displaystyle \int_0^{2\pi} |\cos{n_1 x} + \cdots + \cos{n_k x}| dx \ge 4.

(Το πρόβλημα αυτό το έμαθα από το Σταύρο Παπαδόπουλο.)

15 Μαΐου, 2008

Τα εφτά τρίγωνα

Filed under: Λυμένα Προβλήματα,Με επιπλέον ερωτήματα — Michalis Loulakis @ 2:19 πμ

Ζωγραφίστε ένα κεφαλαίο Η (δύο παράλληλα ευθύγραμμα τμήματα και ένα κάθετο σε αυτά τμήμα με τα άκρα του στα παράλληλα τμήματα). Φέρνοντας 3 επιπλέον ευθύγραμμα τμήματα σχηματίστε 7 ξένα μεταξύ τους τρίγωνα. Τρίγωνα με κορυφές στο άπειρο δεν προσμετρώνται!

(Την άσκηση αυτή έμαθα από τον Άρη Αραποστάθη που επισκέπτεται το Πανεπιστήμιο Κρήτης αυτές τις μέρες.)

14 Μαΐου, 2008

– Απυρόβλητοι κύκλοι

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

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

– Ο αποτελεσματικός ηλεκτρολόγος

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 9:20 πμ

Μετά το τέλος ενός πρωτοποριακού δημόσιου έργου διαπιστώνεται ότι ναι μεν ο εργολάβος είχε, όπως απαιτούνταν, περάσει 11 καλώδια από τη μια πλευρά ενός ποταμού στην άλλη (σκάβοντας ένα μικρό τούνελ κάτω από την κοίτη) αλλά δεν είχε κρατήσει λογαριασμό ποιο από τα άκρα στην πλευρά Α αντιστοιχούσε σε ποιο στην πλευρά Β. Δεν απαιτούνταν άλλωστε ρητά από τη μελέτη και τη σύμβαση.

Έτσι, ο άτυχος ηλεκτρολόγος που ανέλαβε μετά να χρησιμοποιήσει τα καλώδια βρίσκεται αντιμέτωπος με ονομασίες των άκρων Α1 έως Α11 και Β1 έως Β11 που είναι τελείως αυθαίρετες. Πρώτο πράγμα που πρέπει λοιπόν να κάνει είναι να βρει ποιο από το Α άκρα αντιστοιχεί σε ποιο Β άκρο.

Για να το πετύχει αυτό δύο πράγματα μπορεί να κάνει (δουλεύει μόνος του):

  • να δένει μεταξύ τους κάποια άκρα (βραχυκυκλώνοντάς τα) και
  • να ελέγχει με ένα λαμπάκι και μια μπαταρία αν δύο άκρα είναι μεταξύ τους βραχυκυκλωμένα.

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

Δείξτε ότι μπορεί να λύσει το πρόβλημά του με ένα μόνο πέρασμα, μετ’ επιστροφής.

13 Μαΐου, 2008

Πιθανότητα πολλαπλασίων

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 6:47 πμ

Θα συμβολίζουμε με m\mathbb{N} το σύνολο των πολλαπλασίων του m\in\mathbb{N}. Υπάρχει μέτρο πιθανότητας που να ορίζεται τουλάχιστον σε όλα τα σύνολα αυτής της μορφής και τέτοιο ώστε για κάθε m\in\mathbb{N} να ισχύει \displaystyle P[m\mathbb{N}]=\frac{1}{m};

– Εμπιστεύεστε την τύχη σας;

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

Ο Paul Erdős (ουγγρικά: Erdős Pál) υπήρξε από τους πρωτεργάτες και ο κυριότερος προπαγανδιστής της λεγόμενης «πιθανοθεωρητικής μεθόδου» (probabilistic method) στα μαθηματικά και ιδιαίτερα σε αυτό που σήμερα ονομάζεται «διακριτά μαθηματικά» (θεωρία αριθμών, συνδυαστική, θεωρητική επιστήμη υπολογιστών). Η πρωσοποποίηση της ιδιορρυθμίας, ο Erdős έζησε μια ζωή γεμάτη μαθηματικά και μόνο, τα οποία σημάδεψε με δεκάδες σημαντικά αποτελέσματα και εκατοντάδες συνεργασίες σε όλο τον κόσμο.

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

Υποθέστε ότι έχετε ένα πλήρες γράφημα με n κορυφές (n σημεία δηλ. που όλα ενώνονται με όλα τα άλλα, με πλήθος ακμών {n \choose 2}) και ότι κάθε ακμή του μπορεί να βαφεί κόκκινη ή μπλε. Δείξτε ότι μπορείτε να επιλέξετε τα χρώματα των ακμών έτσι ώστε το πλήθος των μονοχρωματικών τριγώνων που σχηματίζονται να είναι το πολύ \frac{1}{4} {n \choose 3}.

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

Blog στο WordPress.com.