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

Μαΐου 3, 2008

Ακεραιότιμα πολυώνυμα

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 11:59 πμ

Ένα πολυώνυμο με πραγματικούς συντελεστές P(x)=a_0+a_1 x + \cdots + a_n x^n παίρνει ακέραιες τιμές για κάθε ακέραιο x (ονομάζουμε τέτοια πολυώνυμα ακεραιότιμα).

Δείξτε ότι υπάρχουν ακέραιοι b_0, \ldots, b_n τέτοιοι ώστε

\displaystyle P(x) = b_0 + b_1 {x \choose 1} + b_2 {x \choose 2} + \cdots + b_n {x \choose n},

όπου το πολυώνυμο {x \choose k}, k \ge 0, ορίζεται ως

\displaystyle {x \choose k} = \frac{x(x-1)(x-2)\cdots(x-k+1)}{1\cdot 2 \cdot 3 \cdots k}

και είναι ακεραιότιμο (γιατί;).

Advertisements

9 Σχόλια »

  1. Το ότι τα πολυώνυμα \displaystyle {x \choose k} είναι ακεραιότιμα φαίνεται διότι για κάθε ακέραιο τέτοιο ώστε ο αριθμητής να μη μηδενίζεται, ο αριθμητής περιέχει έναν αντιπρόσωπο από όλες τις κλάσεις \mod{k} ο οποίος επομένως διαιρείται από τον αντίστοιχο αντιπρόσωπο στον παρονομαστή. Επομένως το πολυώνυμο είναι ακεραιότιμο.

    Έπειτα, επειδή τα διάφορα αυτά πολυώνυμα έχουν διαφορετικούς βαθμούς που κυμαίνονται από 1 μέχρι n, έπεται ότι είναι γραμμικά ανεξάρτητα πάνω από το {\mathbb R}(καντε evaluate σε έναν υπερβατικό). Επομένως μαζί με το σταθερό πολυώνυμο παράγουν όλο το χώρο των πολυωνύμων βαθμού μέχρι και ν. Άρα το ακεραιότιμο πολυώνυμο P μπορεί να γραφεί στη δεύτερη μορφή που δίνεται στη διατύπωση, ενώ μένει να δειχθεί ότι τα b_i είναι ακέραια. Όμως αυτό πλέον είναι μια τετριμμένη επαγωγή, διότι κάνοντας evaluate στο k ακριβώς οι k πρώτοι όροι δε μηδενίζονται, οπότε διαδοχικά μπορείς να συνεπάγεις ότι το b_1, b_1+b_2 είναι ακέραια, άρα b_2 ακέραιο και ούτω καθεξής, από όπου έπεται άμεσα το ζητούμενο.

    Μου αρέσει!

    Σχόλιο από ikonst — Μαΐου 4, 2008 @ 2:06 μμ

  2. ikonst:

    Το δεύτερο κομμάτι της απόδειξής σου είναι σωστό.

    Όμως όχι το πρώτο. Δες για παράδειγμα το μη ακέραιο πηλίκο

    \displaystyle \frac{7 \cdot 5 \cdot 3}{1 \cdot 2 \cdot 3},

    όπου ο αριθμητής περιέχει όλες τις κλάσεις mod 3.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 4, 2008 @ 5:18 μμ

  3. Έχετε δίκιο. Η σωστή απόδειξη είναι: αν έχεις ν διαδοχικούς φυσικούς στον αριθμητή και τους 1, 2, … , ν στον παρονομαστή, τότε για κάθε k\leq n στον παρονομαστή, ο ελάχιστος παράγοντας στον αριθμητή γράφεται σαν pk+q οπότε ο pk+q+(k-q) διαιρείται από τον k και είναι ο ίδιος παράγοντας στον αριθμητή διότι k-q\leq n-1.

    Μου αρέσει!

    Σχόλιο από ikonst — Μαΐου 5, 2008 @ 1:39 πμ

  4. ikonst:

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

    \displaystyle \frac{5 \cdot 6 \cdot 7}{1 \cdot 2 \cdot 3}.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 5, 2008 @ 8:01 πμ

  5. Τρέξτε τη διαδικασία που δίνω για το παράδειγμά σας, πχ για να δούμε ότι ο αριθμητής διαιρεί το 3. Έχουμε 5 = 3*1+2, οπότε 3*1 + 2 +(3-2) = 5 + 1 = 6.
    Αυτό δείχνει ότι το 6 διαιρεί το 3. Από την άλλη, για το 2,

    5 = 2*1 + 3 οπότε 2*1 + 3 + (2-1) = 5 + 1 = 6, δηλαδή δε δίνεται αναγκαστικά διαφορετικός παράγοντας κάθε φορά.

    Μου αρέσει!

    Σχόλιο από ikonst — Μαΐου 5, 2008 @ 12:35 μμ

  6. Το ότι κάθε παράγοντας του παρανομαστή διαιρεί τον αριθμητή δε συνεπάγεται ότι ολόκληρος ο παρανομαστής διαιρεί τον αριθμητή. Αυτό θα ήταν σωστό αν κάθε παράγοντας διαιρούσε διαφορετικό παράγοντα στον αριθμητή, που όμως δεν ισχύει. Άρα χρειάζεσαι κάτι άλλο μάλλον.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 5, 2008 @ 12:56 μμ

  7. sigh… έχετε δίκιο και πάλι. Να τη σκαπουλάρω εύκολα λέγοντας ότι για ακέραιο argument το πολυώνυμο έχει ως τιμή τον αντίστοιχο διωνυμικό συντελεστή και υπάρχει γνωστή συνδυαστική ερμηνεία της ποσότητας που δείχνει ότι είναι ακέραια; Μα θυμάμαι ότι υπήρχε κάτι παρόμοιο με τα επιχειρήματα που έχω πάνω και δούλευε.

    Μου αρέσει!

    Σχόλιο από ikonst — Μαΐου 5, 2008 @ 1:31 μμ

  8. Έχουμε λοιπόν από τη συνδυαστική ερμηνεία ότι το {x \choose n} είναι ακέραιος για x \ge 0.

    Για αρνητικό x χρησιμοποιούμε τον απλό τύπο

    \displaystyle {x \choose n} = (-1)^n {{-x+n-1}\choose{n}}.

    Αυτός προκύπτει απ’ ευθείας από τον ορισμό του {x \choose n}.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 5, 2008 @ 1:41 μμ

  9. Κάτι άλλο που είναι ενδιαφέρον να δείξετε σχετικά με τα ακεραιότιμα πολυώνυμα είναι το εξής:


    Αν ένα πολυώνυμο έχει βαθμό n και παίρνει ακέραιες τιμές για n+1 διαδοχικούς ακεραίους τότε παίρνει πάντα ακέραιες τιμές.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 5, 2008 @ 6:04 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

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