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

Μαρτίου 12, 2008

Πλήθος λέξεων από 0 και 1

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

Έστω f:{\mathbf Z}\to\{0,1\} και n\ge 1 φυσικός αριθμός τ.ώ. το πλήθος των λέξεων

f(x) f(x+1) \cdots f(x+n-1),\ \ \ x \in {\mathbf Z},

είναι \le n.
Δείξτε ότι η συνάρτηση f είναι περιοδική, ότι υπάρχει δηλαδή ακέραιος T\neq 0 ώστε
f(x+T) = f(x), για κάθε x\in {\mathbf Z}.

Advertisements

5 Σχόλια »

  1. Έστω n ο μικρότερος τέτοιος φυσικός που ικανοποιεί την παραπάνω ιδιότητα, m το πλήθος των λέξεων μήκους n και έστω k το πλήθος των λέξεων μήκους n-1. Έχουμε ότι k<=mn-1 γιατί διαφορετικά το n-1 θα ικανοποιούσε την παραπάνω ιδιότητα το οποίο δεν ισχύει γιατι ο n είναι ο μικρότερος φυσικός που το ικανοποιεί.

    Από τα παραπάνω προκύπτει k=m=n.

    Έστω τώρα ένας κατευθυνόμενος γράφος με k κορυφές όπου ο κάθε κορυφή αναπαριστά μια λέξη μήκους n-1 και m κατευθυνόμενες ακμές. Μια ακμή υπάρχει ανάμεσα σε δύο κορυφές μόνο αν μπορώ να αφαιρέσω τον πρώτο αριθμό στην αρχή της λέξης της 1ης κορυφής και να προσθέσω ένα κατάληλο αριθμό (0 ή 1) στο τέλος της έτσι ώστε να καταλήξω στη 2η.

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

    Τα παραπάνω ισχύουν για n>1. προφανώς για n=1 η πρόταση ισχύει γιατί f(x)=0 ή F(x)=1

    Μου αρέσει!

    Σχόλιο από ctzamos — Μαρτίου 21, 2008 @ 6:45 μμ

  2. Δεν ξέρω γιατί αλλά πάνω έφαγε κάτι χαρακτήρες.

    Ξαναγράφω το κομμάτι αυτό με λόγια

    Έχουμε ότι k μικρότερο ή ίσο του m μικρότερο ή ίσο του n. Όμως k μεγαλύτερο του n-1

    Μου αρέσει!

    Σχόλιο από ctzamos — Μαρτίου 21, 2008 @ 6:50 μμ

  3. Δυσκολεύομαι λίγο να καταλάβω:

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαρτίου 23, 2008 @ 12:59 πμ

  4. Κάθε λέξη μήκους n-1 έχει μια προηγούμενη και μια επόμενη.

    f(x)…f(x+n-2) έχει προηγούμενη την f(x-1)…f(x+n-3) και επόμενη την f(x+1)…f(x+n-1)

    Για οποιεσδήποτε 2 λέξεις (x, y) υπάρχει ένα μονοπάτι που να τις συνδέει. Άρα ο γράφος είναι συνδεδεμένος.

    Η ύπαρξη κύκλου δεν λέει κάτι για την ακολουθία. Το γεγονός όμως ότι ο γράφος είναι μόνο κύκλος λέει. Και αυτό γιατί για κάθε λέξη υπάρχει μοναδική επόμενη. Δλδ. αν για κάποια x,y ισχύει f(x+i) = f(y+i) για i = 0..n-2
    Τότε f(x+n-1) = f(y+n-1)
    Και επειδή μετά απο ακριβως n βήματα ξανακαταλήγουμε στην ίδια λέξη έχουμε f(x)=f(x+n) για κάθε x.

    Μου αρέσει!

    Σχόλιο από ctzamos — Μαρτίου 23, 2008 @ 7:48 μμ

  5. Ωραία, ας απλουστεύσω λίγο το επιχείρημα:

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

    Έπεται ότι μια λέξη μήκους n-1 δε μπορεί να είναι αρχικό κομμάτι δύο λέξεων μήκους n, γιατί τότε το πλήθος των λέξεων μήκους n-1 θα ήταν το πολύ n-1, που δεν ισχύει.

    Με άλλα λόγια, αν γνωρίζουμε μια λέξη μήκους n-1 τότε γνωρίζουμε μονοσήμαντα τη συνέχειά της προς τα δεξιά, μέχρι το άπειρο, και, με όμοιο επιχείρημα, προς το -\infty.

    Αφού το πλήθος των λέξεων με μήκος n-1 είναι n έπεται ότι στην άπειρή μας λέξη f μπορούμε να βρούμε δύο εμφανίσεις της ίδιας λέξης που να έχουν απόσταση T \le n (σχεδόν προφανές). Αυτό συνεπάγεται ότι f(x+T) = f(x) για κάθε x \in {\mathbf Z}.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαρτίου 23, 2008 @ 9:53 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

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