Τέσσερα μηδενικά

[ealexiou]

Στην γνωστή ακολουθία και να βρεθεί
ο μικρότερος θετικός ακέραιος για τον οποίο ο τελειώνει σε μηδενικά.

Ευθύμης

[Demetres]

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

Για την εύρεση του μικρότερου τέτοιου αριθμού θα ήθελα όντως να δω λύση κατάλληλη (*) για αυτόν τον φάκελο.

(*) Δηλαδή και με λίγες πράξεις αλλά και χωρίς πολλή αριθμοθεωρία.

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

Βάλτε τον πιο κάτω κώδικα εδώ και πατήστε "evaluate" για να το επιβεβαιώσετε.

Κώδικας: Επιλογή όλων

v=[0,1]
i=1
while (v[i]%10000 != 0):
    i=i+1
    v.append(v[i-1]+v[i-2])
print i

[ealexiou]

Υπερβολικό το ζητούμενο για τον συγκεκριμένο φάκελλο (δεν γνωρίζω σε ποιον φάκελλο πρέπει να πάει, αν πρέπει να πάει κάπου), για να το λέει ο Δημήτρης έτσι θα είναι, οπότε το τροποποιώ σε:

Στην γνωστή ακολουθία και να βρεθεί ο μικρότερος θετικός ακέραιος για τον οποίο ο τελειώνει σε:
α) μηδενικό. β) μηδενικά.

[Mihalis_Lambrou]

υπάρχει αριθμός Fibonacci ο οποίος λήγει σε τέσσερα μηδενικά. (Το αφήνω ως άσκηση.)

Ενδιαφέρον.

Για τυπογραφική ευκολία θα γράφω για τον (ή όσα μηδένικά θέλουμε).

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

Άρα ισχύει , που είναι σαν την αλλά "μία μονάδα πιο κάτω".

Επαγωγικά είναι και άρα οπότε και , που είναι το ζητούμενο.

Φιλικά,

Μιχάλης

[ealexiou]

Για την εύρεση του μικρότερου τέτοιου αριθμού θα ήθελα όντως να δω λύση κατάλληλη (*) για αυτόν τον φάκελο.

(*) Δηλαδή και με λίγες πράξεις αλλά και χωρίς πολλή αριθμοθεωρία.

Ναι, υπάρχει τρόπος να βρεθεί ο για τον οποίο ο αντίστοιχος είναι , που πράγματι είναι ο , με ελάχιστες και σχετικά εύκολες πράξεις και με χρήση μιας ιδιότητας των αριθμών Φιμπονάτσι.

[ealexiou]

Eύρεση αριθμού μικρότερου θετικού αριθμού για τον οποίο ο τελειώνει:
α) σε μηδενικό β) σε γ) σε δ) σε μηδενικά.
Κάνω σε όλες τις περιπτώσεις χρήση της ιδιότητας, των αριθμών Φιμπονάτσι,
κάποιος ακέραιος αριθμός.

α) O μικρότερος πολλαπλάσιος του αριθμός είναι ο και του είναι ο , οπότε ο μικρότερος είναι ο και πράγματι στον πίνακα των αριθμών Φιμπονάτσι βλέπω και δεν υπάρχει μικρότερος από αυτόν.

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

γ) Για το πάλι ο (το που μας περίσσεψε από πριν, το χρησιμοποιούμε τώρα) και ο μικρότερος είναι ο , άρα ο ζητούμενος αριθμός είναι ο

δ) . Ο μικρότερος είναι ο και ο μικρότερος είναι ο , άρα ο μικρότερος είναι ο

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

Πηγή: Το θέμα είναι από το του κ. Ρωμανίδη. Το έθεσε ο Γιώργος Ριζόπουλος και το έλυσε ο Θανάσης Παπαδημητρίου (papadim), συνάδελφοι Πολιτικοί μηχανικοί ΕΜΠ.

[Demetres]

Το κριτήριο ισχύει μόνο όταν πρώτοι μεταξύ τους. (Π.χ. Το δεν είναι πολλαπλάσιο του .)

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

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

Ευτυχώς υπάρχει ένα άλλο πιο ισχυρό κριτήριο που βοηθάει. Αυτό το κριτήριο λέει ότι .

Έτσι έχουμε . Άρα το δεν είναι πολλαπλάσιο του και άρα δεν μπορεί να λήγει σε τέσσερα μηδενικά.

Αυτό το επιπλέον κριτήριο είναι αρκετό για να δείξουμε ότι ο είναι ο μικρότερος αριθμός Fibonacci ο οποίος λήγει σε τέσσερα μηδενικά αρκεί προηγουμένως να δείξουμε ότι ο είναι ο μικρότερος που είναι πολλαπλάσιο του (απλές πράξεις) και ο είναι ο μικρότερος που είναι πολλαπλάσιο του . Για το τελευταίο τα πιο πάνω κριτήρια δεν επαρκούν και είτε πρέπει να κάνουμε τις πράξεις, είτε να βρούμε κάποιο επιπλέον κριτήριο αν θέλουμε να τις αποφύγουμε.

[Mihalis_Lambrou]

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

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

Ας δούμε ένα παράδειγμα:

κάποιος ακέραιος αριθμός.

α) O μικρότερος πολλαπλάσιος του αριθμός είναι ο και του είναι ο , οπότε ο μικρότερος είναι ο
....
Πηγή: Το θέμα είναι από το του κ. Ρωμανίδη. Το έθεσε ο Γιώργος Ριζόπουλος και το έλυσε ο Θανάσης Παπαδημητρίου (papadim), συνάδελφοι Πολιτικοί μηχανικοί ΕΜΠ.

Σύμφωνα με τον συλλογισμό, το γινόμενο των μικρότερων πολλαπλασίων των οδηγεί μέσω του σε μικρότερο πολλαπλάσιο του . Χμμμμμ, και το στο που πήγε; Αν έχει και αυτό δεκάρι μέσα του, τότε χάσαμε το ελάχιστο μια και βρεθήκαμε στο . Με άλλα λόγια η όποια απόδειξη πρέπει να λάβει υπόψη και το (στο συγκεκριμένο θέμα, η απόδειξη φτιάχνει).

Όπως και να είναι, ο συλλογισμός των λυτών στο eisatopon είναι αξιοπρόσεκτος αν και ελλειπής. Εύγε στους λύτες μια και η απόδειξη βελτιώνεται σε πλήρως ορθή.

Μ.

[ealexiou]

Το κριτήριο ισχύει μόνο όταν πρώτοι μεταξύ τους.

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

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

Δεν νομίζω ότι υπάρχει πρόβλημα γιατί αφού ξέρουμε ότι ο είναι ο μικρότερος αριθμός Φιμπονάτσι και με βάση την ιδιότητα ότι αν ο αριθμός διαιρεί τον αριθμό τότε και ο αριθμός διαιρεί τον αριθμό και το αντίστροφο (Δεν έχω απόδειξη, αλλά μην ξεχνάμε ότι είμαστε στον φάκελλο Διασκεδαστικά Μαθηματικά, και γιαυτό το έβαλα εδώ)
Οπότε για τον π.χ αριθμό έχουμε , άρα επειδή ο δεν διαιρεί τον και ο δεν διαιρεί τον , δηλαδή ο δεν έχει όχι μηδενικά αλλά ούτε ένα μηδενικό στο τέλος και πράγματι επιβεβαιώνεται από το λογισμικό.

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

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

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

[Mihalis_Lambrou]

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

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

Έστω ότι θέλουμε να βρούμε τον μικρότερο αριθμό Fibonacci που διαιρείται από το .

Ο μικρότερος που διαιρείται με το είναι ο και ο μικρότερος που διαιρείται με τον είναι ο . Τότε ο παραπάνω συλλογισμός δίνει ως το μικρότερο πολλαπλάσιο του τον ( βλέπε εδώ)

Να όμως που ο (βλέπε την ίδια παραπομπή) είναι μικρότερος.

Μ.

[gbdalako]

Μία μικρή διόρθωση για την πηγή του προβλήματος! Το πρόβλημα είναι από την ΙΧ Μαθηματική Ολυμπιάδα Μόσχας.

ΥΓ: Το πιο ενδιαφέρον είναι ότι στο "Εισάτοπον" το πρόβλημα (ή πιο σωστά η λύση του) είναι λάθος Η παραπάνω λύση θα ήταν σωστή για την συγκεκριμένη εκφώνηση εκεί.