QUOTE(NBAholic @ Jul 23 2010, 03:36 )
[δόλωμα]ΟΚ, επόμενο πρόβλημα!
Έστω Χ φυσικός αριθμός, οποιουδήποτε μεγέθους. Αν ο Χ είναι ζυγός διαιρέστε με 2, αλλιώς πολλαπλασιάστε με 3 και προσθέστε 1. Με τον αριθμό που θα πάρετε, επαναλάβετε την ίδια διαδικασία, με τον επόμενο την ίδια, κ.ο.κ. Να αποδειχτεί αν ισχύει ότι για κάθε φυσικό Χ, ανεξαρτήτως του πόσο μεγάλος είναι ο αρχικός αυτός Χ, ακολουθώντας τη διαδικασία αυτή, θα καταλήγουμε στο τέλος πάντα στον αριθμό 1.[/δόλωμα]
Ομολογω οτι αυτο το προβλημα ηταν ΠΟΛΥ πιο δυσκολο απο το αλλο και μου πηρε λιγο να το λυσω.
Παμε λοιπον:
(
ΜΕΓΑΛΟ HINT: οι ν+1 μορφες κρατανε ενα κλειδι).
Οριζω:
Ν = {0,1,2,3,...}
Ν* = {1,2,3,...}
Το προβλημα ειναι ισοδυναμο με το να πουμε οτι η διαδικασια τερματιζει παντα με την ακολουθια αριθμων 4,2,1.
•Ακολουθια αριθμων Z(ΑΑΖ), ξεκινωντας απο εναν συγκεκριμενο αριθμο Τ, ονομαζεται η ακολουθια των αριθμων που προκυπτουν με βαση την διαδικασια που εγραψες και οριζεται ακριβεστερα ως εξης:
Τ,Τ1,Τ2,...,Τν με ν φυσικο και για καθε Τκ με κ απο 2 εως ν να ισχυει:
-Αν Τκ αρτιος τοτε Τκ+1=(Τκ)/2
-Αν Τκ περιττος τοτε Τκ+1 = (3Τκ)+1
Οπως επισης να ισχυει:
-Αν Τ αρτιος τοτε Τ1=Τ/2
-Αν Τ περιττος τοτε Τ1 = 3Τ+1
•Θετικη ακολουθια αριθμων Z(ΘΑΑΖ), ξεκινωντας απο εναν συγκεκριμενο αριθμο Τ, ονομαζεται η ακολουθια αριθμων Z για να φτασουμε στην ακολουθια 4,2,1 και οριζεται ακριβεστερα ως εξης:
Τ,Τ1,Τ2,...,Τν,4,2,1 με ν φυσικο και για καθε Τκ με κ απο 2 εως ν να ισχυει:
-Αν Τκ αρτιος τοτε Τκ+1=(Τκ)/2
-Αν Τκ περιττος τοτε Τκ+1 = (3Τκ)+1
Οπως επισης να ισχυει:
-Tν=1 ή Τν=8
-Αν Τ αρτιος τοτε Τ1=Τ/2
-Αν Τ περιττος τοτε Τ1 = 3Τ+1
•Αρνητικη ακολουθια αριθμων Z(ΑΑΑΖ) που αρχιζει απο Τ, ειναι μια ακολουθια αριθμων Z που αρχιζει απο Τ που δεν ειναι θετικη, που δεν καταληγει δηλαδη στην ακολουθια 4,2,1 οσες πραξεις και να κανουμε.
Ενα φυσικος αριθμος Τ λεμε οτι ικανοποιει την διαδικασια που εγραψες(και καταληγει στο 1) αν και μονο αν υπαρχει θετικη ακολουθια αριθμων Z, ξεκινωντας απο το Τ.
Θεωρημα-Α1:Ξερουμε οτι αν εχουμε μια θετικη ακολουθια αριθμων Z που αρχιζει με εναν συγκεκριμενο αριθμο (και τερματιζει-προφανως λογω ορισμου) και αυτος ο αριθμος αποτελει εναν ορο μιας ακολουθιας αριθμων Z που αρχιζει απο Τ, τοτε και η ακολουθια αυτη ειναι θετικη ακολουθια αριθμων Z που αρχιζει απο Τ.
Πχ ξερουμε οτι το 5 τερματιζει(η ΑΑΖ που αρχιζει απο 5 ειναι θετικη) καθως 5,16,8,4,2,1.
Επισης ξερουμε οτι η ΑΑΖ που αρχιζει απο 20 παει: 20,10,5. Οποτε και αυτη θα τερματιζει.
Θεωρημα-Α2:Αν μια ακολουθια αριθμων Z που αρχιζει απο Τ ειναι αρνητικη, τοτε θα ισχυει Τ = 4κ-1 για καποιο κ στο {1,2,3,...}.
Αποδειξη(με την μεθοδο της ισχυρης μαθηματικης επαγωγης):Για Τ = 1 εχουμε οτι η ΑΑΖ που αρχιζει απο 1 ειναι θετικη αφου η ΑΑΖ της ειναι 1,4,2,1.
Θα αποδειξουμε οτι αν η ΑΑΖ που αρχιζει απο Τ ειναι θετικη για Τ=1 εως Τ=ν-1, τοτε ειναι θετικη και για Τ=ν.
Εστω λοιπον οτι οι ΑΑΖ που αρχιζουν απο Τ ειναι θετικες για Τ=1 εως Τ=ν-1 για καποιο ν φυσικο μεγαλυτερο του 1.
Ισχυει οτι καθε φυσικος ν μπορει να γραφει με ακριβως εναν απο τους εξης τροπους:
4κ+1, 4κ+2,4κ+3,4κ+4 για κ να ανηκει στο {0,1,2,3,...}
-Για ν = 4κ+4:Η ΑΑΖ που αρχιζει απο ν θα εχει επομενο μελος του ν το (4κ+4)/2 = 2κ+2 και ισχυει 2κ+2 < ν αρα ειναι θετικη.
-Για ν = 4κ+2:Η ΑΑΖ που αρχιζει απο ν θα εχει επομενο μελος του ν το (4κ+2)/2 = 2κ+1 και ισχυει 2κ+1 < ν αρα ειναι θετικη.
-Για ν = 4κ+1:Η ΑΑΖ που αρχιζει απο ν θα εχει επομενο μελος του ν το 3(2·2κ+1)+1 = 12κ+4 και επομενο μελος το 6κ+2 και επομενο το 3κ+1 και ισχυει 3κ+1 < ν αρα ειναι θετικη.
Επομενως καθε ΑΑΖ που αρχιζει απο 4κ+4 ή 4κ+2 ή 4κ+1 ειναι θετικη.
Αρα μια ακολουθια που ειναι αρνητικη δεν μπορει να ειναι της μορφης 4κ+4 ή 4κ+2 ή 4κ+1.
Οποτε μια ακολουθια που ειναι αρνητικη θα ειναι της μορφης 4κ+3 με κ φυσικο.
Το παραπανω ειναι ισοδυναμο με το:
Οποτε μια ακολουθια που ειναι αρνητικη θα ειναι της μορφης 4κ-1 με κ φυσικο μεγαλυτερο του μηδενος.
Αποδειξη για αυτο:
Α = 4κ+3 με κ στο Ν <=> Α = 4ε-1 με ε στο Ν*
Αν Α=4κ+3 με κ στο Ν τοτε ψαχνω να βρω ε στο Ν* ετσι ωστε Α=4ε-1 δηλαδη ψαχνω να βρω ε στο Ν* ετσι ωστε:
4κ+3 = 4ε-1 <=> ε=κ+1 και αφου κ>=0=> κ+1>=1 αρα βρεθηκε ε στο Ν* ετσι ωστε να ισχυει η =>
Αν Α=4ε-1 με ε στο Ν* τοτε ψαχνω να βρω κ στο Ν ετσι ωστε Α=4κ+3 δηλαδη ψαχνω να βρω κ στο Ν ετσι ωστε:
4κ+3 = 4ε-1 <=> κ=ε-1 και αφου ε>=1=> ε-1>=0 => κ>=0 αρα βρεθηκε κ στο Ν ετσι ωστε να ισχυει η <=
ΟΕΔ.Οποτε:
Οποτε μια ακολουθια που ειναι αρνητικη θα ειναι της μορφης 4κ-1 με κ στο Ν*.
Λογω του θεωρηματος Α1 τωρα, βλεπουμε οτι μια ΑΑΑΖ που αρχιζει με καποιον αριθμο 4κ-1 με κ στο Ν*, πρεπει να περιεχει αριθμους μόνο αυτης της μορφης, ειδαλλως δεν θα ηταν αρνητικη. Αν δηλαδη περιεχει σαν μελος της καποιον αριθμο του οποιου η ΑΑΖ ξεκινωντας απο αυτον ειναθ θετικη, τοτε και η αρχικη ακολουθια δεν θα ηταν αρνητικη αλλά θετικη.
Πρεπει δηλαδη μια αρνητικη ακολουθια αριθμων Z να αποτελειται
μόνο απο αριθμους της μορφης 4κ-1 με κ στο Ν*.
(Θεωρημα-Α3)•Οριζουμε ως ΧΑΑΖ που αρχιζει απο Τ, μια ακολουθια αριθμων που προκυπτουν απο μια ΘΑΑΖ που αρχιζει απο Τ (Τ,Τ1,Τ2,Τ3,...,Τν,4,2,1), στην οποια θα εξαλειψουμε τα στοιχεια της Χκ με κ απο 2 εως ν+3(Χ1=Τ, Χ2=Τ1,...,Χν+3=2,Χν+4=1) για τα οποια ισχυει: Χκ = 2φ με φ στο Ν*, δηλαδη θα εξαλειψουμε τα αρτια στοιχεια.
Πχ για την ΘΑΑΖ: 7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 εχουμε την αντιστοιχη ΧΑΑΖ της:
7,11,17,13,5,1
Ειναι τελειως προφανες οτι μια ακολουθια ΑΑΖ ειναι θετικη εαν και μονο αν η αντιστοιχη ΧΑΑΖ της περιεχει το 1 ως
ψηφιο.
(Θεωρημα-Α4)Ενω μια ακολουθια ΑΑΖ ειναι αρνητικη εαν και μονο αν η αντιστοιχη ΧΑΑΖ της δεν περιεχει πουθενα το ψηφιο 1.
Δηλαδη το προβλημα μπορει και να λυθει με βαση την ΧΑΑΖ, αν αποδειξουμε οτι καθε ΧΑΑΖ περιεχει παντα ή οχι το ψηφιο 1.
Εχουμε λοιπον:Υποθετουμε οτι υπαρχει ΑΑΑΖ που αρχιζει απο Τ, που θα ειναι φυσικα της μορφης 4κ-1 με κ στο Ν*.
Τοτε το επομενο νουμερο της ειναι το 3(4κ-1)+1 = 12κ-2 και αρα το επομενο νουμερο της ΧΑΑΖ της θα ειναι 6κ-1.
Και φυσικα θα ειναι της μορφης 4κ-1 για καποιο αλλο κ αυτη τη φορα δηλαδη θα ισχυει:
4κ'-1 = 6κ-1 με κ' στο Ν*.
Δηλαδη 2κ' = 3κ αρα κ'=3α1 και κ=2α2 με α1,α2 στο Ν*
Αρα η τελικη μορφη θα ειναι ενα νουμερο της μορφης 12·α2-1
Και αυτο ειναι το 3 νουμερο της ΑΑΑΖ και 2ο της ΧΑΑΖ.
Αρα σκεφτομενοι αναποδα βλεπουμε οτι το 2ο νουμερο της ΑΑΑΖ ειναι το 24·α2-2 και το 1ο της ΑΑΑΖ και της ΧΑΑΖ ειναι το 8·α2-1 με α2 στο Ν*.
◘Δηλαδη το πρωτο νουμερο μιας ΑΑΑΖ και μιας ΧΑΑΖ βρηκαμε οτι οχι μονο εχει την μορφη 4κ-1 αλλά εχει και την μορφη 8κ-1 με κ στο Ν*.
Επαναλαμβανοντας την διαδικασια δειχνουμε ευκολα οτι:
◘Δηλαδη το πρωτο νουμερο μιας ΧΑΑΖ οχι μονο εχει την μορφη 4κ-1 και την 8κ-1 αλλά εχει και την μορφη 16κ-1 με κ στο Ν*.
Και μπορουμε να ξανα-δειξουμε οτι:
◘Το πρωτο νουμερο μιας ΧΑΑΖ εχει την μορφη 4κ-1, την μορφη 8κ-1, την 16κ-1 αλλά εχει και την μορφη 32κ-1 με κ στο Ν*.
Και γενικα, με μια απλη επαγωγη αυτη τη φορα, δειχνουμε πολυ ευκολα οτι:
◘Το πρωτο νουμερο Τ μιας ΑΑΑΖ εχει τις εξης ν+1 μορφες
: Τ = 4·(2^ν)·κ-1 για καθε ν στο Ν με κ στο Ν*.
Ομως το ν αυξανει απεριοριστα δηλαδη το Τ γινεται απεριοριστα μεγαλο, καθως η διαδικασια επαναλαμβανεται απειρες φορες για καθε ν στο Ν, οποτε το Τ δεν ειναι πεπερασμενο.
Οποτε μια ΧΑΑΖ δεν μπορει να αρχιζει με πεπερασμενο αριθμο ουτε(θεωρημα Α3) και να περιλαμβανει στους ορους της καποιον πεπερασμενο αριθμο.
Αρα δεν μπορει να εχει σαν ορο της το 1.
Οποτε(θεωρημα Α4) και δεν μπορει να υπαρξει ΑΑΑΖ.
Αρα ολες οι ΑΑΖ ειναι θετικες.
Αρα αποδειχτηκε οτι η διαδικασια που περιεγραψες τερματιζει παντα στο 4,2,1 δηλαδη στο 1.