Σύνολο με ιδιότητα

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #1

Θεωρούμε θετικό ακέραιο

. Να βρεθούν όλα τα υποσύνολα των θετικών ακεραίω $\mathbb{S}$ με την εξής ιδιότητα:
Κάθε θετικός ακέραιος

μπορεί να γραφεί κατά μοναδικό τρόπο ως άθροισμα της μορφής
$\displaystyle m=\sum_{x\in \mathbb{S}} x\cdot c_x$ με τα $0\leq c_x<n$ να είναι ακέραιοι.

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

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ έγραψε: ↑
Δευ Οκτ 09, 2023 7:34 pm
Θεωρούμε θετικό ακέραιο . Να βρεθούν όλα τα υποσύνολα των θετικών ακεραίων $\mathbb{S}$ με την εξής ιδιότητα:
Κάθε θετικός ακέραιος μπορεί να γραφεί κατά μοναδικό τρόπο ως άθροισμα της μορφής
$\displaystyle m=\sum_{x\in \mathbb{S}} x\cdot c_x$ με τα $0\leq c_x<n$ να είναι ακέραιοι.

Απάντηση: Αν n=1

, τότε δεν υπάρχει κανένα τέτοιο σύνολο

. Αν $n \geq 2,$ τότε $S=\{n^0,n^1,n^2, \ldots \}$ .

Πράγματι, είναι άμεσο ότι για n=1

τέτοιο σύνολο δεν υπάρχει, ενώ για $n \geq 2$ γνωρίζουμε ότι κάθε $m \geq 1$ έχει μοναδική αναπαράσταση σε βάση

, άρα προκύπτει ότι το πιο πάνω σύνολο όντως ικανοποιεί. Μένει να αποδείξουμε ότι είναι και το μοναδικό. Εργαζόμαστε επαγωγικά. Έστω:

P(k):

για κάθε $k \geq 1$ ισχύει ότι αν $1 \leq x \leq k$ τότε $x \in S \Longleftrightarrow x=n^t$ με $t \geq 0$ .

Για k=1

η

ισχύει, καθώς αν $1 \notin S$ τότε το

δεν γράφεται ως γραμμικός συνδυασμός των στοιχείων του

.
Αν ισχύει η P(k)

για κάθε $k \leq s$ , τότε αν το s+1

είναι δύναμη του

, τότε το

δεν γράφεται ως γραμμικός συνδυασμός μικρότερων στοιχείων του

(λόγω μοναδικότητας της αναπαράστασης σε βάση

), άρα αναγκαστικά $s+1 \in S$ . Αν πάλι δεν είναι δύναμη του

, τέτοια αναπαράσταση υπάρχει, και αφού είναι μοναδική πρέπει $s+1 \notin S$ , όπως θέλαμε.

Χρησιμοποιώντας τώρα την ισχύ της P(k),

προκύπτει ο ζητούμενος χαρακτηρισμός του συνόλου

.

Σύνολο με ιδιότητα

Σύνολο με ιδιότητα

Re: Σύνολο με ιδιότητα

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