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

20 Μαρτίου, 2008

Ποιο πολυώνυμο;

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

Ένα πολυώνυμο P(x) έχει μη αρνητικούς ακέραιους συντελεστές. Βρείτε ποιο είναι το πολυώνυμο αυτό ρωτώντας μόνο δύο ερωτήσεις του τύπου «Πόσο είναι το P(x);», για όποιες δύο ακέραιες τιμές του x θέλετε; Δείξτε επίσης ότι μπορείτε να «αποφασίσετε» ποιο είναι το P(x) με μόνο μια ερώτηση «Πόσο είναι το P(x);» αλλά με x όχι αναγκαστικά ρητό αριθμό.

2 Σχόλια »

  1. Θα ρωτήσουμε για το P(1) και στη συνεχεια το P(k) όπου k ενας ακεραιος μεγαλύτερος του P(1). δλδ
    k > P(1) = a_0+...+ a_N
    και επειδή κάθε a_i είναι μη αρνητικό έχουμε k> a_i για κάθε i. Τότε κάθε a_i = [P(k) / k^i] \bmod k.

    Για τη λύση με μία ερώτηση αρκεί να ρωτήσουμε με έναν άρρητο υπερβατικό αριθμό r. Τότε το πολυώνυμο που θα αντιστοιχει στην απάντηση θα είναι μοναδικό. Έστω ότι υπαρχουν 2 πολυώνυμα P(x) και Q(x) με ρητούς συντελεστες τέτοια ώστε P(r)=Q(r). Tότε το πολυώνυμο P(x)-Q(x) που έχει και αυτό ρητούς συντελεστες θα πρέπει να είναι το 0 διαφορετικά θα είχε ρίζα το r που είναι άτοπο.

    Μου αρέσει!

    Σχόλιο από ctzamos — 21 Μαρτίου, 2008 @ 12:31 μμ

  2. Πολύ σωστά. Και στη δεύτερη περίπτωση, με τη μια ερώτηση μόνο, πρέπει να τονιστεί ότι δεν είναι αλγοριθμικός ο τρόπος εύρεσης του πολυωνύμου (ενώ με τις δύο ερωτήσεις είναι). Γι’ αυτό και η λέξη «αποφασίσετε» είναι μέσα σε εισαγωγικά.

    Για παράδειγμα, δεν είναι καθόλου προφανές το πώς μπορεί κανείς να αναπαραστήσει ακριβώς ένα υπερβατικό αριθμό (ένα αριθμό δηλ. που δεν ικανοποιεί καμία πολυωνυμική εξίσωση με ακεραίους συντελεστές);

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 23 Μαρτίου, 2008 @ 12:53 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Blog στο WordPress.com.