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

Φεβρουαρίου 28, 2010

Κομπολόι

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

N χάντρες είναι περασμένες στη σειρά σε μια κλωστή. Διαλέγουμε τυχαία ένα ζευγάρι γειτονικές χάντρες και κόβουμε την κλωστή δεξιά και αριστερά τους, απομονώνοντάς τις από τις υπόλοιπες. Συνεχίζουμε να το κάνουμε ώσπου να μείνουν από την κλωστή μόνο κομμάτια με δύο το πολύ χάντρες. Στο τέλος της διαδικασίας λέμε ότι μια χάντρα είναι απομονωμένη αν έχουμε κόψει την κλωστή και δεξιά και αριστερά της. Αν E_N είναι το αναμενόμενο πλήθος των απομονωμένων χαντρών, ποιό είναι το όριο

\displaystyle lim_{N\to\infty}\frac{E_N}{N};

Advertisements

Φεβρουαρίου 20, 2010

Ο πύργος τής Βαβέλ

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

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

Φεβρουαρίου 15, 2010

Διαταραχές πινάκων

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

Θεωρήστε δύο πραγματικούς συμμετρικούς n\times n πίνακες A, B με ιδιοτιμές \lambda_1\le\cdots\le\lambda_n και \mu_1\le\cdots\le\mu_n, αντίστοιχα. Ας συμβολίζουμε με \rho_i τις ιδιοτιμές του πίνακα A-B. Δείξτε ότι

\displaystyle \sum_{k=1}^n (\lambda_k-\mu_k)^2\le\sum_{k=1}^n\rho_k^2\le\sum_{k=1}^n(\lambda_k-\mu_{n-k})^2.

Φεβρουαρίου 6, 2010

Συγκλίνει;

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

Έστω p_1\le p_2\le \cdots η ακολουθία όλων των πρώτων αριθμών και ας θεωρήσουμε μια ακολουθία \{q_n\} από σύνθετους αριθμούς που είναι μεταξύ τους σχετικά πρώτοι: (q_m,q_n)=1,\ \forall m\neq n. Συγκλίνει η σειρά

\displaystyle \sum_n\frac{q_n}{p_n^3};

Φεβρουαρίου 4, 2010

Τυχαίοι φορολογικοί έλεγχοι

Filed under: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 7:53 μμ

Εργάζεστε στο Υπουργείο Οικονομικών και παίρνετε εντολή να επιλέξετε ένα τυχαίο δείγμα επαγγελματιών για φορολογικό έλεγχο. Ο προϊστάμενός σας έχει θέσει αυστηρές προδιαγραφές:

  1. Κάθε επαγγελματίας θα πρέπει να ελεγχθεί με πιθανότητα p=1/10000=10^{-4}.
  2. Η πιθανότητα που έχει κάθε ένας να ελεγχθεί δεν εξαρτάται από το αν κάποιοι άλλοι θα ελεγχθούν ή όχι (σε πιο μαθηματική γλώσσα, τα ενδεχόμενα ελέγχου των επαγγελματιών είναι ανεξάρτητα).

Βλέπετε ότι υπάρχουν N=10^6 επαγγελματίες. Κατ’ αρχήν λοιπόν σκέφτεστε να βάλετε τον υπολογιστή σας να κάνει N τυχαίες και ανεξάρτητες επιλογές και έτσι να επιλέξετε το δείγμα σας. Ο υπολογιστής σας μπορεί φυσικά εύκολα να το κάνει αυτό: είναι εφοδιασμένος με ένα υποπρόγραμμα το οποίο, κάθε φορά που καλείται, επιστρέφει ένα αριθμό X ομοιόμορφα κατανεμημένο στο διάστημα [0,1]. Καλείτε λοιπόν αυτό το υποπρόγραμμα N φορές και, κάθε φορά, αν το X πέσει στο διάστημα [0,p] τότε ο «τυχερός» επαγγελματίας επιλέγεται για έλεγχο.

Όμως, σας λέει ο έμπειρος προϊστάμενός σας (ο οποίος μόλις είχε πάρει μεταγραφή στο Υπουργείο Οικονομικών από τη Στατιστική Υπηρεσία, η οποία εκείνη την εποχή υπόκειτο σε ανακατατάξεις και δικαστικούς ελέγχους), υπάρχει και η εξής παράμετρος: το σύστημα επιλογής σας υπόκειται σε δικαστικό έλεγχο. Και είναι γνωστό ότι οι υπολογιστές είναι ντετερμινιστικά μηχανήματα και τίποτα από αυτά που κάνουν δεν είναι τυχαίο. Η υπορουτίνα τυχαίων αριθμών που χρησιμοποιείτε δεν παράγει πραγματικά τυχαίους αριθμούς· αυτό όλοι το γνωρίζουν. Πώς μπορεί λοιπόν να σταθεί στο δικαστήριο η μέθοδός σας;

Η μόνη λύση που σας έρχεται στο μυαλό είναι να χρησιμοποιήσετε γεννήτρια τυχαίων αριθμών εκτός του υπολογιστή σας. Ένας τρόπος π.χ. να το κάνετε αυτό είναι να παράγετε πολλά ανεξάρτητα τυχαία νούμερα ομοιόμορφα στο [0,1] (π.χ. χρησιμοποιώντας κάτι σα ρουλέτα στην οποία μετράτε κάθε φορά τη γωνία με την οποία περιστράφηκε και διαιρείτε διά 2\pi) και να τα καταχωρήσετε σε ένα αρχείο του υπολογιστή σας. Όποτε το πρόγραμμά σας χρειάζεται ένα τυχαίο αριθμό απλά θα παίρνει τον επόμενο απο αυτό το αρχείο.

Ο προιστάμενός σας είναι ευχαριστημένος: η μέθοδός σας σίγουρα περνάει κάθε νομικό έλεγχο.

Όμως μετά από λίγο καταλαβαίνετε ότι το να παράγετε 10^6 τυχαίους αριθμούς με μηχανικό τρόπο θα πάρει πολύ χρόνο και χρήμα. Είναι πρακτικά αδύνατο.

Πρέπει να βρείτε ένα τρόπο να παράγετε αυτό το τυχαίο δείγμα (κατά μέσο όρο θα έχει μέγεθος 100) χρησιμοποιώντας πολύ λιγότερους τυχαίους αριθμούς.

Προτείνετε λύσεις.

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

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