Ψηφία από Εσθονία

Συντονιστές: cretanman, silouan, rek2

DrStrange
Δημοσιεύσεις: 25
Εγγραφή: Τετ Μάιος 08, 2019 8:30 pm

Ψηφία από Εσθονία

#1

Μη αναγνωσμένη δημοσίευση από DrStrange » Δευ Οκτ 05, 2020 8:46 pm

Καλούμε έναν θετικό ακέραιο n των οποίων όλα τα ψηφία είναι διαφορετικά "bronze", αν ο n είτε είναι μονοψήφιος είτε υπάρχει διαιρέτης του που προκύπτει σβήνοντας ένα ψηφίο του n και είναι "bronze". Να βρεθεί ο μεγαλύτερος "bronze" θετικός ακέραιος. (υποθέτουμε ότι αριθμοί δεν ξεκινούν με 0)



Λέξεις Κλειδιά:
Άβαταρ μέλους
llenny
Δημοσιεύσεις: 47
Εγγραφή: Τρί Απρ 23, 2019 11:10 pm
Τοποθεσία: Σητεία Κρήτης

Re: Ψηφία από Εσθονία

#2

Μη αναγνωσμένη δημοσίευση από llenny » Παρ Δεκ 18, 2020 2:35 pm

Μπορεί κάποιος να δώσει μία υπόδειξη για το παραπάνω θέμα;


giannisd
Δημοσιεύσεις: 21
Εγγραφή: Τετ Δεκ 05, 2018 1:02 am
Τοποθεσία: Θεσσαλονίκη

Re: Ψηφία από Εσθονία

#3

Μη αναγνωσμένη δημοσίευση από giannisd » Τρί Δεκ 29, 2020 7:54 pm

Μήπως είναι η απάντηση 146250;
Αν γνωρίζει κάποιος, ας με επιβεβαιώσει και θα προσπαθήσω να βάλω λύση το συντομότερο.


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 13338
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Ψηφία από Εσθονία

#4

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τρί Δεκ 29, 2020 11:21 pm

giannisd έγραψε:
Τρί Δεκ 29, 2020 7:54 pm
Μήπως είναι η απάντηση 146250;
Αν γνωρίζει κάποιος, ας με επιβεβαιώσει και θα προσπαθήσω να βάλω λύση το συντομότερο.
Ναι, η απάντηση είναι σωστή.

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

Το πρώτο βήμα της λύσης είναι
να δείξεις ότι το τελευταίο ψηφίο του μέγιστου πρέπει να είναι 10
.

Μετά πρέπει να ασχοληθείς με
τα δύο πρώτα ψηφία.


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 13338
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Ψηφία από Εσθονία

#5

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τετ Δεκ 30, 2020 9:08 am

Mihalis_Lambrou έγραψε:
Τρί Δεκ 29, 2020 11:21 pm
Από σύμπτωση ξέρω από παλαιότερα την άσκηση και την λύση της. Μας την είχε βάλει πριν από ενάμιση χρόνο ο Εσθονός συνάδελφος του Καγκουρό σε συνάντησή μας, για να μας ...παιδέψει (υπάρχουν και διαστροφές στον κόσμο). Μία ομάδα φίλων την λύσαμε από κοινού συνεργαζόμενοι στα διαλείμματα της συνάντησης. Δύσκολη άσκηση. Αν θυμάμαι καλά, ο Εσθονός "δράστης" μας είπε ότι ήταν θέμα από την τελική φάση της επιλογής της Εθνικής τους ομάδας για την ΙΜΟ ένα ή δύο χρόνια νωρίτερα.
Έγραψα μήνυμα στον εν λόγω Εσθονό, ο οποίος μου απάντησε επιβεβαιώνοντας τα περί της πηγής της άσκησης. Μου έστειλε και την σχετική ιστοσελίδα όπου υπάρχει. Θα την αναρτήσω όταν τελειώσει η εδώ συζήτηση.


Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1655
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Re: Ψηφία από Εσθονία

#6

Μη αναγνωσμένη δημοσίευση από Ορέστης Λιγνός » Τετ Δεκ 30, 2020 6:50 pm

DrStrange έγραψε:
Δευ Οκτ 05, 2020 8:46 pm
Καλούμε έναν θετικό ακέραιο n των οποίων όλα τα ψηφία είναι διαφορετικά "bronze", αν ο n είτε είναι μονοψήφιος είτε υπάρχει διαιρέτης του που προκύπτει σβήνοντας ένα ψηφίο του n και είναι "bronze". Να βρεθεί ο μεγαλύτερος "bronze" θετικός ακέραιος. (υποθέτουμε ότι αριθμοί δεν ξεκινούν με 0)
Χρόνια Πολλά!

Για ευκολία, θα ονομάζω τους αριθμούς καλούς αντί για bronze.
Αρχίζουμε με δύο Ισχυρισμούς.

Ισχυρισμός 1: Αν ο αριθμός 10k είναι καλός, τότε και ο k είναι καλός.
Απόδειξη: Προχωράμε με επαγωγή στο πλήθος των ψηφίων του k. Αν ο k είναι μονοψήφιος τότε είναι προφανές. Έστω πως ο k έχει t ψηφία και το ζητούμενο ισχύει για κάθε αριθμό με t-1 ψηφία.

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

Αν τώρα σβήνουμε κάποιο άλλο ψηφίο, τότε προκύπτει ένας καλός αριθμός s με t-1 ψηφία που λήγει σε 0, οπότε από την επαγωγική υπόθεση ο s/10 είναι καλός. Όμως, ο s/10 διαιρεί τον n, καθώς ο s διαιρεί τον 10n. Επομένως ο n έχει έναν καλό διαιρέτη που προκύπτει με σβήσιμο ενός του ψηφίου, άρα και ο n είναι καλός \blacksquare

Ισχυρισμός 2: Αν ένας καλός αριθμός έχει πάνω από 3 ψηφία και δεν διαιρείται με 10, τότε δεν γίνεται να προκύψει καλός διαιρέτης του σβήνοντας κάποιο ψηφίο εκτός των δύο πρώτων.
Απόδειξη: Έστω A=\overline{a_1a_2 \ldots a_m} ο καλός αριθμός και έστω ότι σβήνουμε το ψηφίο a_i με i \geq 3, οπότε προκύπτει ο αριθμός B.

Έστω P=\overline{a_1a_2 \ldots a_{i-1}} και Q=\overline{a_{i+1} \ldots a_m}. Τότε, A=10^{m-i+1}P+10^{m-i}a_i+Q και B=10^{m-i}P+Q.

Παρατηρούμε ότι, A-9B=10^{m-i}P+10^{m-i}a-8Q. Είναι P=\overline{a_1a_2 \ldots a_{i-1}}>10^{i-2} και Q=\overline{a_{i+1} \ldots a_m}<10^{m-i}, οπότε A-9B \geq 10^{m-i} \cdot 10^{i-2}-8 \cdot 10^{m-i}=10^{m-2}-8 \cdot 10^{m-i}=10^{m-i}(10^{i-2}-8)>0, όπου στο τέλος χρησιμοποιήθηκε το γεγονός ότι i \geq 3.

Επίσης, 11B-A=10^{m-i}P+10Q-10^{m-i}a_i>0, καθώς ο P είναι σίγουρα διψήφιος ενώ a_i \leq 9.

Συνεπώς 9B<A<11B και B \mid A, άρα A=10B, που είναι άτοπο καθώς ο A από την υπόθεση δεν διαιρείται με 10 \blacksquare

Πίσω στο πρόβλημα.

Ισχυριζόμαστε ότι ο μοναδικός πενταψήφιος καλός αριθμός που δεν λήγει σε 0 είναι ο 14625.

Έστω \overline{abcde} ο πενταψήφιος καλός αριθμός. Διακρίνουμε δύο περιπτώσεις σχετικά με το ποιο ψηφίο σβήνουμε.

\bullet Σβήνουμε το a. Τότε \overline{bcde} \mid \overline{abcde} \Rightarrow \overline{bcde} \mid 10^4a.

Αφού e \neq 0, ο \overline{bcde} δεν διαιρείται και από το 2 και από το 5.

Αν διαιρείται μόνο από το 2, τότε πρέπει \overline{bcde} \mid 16a \Rightarrow 1000 \leq \overline{bcde} \leq 16a \leq 144, άτοπο.
Άρα πρέπει να διαιρείται μόνο από το 5, δηλαδή \overline{bcde} \mid 625a.

Ο \overline{bcde} είναι πολλαπλάσιο του 5 και περιττός, οπότε λήγει σε 5. Εξετάζοντας τώρα όλες τις περιπτώσεις a \in \{1,2, \ldots, 9 \}, προκύπτουν οι αριθμοί 31875, 53125, 61875, 74375, 95625,91875, 91125, εκ των οποίων ο δεύτερος και ο τέταρτος απορρίπτονται λόγω επανάληψης ψηφίου, ενώ για τους υπόλοιπους μπορούμε εύκολα να ελέγξουμε ότι δεν είναι καλοί.

\bullet Σβήνουμε το b. Οπότε πρέπει 1000a+\overline{cde} \mid \overline{abcde}=10^4a+10^3b+\overline{cde} \Rightarrow 1000a+\overline{cde} \mid 1000(9a+b).

Ο αριθμός \overline{cde}, άρα και ο 1000a+\overline{cde} δεν διαιρείται με το 10. Αν διαιρείται λοιπόν με το 2, τότε δεν διαιρείται με το 5 και όπως πριν έχουμε εύκολα άτοπο. Άρα διαιρείται μόνο με το 5, οπότε 1000a+\overline{cde} \mid 125(9a+b) \Rightarrow 1000a+\overline{cde} \mid 125(a+b)-\overline{cde}.

Διακρίνουμε τρεις περιπτώσεις.

- \overline{cde}>125(a+b). Τότε \overline{cde}-125(a+b)>1000a+\overline{cde}, προφανώς άτοπο.
- \overline{cde}=125(a+b). Τότε ο a+b είναι σίγουρα περιττός, και επίσης 125(a+b)=\overline{cde} \leq 987 \Rightarrow a+b \leq 7.

Αν a+b=7, τότε \overline{cde}=875, οπότε διακρίνοντας μερικές εύκολες περιπτώσεις απορρίπτονται όλοι οι πιθανοί αριθμοί.
Αν a+b=5 τότε \overline{cde}=625, οπότε πάλι διακρίνοντας περιπτώσεις προκύπτει ο 14625.
Αν a+b=3 τότε \overline{cde}=375 οπότε απορρίπτονται οι πιθανοί αριθμοί ξανά.

- \overline{cde}<125(a+b). Τότε, έχουμε ότι 125(a+b)-\overline{cde} \geq 1000a+\overline{cde} \Rightarrow 125(a+b) \geq 1000a+2\overline{cde}.

Επομένως, 1000a \leq 125(9+8)-2 \cdot 123<2000 άρα a=1. Οπότε είναι 125(b+1) \geq 1000+2\overline{cde} \Rightarrow 125b \geq 775+2 \overline{cde} \geq 775+2 \cdot 234=1243 \Rightarrow b \geq 10, άτοπο (αφού χρησιμοποιήσαμε το 1, πρέπει τα άλλα ψηφία να είναι μεγαλύτερα ή ίσα του 2, οπότε \overline{cde} \geq 234).

Επομένως, η απόδειξη ολοκληρώθηκε.

Συνεχίζουμε την απόδειξη μελετώντας τους εξαψήφιους καλούς αριθμούς.

Αν ένας εξαψήφιος καλός αριθμός x λήγει σε 0 τότε από τον Ισχυρισμό 1 ο x/10 είναι επίσης καλός. Καθώς είναι και πενταψήφιος αριθμός και δεν λήγει σε 0 (οι καλοί αριθμοί έχουν ανά δύο τα ψηφία τους διαφορετικά), από το πιο πάνω έχουμε ότι x=146250. Αν πάλι ο x δεν λήγει σε 0, τότε έστω x=\overline{abcde  f} και μπορούμε από τον Ισχυρισμό 2 να σβήσουμε είτε το a είτε το b. Σε κάθε περίπτωση, ο πενταψήφιος καλός αριθμός που θα προκύψει δεν λήγει σε 0, άρα είναι ο 14625. Διακρίνουμε τώρα δύο περιπτώσεις:

\bullet Αν σβήσουμε τον a, τότε πρέπει 14625 \mid \overline{a14625} \Rightarrow 14625 \mid 10000a \Rightarrow 117 \mid 80a, άτοπο.
\bullet Αν σβήσουμε τον b, τότε πρέπει 14625 \mid \overline{1a4625} \Rightarrow 14625 \mid 10^5+10^4(a-1) \Rightarrow 117 \mid a+9, άτοπο.

Σε κάθε περίπτωση καταλήγουμε σε άτοπο, άρα ο μόνος καλός εξαψήφιος είναι ο 146250.

Αν πάμε στους εφταψήφιους τώρα, διακρίνουμε δύο περιπτώσεις:

\bullet Αν ο εφταψήφιος y τελειώνει σε μηδέν, τότε ο y/10 είναι καλός άρα από τα προηγούμενα πρέπει y/10=146250 οπότε y=1462500 που είναι άτοπο καθώς οι καλοί αριθμοί έχουν τα ψηφία τους διαφορετικά.
\bullet Αν δεν τελειώνει σε μηδέν τότε σβήνοντας ένα ψηφίο του προκύπτει ένας εξαψήφιος καλός αριθμός που δεν λήγει σε μηδέν, κάτι το οποίο δεν γίνεται να συμβαίνει όπως δείξαμε πριν.

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

Συνεπώς, ο μεγαλύτερος καλός αριθμός είναι πράγματι ο 146250.


Κερδίζουμε ό,τι τολμούμε!
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 13338
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Ψηφία από Εσθονία

#7

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Δευ Ιαν 04, 2021 4:48 pm

giannisd έγραψε:
Τρί Δεκ 29, 2020 7:54 pm
Μήπως είναι η απάντηση 146250;
Αν γνωρίζει κάποιος, ας με επιβεβαιώσει και θα προσπαθήσω να βάλω λύση το συντομότερο.
Γιάννη, έχεις την εν λόγω λύση;

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


giannisd
Δημοσιεύσεις: 21
Εγγραφή: Τετ Δεκ 05, 2018 1:02 am
Τοποθεσία: Θεσσαλονίκη

Re: Ψηφία από Εσθονία

#8

Μη αναγνωσμένη δημοσίευση από giannisd » Τρί Ιαν 05, 2021 5:35 pm

Θα επιρρίψω την καθυστέρησή μου στα ζόρια της Γ Λυκείου. :D :D
Είναι μάλλον πανομοιότυπη με αυτήν του Ορέστη και απολογούμαι για την υπόσχεση που δεν τήρησα.


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 13338
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Ψηφία από Εσθονία

#9

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τρί Ιαν 05, 2021 7:01 pm

giannisd έγραψε:
Τρί Ιαν 05, 2021 5:35 pm
Θα επιρρίψω την καθυστέρησή μου στα ζόρια της Γ Λυκείου. :D :D
Είναι μάλλον πανομοιότυπη με αυτήν του Ορέστη και απολογούμαι για την υπόσχεση που δεν τήρησα.
Ιερός ο σκοπός και σου εύχομαι ολόψυχα καλό διάβασμα και καλή επιτυχία.

Η παραπομπή που υποσχέθηκα είναι στην σελίδα 32, άσκηση S5 εδώ


Απάντηση

Επιστροφή σε “Θεωρία Αριθμών - Επίπεδο Αρχιμήδη (Seniors)”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης