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

Αύγουστος 28, 2017

Μπορείτε να σκοτώσετε τον ψύλλο;

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

flea-jumping

Πάνω στο επίπεδο {\mathbb R}^2 βρίσκεται ένας ψύλλος, ο οποίος είναι περιορισμένος να ζει και να κινείται πάνω στο σύνολο των ακεραίων σημείων του επιπέδου {\mathbb Z}^2. Τη χρονική στιγμή 0 βρίσκεται στο σημείο (0,0) και από κει και πέρα κινείται σε κάθε δευτερόλεπτο πηδώντας πάντα κατά το ίδιο διάνυσμα.

Με άλλα λόγια ο ψύλλος κινείται πάνω σε μια ευθεία και μάλιστα πάνω στα ακέραια σημεία της ευθείας αυτής, με σταθερή ταχύτητα. Για παράδειγμα θα μπορούσε σε κάθε ακέραια χρονική στιγμή να πηδάει κατά το διάνυσμα

v=(2,3).

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

Δε βλέπετε όμως πού είναι ο ψύλλος (παρά μόνο αφού τον σκοτώσετε) ούτε ξέρετε ποιο είναι το διάνυσμα κίνησης του ψύλλου v.

Μπορείτε να ακολουθήσετε μια μέθοδο χτυπημάτων που θα είναι σίγουρο ότι θα πετύχει τον ψύλλο αργά η γρήγορα; (Τη χρονική στιγμή 0 δε μπορείτε να χτυπήσετε. Αρχίζετε τη χρονική στιγμή 1.)

Έμαθα το πρόβλημα αυτό από τον Miklos Laczkovich.

Advertisements

Ιουλίου 20, 2015

Ασύμμετρα σύνολα

Ένα ακόμα πρόβλημα από τον Κωνσταντίνο Κουρουζίδη

Για κάθε δυαδικό διάνυσμα x\in\{0,1\}^n θέτουμε \hat x να είναι το διάνυσμα με συντεταγμένες \hat x(j)=1-x(j). Ένα σύνολο δυαδικών διανυσμάτων A λέγεται ασύμμετρο αν x\in A\Rightarrow \hat x\notin A. Πόσα ασύμμετρα σύνολα υπάρχουν;

Ιουλίου 4, 2015

Συμμετρική κατάσταση

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

y

Γνωρίζουμε πολύ καλά ότι αν e_1=(1,0), e_2=(0,1) είναι τα συνηθισμένα διανύσματα βάσης στο επίιπεδο {\mathbb R}^2 τότε κάθε διάνυσμα v\in{\mathbb R}^2 μπορεί να γραφεί ως:

v = \langle v, e_1 \rangle e_1 + \langle v, e_2 \rangle e_2.

Μπορεί δηλ. να γραφεί το v ως γραμμικός συνδυασμός των e_1, e_2 όπου οι συντελεστές είναι απλά τα εσωτερικά γινόμενα με τα διανύσματα αυτά. Το ίδιο φυσικά ισχύει αν στη θέση των e_1, e_2 βάλουμε δύο οποιαδήποτε ορθογώνια μεταξύ τους διανύσματα του επιπέδου με μέτρο 1.

Αν \phi_1 = (\sqrt{2/3}, 0) και \phi_2, \phi_3 είναι οι περιστροφές του \phi_1 κατά \pm\frac{2\pi}{3} αντίστοιχα (όπως φαίνονται στο σχήμα παραπάνω), δείξτε ότι και για τα \phi_1, \phi_2, \phi_3 ισχύει ότι κάθε διάνυσμα v\in{\mathbb R}^2 μπορεί να γραφεί ως:

v = \sum_{j=1}^3 \langle v, \phi_j \rangle \phi_j.

Ιουνίου 17, 2015

Το μαγικό κολιέ των χρωμάτων για μια ζωή χωρίς βαρετές επαναλήψεις

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

Στο φετινό φεστιβάλ στα Μάταλα ένας από τους πλανόδιους πωλητές χειροποίητης τέχνης θα πουλάει το μαγικό κολιέ των χρωμάτων:

necklace

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

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

(Αν ονομάσουμε, χάριν συντομίας, τα χρώματά μας \chi_1,\ldots,\chi_8 τότε θα δούμε δηλ. διανύοντας το κολιέ και μια μετάβαση από \chi_1 σε \chi_1, και μια μετάβαση από \chi_1 σε \chi_2, … , και μια μετάβαση από το \chi_1 σε \chi_8, κλπ. Υπάρχουν φυσικά 8\times 8 = 64 τέτοιες μεταβάσεις, όσες και οι χάντρες του κολιέ. Άρα ένας άλλος τρόπος να πει κανείς το ίδιο πράγμα είναι ότι όπως κινούμαστε γύρω-γύρω στο κολιέ δε θα δούμε ποτέ την ίδια διαδοχή χρωμάτων ξανά σε μια πλήρη μας διάσχιση του κολιέ.)

Υπάρχει τρόπος να φτιαχτεί τέτοιο κολιέ; Αν ναι, πώς; Αν όχι, γιατί;

Ιουνίου 11, 2013

Αλυσίδες

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

circle

Ας είναι T ο μοναδιαίος κύκλος στο επίπεδο.

Η συνάρτηση f: T\to T είναι συνεχής. Αποδείξτε ότι υπάρχουν x_n \in T, n \in {\mathbb Z}, τ.ώ.

f(x_n) = x_{n+1}, για κάθε n\in{\mathbb Z}.

Δεν υποθέτουμε ότι η f είναι 1-1 ή επί.

Νοέμβριος 6, 2012

Εκλογικές αντιφάσεις

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

Σε ένα ελληνικό Πανεπιστήμιο έγιναν πρόσφατα, μετά πολλών βασάνων, οι εκλογές για το Συμβούλιο Διοίκησης, με το νέο, για την Ελλάδα, σύστημα της ταξινομικής ψήφου. Με αυτό το σύστημα οι εκλογείς ψηφίζουν διατάσσοντας τους υποψηφίους γραμμικά (1η προτίμηση, 2η κλπ).

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

  • Τα 2/3 των εκλογέων προτιμούσαν τον Α από τον Β (δηλ. κατέταξαν τον Α σε υψηλότερη θέση),
  • Τα 2/3 των εκλογέων προτιμούσαν τον Β από τον Γ, και,
  • παρ’ όλ’ αυτά, τα 2/3 των εκλογέων προτιμούσαν τον Γ από τον Α!

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

Είναι;

Ιουλίου 19, 2011

Υποσύνολα φυσικών

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

Το πρόβλημα αυτό το έμαθα από τον Δημήτρη Απατσίδη.

Δείξτε ότι υπάρχει μια μη αριθμήσιμη οικογένεια υποσυνόλων του \mathbb{N} τέτοια ώστε η τομή οποιωνδήποτε δύο εξ’ αυτών να είναι πεπερασμένο σύνολο.

Απρίλιος 25, 2011

Στοίχημα

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

Ένας φοιτητής έχει 1 ευρώ και χρειάζεται να συγκεντρώσει 1000 ευρώ για να πάει διακοπές. Αποφασίζει να στοιχηματίσει παίζοντας κορώνα-γράμματα με ένα τίμιο νόμισμα, όπου σε κάθε γύρο θα διπλασιάζει το ποντάρισμά του αν προβλέψει σωστά το αποτέλεσμα του στριψίματος  και θα χάνει το ποντάρισμά του αν προβλέψει λάθος. Έχει αποφασίσει να παίζει μέχρι είτε να χάσει όλα του τα χρήματα είτε να συγκεντρώσει τα 1000 ευρώ. Μπορεί σε κάθε γύρο να στοιχηματίσει οποιοδήποτε ακέραιο ποσό σε ευρώ που δεν ξεπερνά την τρέχουσα περιουσία του, αλλά αναρωτιέται αν υπάρχει στρατηγική που θα μεγιστοποιήσει την πιθανότητα να φτάσει τα 1000 ευρώ. Δείξτε ότι η πιθανότητα αυτή είναι το πολύ 1/1000 και βρείτε μια στρατηγική που του εξασφαλίζει αυτήν την πιθανότητα.

Μαρτίου 27, 2011

Αναδρομική ακολουθία

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

Θεωρούμε την αναδρομική ακολουθία x_1=0, x_{n+1}=x_n+e^{-x_n}.
Βρείτε την τάξη μεγέθους τής x_n καθώς n\to+\infty.

Φεβρουαρίου 5, 2011

Ξένη ένωση

Το πρόβλημα αυτό σχετίζεται με τα σχόλια (8) και (9) τού προηγούμενου.
Μπορείτε να γράψετε το \mathbb R σαν υπεραριθμήσιμη ένωση ξένων ανά δύο υπεραριθμήσιμων συνόλων;

Ιανουαρίου 28, 2011

Άρρητοι αριθμοί

Υπάρχει κλειστό σύνολο άρρητων αριθμών χωρίς μεμονωμένα σημεία;

Νοέμβριος 21, 2010

Αποστάσεις ανάμεσα σε σημεία

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

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

(Έμαθα το πρόβλημα αυτό από τον Μπάμπη Τσουρακάκη.)

Οκτώβριος 6, 2010

Άπειρα πολλαπλάσια

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

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

Σεπτεμβρίου 25, 2010

Ομοιόμορφο στρώσιμο

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

Υπάρχει συνεχής συνάρτηση f: {\mathbb R} \to (0,+\infty) (αυστηρά θετική παντού) τέτοια ώστε

\sum_{n=-\infty}^\infty f(x-n) = 1, για κάθε x \in {\mathbb R};

Αύγουστος 19, 2010

Ατέλειωτος περίπατος

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

Στις κορυφές του \mathbb{Z}^2 τοποθετούμε με πιθανότητα p μια μπαταρία, ανεξάρτητα για διαφορετικές κορυφές. Ένα ρομπότ ξεκινά από την αρχή των αξόνων με μια μπαταρία που επαρκεί για να διανύσει απόσταση ακριβώς 1, και ένα χάρτη με τις κορυφές όπου υπάρχει μπαταρία. Αν στην κορυφή που θα μεταβεί βρει μια μπαταρία μπορεί να συνεχίσει τον περίπατό του για ακόμα ένα βήμα. Δείξτε ότι υπάρχει ένα p_*>0, τέτοιο ώστε αν p<p_* ο περίπατος του ρομπότ θα τελειώσει σε πεπερασμένο χρόνο με πιθανότητα 1.

Αύγουστος 17, 2010

Πτώση μέχρι καταστροφής

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

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

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

Εσείς πρέπει λοιπόν να αποφασίσετε ποιο είναι το ελάχιστο n\ge 1 τέτοιο ώστε αν η γυάλινη σφαίρα πέσει από τον n-οστό όροφο σπάει αλλά αν πέσει από τον (n-1)-όροφο τότε δε σπάει.

Ένας προφανής τρόπος να το κάνετε αυτό χρησιμοποιώντας μάλιστα μόνο τη μια σφαίρα είναι να ανεβαίνετε τους ορόφους έναν-έναν και από κάθε όροφο να ρίχνετε τη σφαίρα μέχρι να σπάσει.

Όμως αυτός ο όροφος παίρνει εν γένει πολλές δοκιμές.

Προσπαθείστε να το κάνετε με όσο λιγότερες δοκιμές μπορείτε.

Απρίλιος 24, 2010

Τριγωνομετρική σειρά

Έστω ότι για κάποια ακολουθία a_n\geq0, η συνάρτηση f:\mathbb R\to\mathbb R, με f(x)=\displaystyle\sum_{n=1}^\infty a_n|\sin nx| είναι καλά ορισμένη (δηλαδή η σειρά συγκλίνει για κάθε x). Δείξτε ότι η f είναι συνεχής.

Διαγώνισμα πολλαπλής επιλογής

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

Ένα διαγώνισμα αποτελείται από n ερωτήσεις πολλαπλής επιλογής. Κάθε ερώτηση έχει 5 δυνατές απαντήσεις από τις οποίες μόνο μια είναι σωστή. Αν κάποιος απαντήσει σωστά μια ερώτηση παίρνει 1 μονάδα, ενώ αν απαντήσει λάθος χάνει 0,25 μονάδες. Ο διαγωνιζόμενος θεωρείται ότι πέτυχε στο διαγώνισμα αν πάρει συνολικά τουλάχιστον 0,5 n μονάδες.

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

Οκτώβριος 18, 2009

Οριακό σημείο

Υπάρχει υπακολουθία τής x_n=\sqrt{n}\sin n η οποία να συγκλίνει στο 0;

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

Απαγορευμένοι πίνακες

Έστω A ένας n\times n πίνακας από \heartsuit και \clubsuit. Υποθέτουμε ότι ο A δεν περιέχει κανένα 2\times 2 υποπίνακα που αποτελείται μόνο από \heartsuit. Βρείτε ένα άνω φράγμα για τον συνολικό αριθμό των \heartsuit.

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

Blog στο WordPress.com.

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