Φίλοι αριθμοί

#1

Έστω

το σύνολο όλων των διψήφιων ακεραίων που δεν περιέχουν το ψηφίο 0. Δύο αριθμοί του

λέγονται φίλοι αν τα μεγαλύτερα ψηφία τους ταυτίζονται και η διαφορά των μικρότερων ψηφίων τους είναι ίση με 1. Για παράδειγμα, οι αριθμοί 68 και 85 είναι φίλοι, οι αριθμοί 78 και 88 είναι φίλοι , αλλά οι αριθμοί 58 και 75 δεν είναι φίλοι.

Να προσδιορισθεί το πλήθος των στοιχείων του μεγαλύτερου δυνατού υποσυνόλου του

που δεν περιέχει αριθμούς που να είναι φίλοι.

Φιλικά,

Αχιλλέας

synthels · #2

-- λάθος λύση --

#3

synthels έγραψε: ↑
Κυρ Ιουν 12, 2022 1:17 pm
Ισχυρισμός Κάθε δυάδα φίλων είναι της μορφής $(\overline{ab}, \overline{(b \pm 1)a})$ .

Χάνω κάτι;

α) Η δυάδα $73,\, 74$ είναι φίλοι αλλά δεν είναι της παραπάνω μορφής.

Αλλά και από την ανάποδη,

β) Η δυάδα $38, \, 73$ είναι της παραπάνω μορφής αλλά δεν είναι φίλοι.

synthels · #4

Ναι οκ, θα προσπαθήσω να το φτιάξω..

synthels · #5

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

Ισχυρισμός #1 Κάθε φιλική δυάδα είναι της μορφής $(\overline{ab}, \overline{a(b \pm 1)})$ , $(\overline{ab}, \overline{(b \pm 1)a})$ , $(\overline{ab}, \overline{b(a \pm 1)})$ ή $(\overline{ab}, \overline{(a \pm 1)b})$ .
Απόδειξη Έστω (n, k)

μια δυάδα φίλων. Ας είναι $n = \overline{ab}$ και $k = \overline{cd}$ . Διακρίνουμε τις εξής περιπτώσεις:

και $\implies c = a$ και $|b - d| = 1 \implies k = \overline{a(b \pm 1)}$ .
και $\implies d = a$ και $|b - c| = 1 \implies k = \overline{(b \pm 1)a}$ .
και $\implies c = b$ και $|a - d| = 1 \implies k = \overline{b(a \pm 1)}$ .
και $\implies d = b$ και $|a - c| = 1 \implies k = \overline{(a \pm 1)b}$ .

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

, με κάθε διάταξη που παίρνουν τα a, b

, ώστε να λάβουμε κάποιους περιορισμούς για τα ζευγάρια.

Μαζί με το γεγονός πως αριθμοί της μορφής $\overline{xx}$ δεν μπορούν να έχουν φίλους, μπορούμε να φτάσουμε στο αποτέλεσμα το οποίο θα είναι της μορφής |S| - |F| + 1

, όπου

το σύνολο των φίλων στο

.

#6

synthels έγραψε: ↑
Κυρ Ιουν 12, 2022 5:32 pm
... που βαρίεμαι να το κάνω...

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

... μπορούμε να φτάσουμε στο αποτέλεσμα...

Νομίζω ότι χάσαμε την ουσία. H προτεινόμενη λύση ΟΥΣΙΑΣΤΙΚΑ λέει "για να βρω πόσοι είναι οι φίλοι αριθμοί, πρέπει να τους μετρήσω". Μα το ερώτημα είναι πώς θα τους μετρήσω.

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

Έστω ότι το μεγαλύτερο ψηφίο δύο φίλων αριθμών είναι το

και ότι το ζεύγος αυτό των φίλων αριθμών έχει την μορφή $(\overline {ab},\, \overline {ac}) \, (*)$ , εννοείται για κατάλληλα b,c

. Τότε αμέσως αμέσως και τα ζεύγη $(\overline {ac},\, \overline {ab}) \, (*)$ καιθώς και τα $(\overline {ba},\, \overline {ac})$ και τα $(\overline {ba},\, \overline {ca})$ και τα $(\overline {ba},\, \overline {ac})$ και τα $(\overline {ab},\, \overline {ca})$ και λοιπά ΕΙΝΑΙ φίλοι. Αντίστροφα, κάθε ζεύγος φίλων (εκτός από την περίπτωση b=0

ή

) προκύπτει από την περίπτωση (*)

με κάποια αναδιάταξη των ψηφίων.

Συνοψίζοντας, αρκεί να βρούμε ΜΟΝΟ τα ζεύγη φίλων της μορφής (*)

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

γιατί για τα υπόλοιπα βγάζουμε άκρη. Επίσης βγάζουμε άκρη για την περίπτωση b=0

ή

.

Περιμένω τον synthels να ξεβαρεθεί και να γράψει πλήρη (οικονομική) λύση.

Φίλοι αριθμοί

Φίλοι αριθμοί

Re: Φίλοι αριθμοί

Re: Φίλοι αριθμοί

Re: Φίλοι αριθμοί

Re: Φίλοι αριθμοί

Re: Φίλοι αριθμοί

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