Προβλήματα Μαθηματικών

Δεκέμβριος 4, 2009

Γραμμικοί συνδυασμοί με φυσικούς ως συντελεστές ΙΙ

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 2:03 μμ

Είδαμε στο πρόβλημα «Γραμμικοί συνδυασμοί με φυσικούς αριθμούς ως συντελεστές» ότι αν a,b είναι σχετικά πρώτοι τότε υπάρχει πεπερασμένο πλήθος φυσικών αριθμών n που δεν μπορούν να γραφούν ως n=xa+yb με x,y φυσικούς.

Μπορείτε να υπολογίσετε πόσοι είναι αυτοί οι αριθμοί;

Advertisements

3 Σχόλια »

  1. Υπόδειξη:

    Δώστε μια διαφορετική λύση στο πρόβλημα «Γραμμικοί συνδυασμοί με φυσικούς ως συντελεστές», δείχνοντας ότι κάθε n>ab μπορεί να γραφεί ως n=xa+yb με x,y φυσικούς. Αρκεί επομένως να μετρήσουμε πόσοι φυσικοί αριθμοί \le ab δεν μπορούν να γραφούν έτσι, που είναι πιο εύκολο.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Φεβρουαρίου 12, 2010 @ 8:12 μμ

  2. Αφού οι a,b είναι σχετικά πρώτοι έπεται \{b,2b,\ldots,ab\}=\{1,2,\ldots,a\}=\mathbb{Z}_a (Το \{b,2b,\ldots,ab\} έχει a διαφορετικά ανά δύο στοιχεία αφού αν ib=jb\Rightarrow(i-j)b=0\Rightarrow i-j=0\;\;\;modaφυσικά).
    Αν τώρα n \in \mathbb{N}, \;n>ab τότε n \equiv kb moda ,\;k\in\{1,\ldots,a\} \Rightarrow n=kb+la και οι k,l είναι φυσικοί.
    Τώρα γενικά αν n \in \mathbb{N}\;\;n \equiv kb moda ,\;k \in \{1,\ldots,a\} άρα ο n γράφεται σαν n=ax+by, \;x,y \in \mathbb{N} \Leftrightarrow n>kb
    Άρα το πλήθος των φυσικών μικρότερων ή ίσων του ab που γράφονται σαν n=ax+by,\;x,y \in \mathbb{N} είναι \lfloor b \frac{a-1}{a} \rfloor+\lfloor b \frac{a-2}{a} \rfloor +\ldots+\lfloor \frac{b}{a} \rfloor όπου \lfloor r \rfloorτο ακέραιο μέρος. Οπότε το πλήθος των φυσικών που δεν γράφονται σαν n=ax+by, x,y \in \mathbb{N} είναι ab-( \lfloor b \frac{a-1}{a} \rfloor+\lfloor b \frac{a-2}{a} \rfloor +\ldots+\lfloor \frac{b}{a} \rfloor )
    Αν είναι σωστά αυτά που γράφω πρέπει να ισχύει \lfloor b \frac{a-1}{a} \rfloor+\lfloor b \frac{a-2}{a} \rfloor +\ldots+\lfloor \frac{b}{a} \rfloor = \lfloor a \frac{b-1}{b} \rfloor+\lfloor a\frac{b-2}{b} \rfloor +\ldots+\lfloor \frac{a}{b} \rfloor όταν οι a,b είναι σχετικά πρώτοι.

    Μου αρέσει!

    Σχόλιο από pamp0s — Απρίλιος 23, 2010 @ 11:10 μμ

  3. Αυτά που γράφεις είναι σωστά, και το άθροισμα με τα ακέραια μέρη που εμφανίζεται
    το έχουμε ξανασυναντήσει στο πρόβλημα «Μια ταυτότητα«. Είναι ίσο με \frac{(a-1)(b-1)}{2},
    οπότε η απάντηση είναι \frac{ab+a+b-1}{2}.

    Με παρόμοιο τρόπο μπορεί κανείς να υπολογίσει το πλήθος των φυσικών που δεν γράφονται ως γραμμικοί συνδυασμοί των a,b με συντελεστές μη αρνητικούς ακεραίους, το οποίο
    είναι \frac{(a-1)(b-1)}{2}.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Απρίλιος 24, 2010 @ 6:40 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: