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

Ιουλίου 22, 2015

Στο πνεύμα των ημερών.

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

Στο μακάβριο πνεύμα των σχολίων της προηγούμενης ανάρτησης, Ν στρατιώτες πυροβολούν Ν κατάδικους. 1. Κάθε στρατιώτης πυροβολεί ακριβώς ένα κατάδικο και είναι 100% εύστοχος. 2. Κανένας κατάδικος δεν πυροβολείται από περισσότερους από ένα στρατιώτη (εκτός από τον Herr Schäuble που θέλει ομοβροντία). Ποια η πιθανότητα k στρατιώτες να πυροβολήσουν τους κατάδικους που είναι απέναντι τους; Και για να το καταλάβει και ο μπακάλης της γειτονιάς, ποια η πιθανότητα μια τυχαία μετάθεση να έχει k σταθερά σημεία;

Ιουλίου 20, 2015

Επί

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

Έστω A και B δυο πεπερασμένα σύνολα με το B να έχει το πολύ τόσα στοιχεία όσα και το A. Διαλέγουμε στην τύχη μια συνάρτηση από το A στο B. Ποια η πιθανότητα να είναι επί;

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

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

Για κάθε δυαδικό διάνυσμα 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.

Ιουλίου 1, 2015

Εδώ ο κόσμος χάνεται…

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

… και εμείς υπολογίζουμε αθροίσματα!!!     Αν οι αριθμοί x_1,x_2,\dots,x_n έχουν άθροισμα μηδέν και είναι όλοι απόλυτα φραγμένοι από μια θετική σταθερά c, τότε υπάρχει αναδιάταξη x_1=x_{k_1},x_{k_2},\dots,x_{k_n} τέτοια ώστε  \displaystyle\left|\sum_{j\leq i} x_{k_j}\right|\leq c για κάθε i. Το πρόβλημα πρότεινε ο Κωνσταντίνος Κουρουζίδης.

Ιουνίου 30, 2015

Πόσο μπορεί να επηρεάσει το νόμισμα;

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

greek-euro    drachma

Δύο φίλοι, ο Β και ο S, παίζουν ένα παιχνίδι με κέρματα. Ο κάθε ένας από τους δύο έχει τα δικά του κέρματα. Ο κάθε ένας από τους δύο ρίχνει όλα τα κέρματά του (μια φορά) και κερδίζει όποιος έφερε τις περισσότερες κορώνες.

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

Πόσο επηρεάζεται η πιθανότητα να κερδίσει ο Β τον S από το γεγονός ότι έχει ένα κέρμα παραπάνω;

Ιουνίου 28, 2015

Πάντα θετικό

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

positive

Δείξτε ότι το πολυώνυμο

p(x) = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + \cdots + \frac{x^{2n}}{(2n)!}

είναι πάντα θετικό (για κάθε x\in{\mathbb R}, n=1, 2, \ldots).

Ιουνίου 26, 2015

Χαοτικός χρωματισμός

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

colored-row

Έχουμε 1000 κουτιά στη σειρά (στις θέσεις 1, 2, 3, … , 1000).

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

Ιουνίου 21, 2015

Αλυσίδα υποσυνόλων

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

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

nested

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

Ιουνίου 19, 2015

Μπάλες σε χρωματιστά κουτιά

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

f

Έχουμε n αριθμημένες μπάλες (n>2) και κάμποσα, επίσης αριθμημένα, χρωματιστά κουτιά, κάποια από τα οποία είναι βαμμένα κόκκινα, κάποια μπλε και κάποια είναι άβαφα (υπάρχουν και από τα τρία είδη κουτιών).

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

Δείξτε ότι πάντα A \neq B.

Ιουνίου 18, 2015

Απεριοδική Πλακόστρωση

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

lattice-set

Κατασκευάστε σύνολα A, B \subseteq {\mathbf Z}^2 τέτοια ώστε

  1. Το σύνολο A είναι πεπερασμένο,
  2. Κάθε u \in {\mathbf Z}^2 γράφεται κατά μοναδικό τρόπο ως άθροισμα
    u = a +b, με a \in A, b \in B,
  3. Δεν υπάρχει διάνυσμα u \in {\mathbf Z}^2\setminus\{0\} τέτοιο ώστε B = B+u.

Το παρακάτω το είχα αναρτήσει το 2008 και κανείς δεν έκανε το παραμικρό. Το φέρνω λοιπόν πάνω μήπως και έχει καλύτερη τύχη τώρα.

Ιουνίου 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 τέτοιες μεταβάσεις, όσες και οι χάντρες του κολιέ. Άρα ένας άλλος τρόπος να πει κανείς το ίδιο πράγμα είναι ότι όπως κινούμαστε γύρω-γύρω στο κολιέ δε θα δούμε ποτέ την ίδια διαδοχή χρωμάτων ξανά σε μια πλήρη μας διάσχιση του κολιέ.)

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

Ιουνίου 16, 2015

Μικρό σύνολο, όπου υπάρχουν όλες οι αποστάσεις

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

Κατασκευάστε ένα σύνολο E \subseteq {\mathbb R} που να είναι μια ένωση διαστημάτων με συνολικό μήκος το πολύ 1

intervals

και τέτοιο ώστε για κάθε πραγματικό αριθμό d να υπάρχουν δύο στοιχεία x, y \in E με

x-y=d.

Ιουνίου 15, 2015

Ο ελάχιστος κύκλος που περικλείει κάποια σημεία

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

Ας είναι p_1, p_2, \ldots, p_N σημεία του επιπέδου. Δείξτε ότι κύκλος ελαχίστου εμβαδού που τα περιέχει είναι μοναδικός.

enclosing-circle

Ιουνίου 13, 2015

Wiener

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

Το πρόβλημα προτείνει ο Κωνσταντίνος Κουρουζίδης.

Αν \mathcal D  είναι μια πεπερασμένη οικογένεια δίσκων, τότε υπάρχει υπο-οικογένεια ξένων ανά δυο δίσκων τέτοια ώστε αν φουσκώσουμε κάθε μέλος της τρεις φορές, τότε η ένωση των φουσκωμένων καλύπτει την \mathcal D.

Ιουνίου 12, 2015

Το περπάτημα του μεθυσμένου

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

Κάποιος που έχει πιει πολύ και μόλις βγήκε από το bar περπατάει με τον παρακάτω περίεργο τρόπο.

walk

Σε κάθε χρονική στιγμή κάνει πρώτα μια στροφή κατά a=10 μοίρες γύρω από το σημείο όπου βρίσκεται η πόρτα του bar και αμέσως μετά κινείται κατά το σταθερό διάνυσμα v. Και ξανά στροφή γύρω από την πόρτα του bar κατά 10 μοίρες και πάλι μετακίνηση κατά το διάνυσμα v.

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

Ιουνίου 11, 2015

Ληστές επτά, με κάμποσα λεφτά

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

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

padlocks

Τι θα γίνει π.χ. αν σηκωθεί ένας από αυτούς τα πάρει και φύγει; Αυτό φυσικά δεν είναι αποδεκτό στην ομάδα. Ή αν δύο από αυτούς συμφωνήσουν μεταξύ τους και τα πάρουν και φύγουν; Ούτε κι αυτό είναι αποδεκτό.

Όμως πρόκειται για μια ομάδα κλεφτών μεγαλωμένη από τους γονείς τους με πίστη στα δημοκρατικά ιδεώδη. Αν λοιπόν κάποιοι 4 από αυτούς αποφασίσουν να τα πάρουν αυτό γίνεται αποδεκτό γιατί οι 4 είναι πλειοψηφία στους 7. Όχι όμως 3 ή λιγότεροι.

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

Πρέπει λοιπόν να δώσουμε σε κάθε κλέφτη ένα σετ από κλειδιά με τέτοιο τρόπο ώστε:

  1. Οποιοιδήποτε 4 κλέφτες να έχουν μεταξύ τους όλα τα κλειδιά που απαιτούνται για να ανοίξει το χρηματοκιβώτιο.
  2. Για οποιουσδήποτε 3 κλέφτες αυτό δε συμβαίνει.

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

Προσδιορισμός τετραγώνου από σημεία στις πλευρές του

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

Το παρακάτω προτάθηκε από το Γ. Ριζόπουλο:

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

«Έτσι, και να φυσήξει αέρας και να μας πάρει τα παλούκια και την κορδέλα, θα μπορέσουμε να ξαναφτιάξουμε ακριβώς (κατά μέγεθος ΚΑΙ θέση) το τετράγωνο» χωρίς να ξαναφωνάξουμε τον τοπογράφο. Mας αρκεί η μετροκορδέλα μας!

Έχει δίκιο ο μηχανικός;

Διχοτόμηση σχήματος L

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

Έχετε ένα χαρτί σχήματος L.

l-shape

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

Ιουνίου 10, 2015

Μερικές μέρες έμειναν ακόμη …

Filed under: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 9:31 πμ

gradcall

Τη Δευτέρα 15/6/2015 λήγει η προθεσμία υποβολής υποψηφιοτήτων για τα μεταπτυχιακά προγράμματα του Τμήματός μας.

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

The Rubric Theme. Blog στο WordPress.com.

Follow

Ενημερωθείτε για κάθε νέα δημοσίευση στο email σας.

Μαζί με 33 ακόμα followers

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