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

DrStrange · #1

Καλούμε έναν θετικό ακέραιο

των οποίων όλα τα ψηφία είναι διαφορετικά "bronze", αν ο

είτε είναι μονοψήφιος είτε υπάρχει διαιρέτης του που προκύπτει σβήνοντας ένα ψηφίο του

και είναι "bronze". Να βρεθεί ο μεγαλύτερος "bronze" θετικός ακέραιος. (υποθέτουμε ότι αριθμοί δεν ξεκινούν με

)

llenny · #2

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

giannisd · #3

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

#4

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

Ναι, η απάντηση είναι σωστή.

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

Το πρώτο βήμα της λύσης είναι

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

.

Μετά πρέπει να ασχοληθείς με

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

#5

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

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

Ορέστης Λιγνός · #6

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

Χρόνια Πολλά!

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

Ισχυρισμός 1: Αν ο αριθμός 10k

είναι καλός, τότε και ο

είναι καλός.
Απόδειξη: Προχωράμε με επαγωγή στο πλήθος των ψηφίων του

. Αν ο

είναι μονοψήφιος τότε είναι προφανές. Έστω πως ο

έχει

ψηφία και το ζητούμενο ισχύει για κάθε αριθμό με t-1

ψηφία.

Αν ο καλός διαιρέτης του 10k

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

είναι καλός.

Αν τώρα σβήνουμε κάποιο άλλο ψηφίο, τότε προκύπτει ένας καλός αριθμός

με

ψηφία που λήγει σε

, οπότε από την επαγωγική υπόθεση ο s/10

είναι καλός. Όμως, ο s/10

διαιρεί τον

, καθώς ο

διαιρεί τον 10n

. Επομένως ο

έχει έναν καλό διαιρέτη που προκύπτει με σβήσιμο ενός του ψηφίου, άρα και ο

είναι καλός $\blacksquare$

Ισχυρισμός 2: Αν ένας καλός αριθμός έχει πάνω από

ψηφία και δεν διαιρείται με

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

με $i \geq 3$ , οπότε προκύπτει ο αριθμός

.

Έστω $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$ , καθώς ο

είναι σίγουρα διψήφιος ενώ $a_i \leq 9$ .

Συνεπώς 9B<A<11B

και $B \mid A$ , άρα A=10B

, που είναι άτοπο καθώς ο

από την υπόθεση δεν διαιρείται με

$\blacksquare$

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

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

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

$\bullet$ Σβήνουμε το

. Τότε $\overline{bcde} \mid \overline{abcde} \Rightarrow \overline{bcde} \mid 10^4a$ .

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

και από το

.

Αν διαιρείται μόνο από το

, τότε πρέπει $\overline{bcde} \mid 16a \Rightarrow 1000 \leq \overline{bcde} \leq 16a \leq 144$ , άτοπο.
Άρα πρέπει να διαιρείται μόνο από το

, δηλαδή $\overline{bcde} \mid 625a$ .

Ο $\overline{bcde}$ είναι πολλαπλάσιο του

και περιττός, οπότε λήγει σε

. Εξετάζοντας τώρα όλες τις περιπτώσεις $a \in \{1,2, \ldots, 9 \}$ , προκύπτουν οι αριθμοί 31875, 53125, 61875, 74375, 95625,91875, 91125

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

$\bullet$ Σβήνουμε το

. Οπότε πρέπει $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}$ δεν διαιρείται με το

. Αν διαιρείται λοιπόν με το

, τότε δεν διαιρείται με το

και όπως πριν έχουμε εύκολα άτοπο. Άρα διαιρείται μόνο με το

, οπότε $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

.
Αν

τότε $\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$ , άτοπο (αφού χρησιμοποιήσαμε το

, πρέπει τα άλλα ψηφία να είναι μεγαλύτερα ή ίσα του

, οπότε $\overline{cde} \geq 234$ ).

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

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

Αν ένας εξαψήφιος καλός αριθμός

λήγει σε

τότε από τον Ισχυρισμό 1 ο x/10

είναι επίσης καλός. Καθώς είναι και πενταψήφιος αριθμός και δεν λήγει σε

(οι καλοί αριθμοί έχουν ανά δύο τα ψηφία τους διαφορετικά), από το πιο πάνω έχουμε ότι x=146250

. Αν πάλι ο

δεν λήγει σε

, τότε έστω $x=\overline{abcde f}$ και μπορούμε από τον Ισχυρισμό 2 να σβήσουμε είτε το

είτε το

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

, άρα είναι ο 14625

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

$\bullet$ Αν σβήσουμε τον

, τότε πρέπει $14625 \mid \overline{a14625} \Rightarrow 14625 \mid 10000a \Rightarrow 117 \mid 80a$ , άτοπο.
$\bullet$ Αν σβήσουμε τον

, τότε πρέπει $14625 \mid \overline{1a4625} \Rightarrow 14625 \mid 10^5+10^4(a-1) \Rightarrow 117 \mid a+9$ , άτοπο.

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

.

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

$\bullet$ Αν ο εφταψήφιος

τελειώνει σε μηδέν, τότε ο y/10

είναι καλός άρα από τα προηγούμενα πρέπει y/10=146250

οπότε

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

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

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

.

#7

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

Γιάννη, έχεις την εν λόγω λύση;

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

giannisd · #8

Θα επιρρίψω την καθυστέρησή μου στα ζόρια της Γ Λυκείου.

Είναι μάλλον πανομοιότυπη με αυτήν του Ορέστη και απολογούμαι για την υπόσχεση που δεν τήρησα.

#9

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

Ιερός ο σκοπός και σου εύχομαι ολόψυχα καλό διάβασμα και καλή επιτυχία.

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

, άσκηση

εδώ

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

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

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

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

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

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

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

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

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

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

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