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

Οκτώβριος 12, 2018

Απλά γραφήματα

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 3:52 μμ

Την άσκηση (η οποία οφείλεται στον Adolph Winkler Goodman) προτείνει ο Κ. Κουρουζίδης.

Έστω G ένα απλό γράφημα (χωρίς loops και περισσότερες από μια ακμές που να συνδέουν οποιεσδήποτε δύο κορυφές) με n κορυφές.
Έστω t(G) ο συνολικός αριθμός τριγώνων στο G και στο \overline G (το γράφημα που είναι το συμπλήρωμα του G) μαζί.
Αποδείξτε ότι: t(G)=\binom{n}{3}-(n-2)e(G)+\sum_{v\in V(G)}\binom{d(v)}{2},
όπου:
e(G) είναι το πλήθος των ακμών.
V(G) είναι το σύνολο των κορυφών του G.
v είναι η εκάστοτε κορυφή.
d(v) είναι ο βαθμός της εκάστοτε κορυφής.

 

Υπόδειξη: Αναλογιστείτε την συνεισφορά σε κάθε ακμή από κάθε τριάδα κορυφών.

 

Advertisements

Αύγουστος 30, 2018

Μια ταυτότητα

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 12:00 μμ

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

Χρησιμοποιώντας πλήρη γραφήματα και βασικές αρχές απαρίθμησης αποδείξτε ότι

\displaystyle{\binom{n}{2}=\binom{k}{2}+k(n-k)+\binom{n-k}{2}}

για k\leq n.

 

Ιουλίου 26, 2018

Μήκος γραφήματος

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 4:14 μμ

Δείξτε ότι το μήκος τού γραφήματος μιας γνησίως αύξουσας συνάρτησης από το [0,1] στο [0,1] είναι το πολύ 2, και ότι το φράγμα αυτό «πιάνεται» από κάποια συνάρτηση. Ποιο είναι το καλύτερο άνω φράγμα για το μήκος τού γραφήματος μιας κυρτής συνάρτησης από το [0,1] στο [0,1];

Οκτώβριος 12, 2017

Υπερκύβος

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 1:40 μμ

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

Ο mδιάστατος υπερκύβος Q_m είναι το γράφημα με σύνολο κομβών όλα τα δυαδικά διανύσματα μήκους m. Δύο κόμβοι είναι συνδεδεμένοι με ακμή ακριβώς όταν διαφέρουν σε μία θέση οι συντεταγμένες τους. Ο γράφος ορίζεται αναδρομικά, αν πάρουμε δύο αντίτυπα μιας διάστασης μικρότερης (δηλαδή δύο Q_{m-1}), θέσουμε την πρώτη συντεταγμένη του ενός αντιτύπου να είναι 0 και του δεύτερου 1, και ακολούθως ενώσουμε τις αντίστοιχες κορυφές. Θα μπορούσαμε όμως αυτό να το κάναμε με οποιαδήποτε άλλη από τη πρώτη συντεταγμένη, έτσι έχουμε συνολικά 2m υποκύβους μιας διάστασης μικρότερης (Υποκύβος ονομάζεται οποιοσδήποτε υπερκύβος μικρότερης διάστασης που είναι υπογράφημα στο Q_m ).

Στο Q_m υπάρχουν υποκύβοι Q_j όλων των διαστάσεων, για 1\leq j\leq m . Πόσοι είναι αυτοί για κάθε j; Αν αθροίσουμε τις ακμές όλων των υποκύβων από j=1 έως m, ποιό είναι το αποτέλεσμα;

Υποόδειξη: Υπολογίστε το ζητούμενο άθροισμα με τον προφανή τρόπο, αφού βρείτε πρώτα το πλήθος των υποκύβων διάστασης j , και πόσες ακμές έχει οποιοδήποτε από τα Q_j. Ακολούθως εκφράστε ξανά το ζητούμενο άθροισμα, αναλογιζόμενοι το πόσες φορές προσμετράται μια οποιαδήποτε ακμή, χρησιμοποιώντας ένα συμμετρικό επιχείρημα. Απλοποιήστε. Τί παρατηρείτε;

 

Ιουνίου 30, 2016

Γινόμενα Borel

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 4:38 μμ

Αν ο X είναι ένας μετρικός χώρος με \mathcal B(X) συμβολίζουμε τη σ-άλγεβρα των συνόλων Borel και με \mathcal B(X)\otimes\mathcal B(X) τη σ-άλγεβρα που παράγεται από όλα τα ορθογώνια A\times B όπου τα A,B είναι Borel υποσύνολα τού X. Δεν είναι δύσκολο να δει κανείς ότι

\mathcal B(\mathbb R\times \mathbb R)=\mathcal B(\mathbb R)\otimes\mathcal B(\mathbb R).

Ισχύει το ίδιο με ένα αυθαίρετο μετρικό χώρο στη θέση τού \mathbb R;

Ορθοκανονικό σύνολο

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 2:13 πμ

Ας είναι S ένα ορθοκανονικό υποσύνολο τού L^2([0,1]) το οποίο αποτελείται από συνεχείς συναρτήσεις. Θέτουμε Y=\overline{\langle S \rangle}, όπου \langle\cdot\rangle είναι η γραμμική θήκη. Δείξτε ότι αν υπάρχει σταθερά C>0 τέτοια ώστε

\displaystyle{\sup_{f\in Y,\ f\ne0}\frac{\|f\|_\infty}{\|f\|_2}\leq C}, τότε ο Y έχει πεπερασμένη διάσταση.

Μαρτίου 7, 2016

Argument

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 3:16 μμ

Αν 0<p<1 και u>0, βρείτε μια εκτίμηση για το όρισμα τού μιγαδικού αριθμού

\displaystyle{pe^{-iu\sqrt{\frac{1-p}{p}}}+(1-p)e^{iu\sqrt{\frac{p}{1-p}}}}

Ιανουαρίου 1, 2016

Ροπές και διαμερίσεις

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 8:35 μμ

Το ερώτημα θέτει ο Κ. Κουρουζίδης. Η ροπή  2n τάξης τής τυποποιημένης κανονικής κατανομής είναι ίση με το πλήθος των διαμερίσεων σε 2-σύνολα ενός συνόλου με 2n στοιχεία. Είναι αυτό μια αριθμητική σύμπτωση;

 

Ιουνίου 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 και κανείς δεν έκανε το παραμικρό. Το φέρνω λοιπόν πάνω μήπως και έχει καλύτερη τύχη τώρα.

Ιουνίου 10, 2015

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

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

gradcall

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

Μαΐου 12, 2015

Euler Φ – μέρος δεύτερο

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 1:03 πμ

Το πρόβλημα προτείνει ο Κωνσταντίνος Κουρουζίδης. Υπάρχει  ή όχι ακολουθία φυσικών n_i τέτοια ώστε \frac{\phi(n_1)}{n_1}=\frac{\phi(n_2)}{n_2}=\frac{\phi(n_3)}{n_3}=\cdots;

Απρίλιος 20, 2014

Αναγκαστικά ισομετρία

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

Μια συνεχής συνάρτηση f:X\to X από ένα συμπαγή μετρικό χώρο στον εαυτό του έχει την ιδιότητα ότι δε μικραίνει τις αποστάσεις:

Για κάθε x, y \in X έχουμε d(f(x), f(y)) \ge d(x, y) (εδώ d(\cdot,\cdot) είναι η μετρική του χώρου X).

Δείξτε ότι η f είναι ισομετρία: d(f(x), f(y)) = d(x, y) για κάθε x, y \in X.

(Αν έχετε πρόβλημα με την έννοια «συμπαγής μετρικός χώρος» μπορείτε να σκέφτεστε το X σαν ένα κλειστό και φραγμένο υποσύνολο του Ευκλείδιου χώρου με τη συνηθισμένη Ευκλείδια μετρική.)

Μαρτίου 12, 2014

Όριο με τον ορισμό

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 12:11 πμ

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

Βρείτε το ελάχιστο n_0 στον \varepsilon-n_0 ορισμό τού ορίου

\displaystyle \lim_{n\to+\infty}\frac{\ln n}{n}=0.

Ιουνίου 18, 2013

Διασπορά και Διάταξη

Filed under: Άλυτα Προβλήματα — Michalis Loulakis @ 6:10 μμ

Το πρόβλημα αυτό πρότεινε ο Χρήστος Πελέκης

Αν X_1,X_2,\ldots,X_n είναι τυχαίες μεταβλητές και X_{(1)},X_{(2)},\ldots,X_{(n)} είναι μια αναδιάταξή τους ώστε X_{(1)}\le X_{(2)}\le\cdots\le X_{(n)}, δείξτε ότι

\displaystyle \text{Var}(X_1)+\text{Var}(X_2)+\cdots+\text{Var}(X_n)\ge \text{Var}(X_{(1)})+\text{Var}(X_{(2)})+\cdots+\text{Var}(X_{(n)})

 

Μαΐου 31, 2013

Γρήγορος υπολογισμός διαμέτρου

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

Αν έχουμε x_1,\ldots,x_N σημεία σε ένα μετρικό χώρο X, όπου με d(x,y) συμβολίζουμε την απόσταση (μετρική) ανάμεσα στα σημεία x, y \in X, τότε αν θέλουμε να υπολογίσουμε τη διάμετρο του συνόλου A=\{x_1,\ldots,x_N\}

{\mathrm {diam}}(A) = \max\{d(x,y): x,y \in A\}

εκ πρώτης όψεως φαίνεται να χρειάζεται λίγο-πολύ να υπολογίσουμε όλες τις αποστάσεις d(x_i, x_j). Αν υποθέσουμε ότι κάθε υπολογισμός απόστασης παίρνει χρόνο μια μονάδα, τότε ο συνολικός χρόνος που ξοδεύουμε είναι τετραγωνικός, δηλ. της τάξης του N^2.

  1. Αν ο μετρικός μας χώρος είναι ο X={\mathbf R}^k, όπου k είναι μια σταθερά που δεν αλλάζει με το N, και με μετρική την

               d_\infty(x, y)= \max_{j=1,\ldots,k} |x_j-y_j|

    δείξτε ότι η διάμετρος του συνόλου A μπορεί να υπολογιστεί πολύ γρηγορότερα, σε γραμμικό χρόνο \le C_k N, όπου C_k είναι μια σταθερά που δεν εξαρτάται από το N αλλά μόνο από το k.

  2. Το ίδιο αν ο μετρικός χώρος είναι και πάλι το {\mathbf R}^k με μετρική τώρα την

              d_1(x,y) = \sum_{j=1}^k |x_j-y_j|.

Απρίλιος 17, 2013

Παραγοντικά και συνημίτονα

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 4:04 μμ

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

Συγκλίνει η ακολουθία \cos(n!) ;

 

Απρίλιος 4, 2013

Ανισότητα

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 1:28 μμ

Ένα πρόβλημα από τον Αλέξανδρο Γαλανάκη.

Έστω p>1, και a_1,\dots,a_n,b_1,\dots,b_n μη αρνητικοί αριθμοί τέτοιοι ώστε a_1^p-a_2^p-\dots-a_n^p>0 και b_1^p-b_2^p-\dots-b_n^p>0. Δείξτε ότι

\displaystyle\left(a_1^p-a_2^p-\dots-a_n^p\right)^{1/p}+\left(b_1^p-b_2^p-\dots-b_n^p\right)^{1/p}\leq\left[(a_1+b_1)^p-(a_2+b_2)^p-\dots-(a_n+b_n)^p\right]^{1/p}

 

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

Οι εφτά νάνοι

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 1:18 πμ

Ένα ακόμη πρόβλημα από τον Γιώργο Παπαδόπουλο.

Οι  εφτά νάνοι κάθονται σ’ ένα στρογγυλό τραπέζι και καθένας έχει μια κούπα. Κάποιες κούπες έχουν γάλα. Κάθε νάνος με τη σειρά, μοιράζει το γάλα του εξίσου στους υπόλοιπους έξι. Αφού τελειώσουν, διαπιστώνουν ότι κάθε κούπα έχει την αρχική ποσότητα. Πόσο γάλα έχει κάθε κούπα, αν η συνολική ποσότητα είναι 42 ουγγιές;

Σεπτεμβρίου 29, 2012

Χρωματιστά νομίσματα

Filed under: Άλυτα Προβλήματα — Michalis Loulakis @ 12:00 πμ
Το πρόβλημα αυτό πρότεινε ο Χρήστος Πελέκης
 
Σταθεροποιήστε φυσικό αριθμό ν, και θεωρήστε ν το πλήθος τίμια νομίσματα έχουν χρωματιστεί με ν χρώματα ως ακολούθως:
Για i=1,2,…,ν-1, οι πλευρες του νομισματος i  εχουν  χρωματιστει με τα χρώματα i και i+1 και το νόμισμα ν έχει χρωματιστει με τα χρώματα ν και 1.
 

Στρίψτε όλα τα νομίσματα και ονομάστε X_\nu  το πληθος των διαφορετικών χρωμάτων που βλέπουμε μετά το στρίψιμοΠοια είναι η κατανομή της X_\nu

Μαρτίου 2, 2012

Αθροίσματα δυνάμεων

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

Έχουμε

S_k = \sum_{j=1}^N a_j b_j^k για k=1,2,\ldots,

όπου a_j, b_j \in {\mathbb R}, όλα τα a_j είναι διάφορα του 0 και όλα τα b_j είναι διάφορα μεταξύ τους.

Δείξτε ότι από οι αριθμοί S_1, S_2, \ldots, S_{2N} καθορίζουν μονοσήμαντα τα a_j, b_j (εκτός από μετάθεση).

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

Blog στο WordPress.com.

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