forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 19 Νοέμ 2017, 20:02

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 9 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Πολυώνυμο
ΔημοσίευσηΔημοσιεύτηκε: 05 Μαρ 2016, 11:36 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 05 Φεβ 2008, 03:03
Δημοσ.: 420
Έστω ότι έχουμε δύο παίκτες Α και Β, και ο Α σκέφτεται ένα πολυώνυμο p(x) με συντελεστές μη αρνητικούς ακεράιους, το οποίο ο Β δε γνωρίζει. Ο Β ψάχνει να βρει το πολυώνυμο, και μπορεί να ρωτήσει τον Α μόνο την τιμή του p(n), όπου ο n\in\mathbb N επιλέγεται από τον B. Σε πόσες ερωτήσεις μπορεί να βρει ο Β το πολυώνυμο;

_________________
\emptyset\not=\{\emptyset\}


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πολυώνυμο
ΔημοσίευσηΔημοσιεύτηκε: 05 Μαρ 2016, 12:28 
Χωρίς σύνδεση

Εγγραφη: 09 Σεπ 2014, 09:17
Δημοσ.: 54
Υποθετω οτι αν κανεις την διαδικασια επαγωγικα θα καταληξεις σε γραμμικο συστημα με ιδιους συντελεστες κ αγνωστους .
Δηλαδη ,αν θεωρησεις οτι το δοσμενο πολυωνυμο βαθμου 0,τοτε δυο τιμες φυσικων αριθμων αρκουν.(θα σ δωσουν την ιδια τιμη κ επισης,αφου οι συντελεστες ειναι μη αρνητικοι θα ειναι αδυνατον για δυο διαφορετικες τιμες n,m να παρεις p(n)=p(m))
Τωρα,αν θεωρησεις οτι ειναι βαθμου 1,για δυο διαφορετικες τιμες ,παιρνεις ενα γραμμικο συστημα με 2 εξισωσεις κ 2 αγνωστους.
Ομοιως,υποθετεις οτι ειναι βαθμου 2,3,... μεχρι να βρεις ακριβως τι βαθμου ειναι το ζητουμενο πολ/μο.
Με καθε επιφυλαξη παντα!


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πολυώνυμο
ΔημοσίευσηΔημοσιεύτηκε: 06 Μαρ 2016, 04:44 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 05 Φεβ 2008, 03:03
Δημοσ.: 420
Η απάντηση (περιέργως) δεν εξαρτάται από το βαθμό του πολυωνύμου.

_________________
\emptyset\not=\{\emptyset\}


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πολυώνυμο
ΔημοσίευσηΔημοσιεύτηκε: 06 Μαρ 2016, 15:17 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 12 Μαρ 2006, 22:43
Δημοσ.: 3627
Τοποθεσια: Αθήνα
Για την απάντηση δείτε το θεώρημα παρεμβολής του Lagrange. Περισσότερες πληροφορίες εδώ

_________________
Ευάγγελος Ράπτης


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πολυώνυμο
ΔημοσίευσηΔημοσιεύτηκε: 06 Μαρ 2016, 22:58 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 05 Φεβ 2008, 03:03
Δημοσ.: 420
Υπάρχει τρόπος να βρεθεί το πολυώνυμο σε δύο μόνο ερωτήσεις, ανεξάρτητα από το βαθμό. Πρέπει κάπου να χρησιμοποιηθεί το ότι οι συντελεστές είναι μη αρνητικοί ακέραιοι.

_________________
\emptyset\not=\{\emptyset\}


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πολυώνυμο
ΔημοσίευσηΔημοσιεύτηκε: 07 Μαρ 2016, 21:50 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 22 Ιαν 2009, 21:24
Δημοσ.: 176
Εκπληκτικό πρόβλημα, εντυπωσιάστηκα! Για να μην το χαλάσουμε σε όποιον θέλει να το σκεφτεί, να παίξουμε το παιχνίδι να δούμε αν μπορεί κανείς να βρει τον αλγόριθμο;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πολυώνυμο
ΔημοσίευσηΔημοσιεύτηκε: 07 Μαρ 2016, 23:33 
Χωρίς σύνδεση
Άβαταρ μέλους

Εγγραφη: 02 Οκτ 2012, 19:57
Δημοσ.: 61
Μπορεί η δεύτερη τιμή που ρωτάμε να εξαρτάται απο την πρώτη; (πχ p(1) και p(p(1)))


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πολυώνυμο
ΔημοσίευσηΔημοσιεύτηκε: 07 Μαρ 2016, 23:44 
Χωρίς σύνδεση
Άβαταρ μέλους

Εγγραφη: 16 Ιούλ 2012, 17:35
Δημοσ.: 43
Μια πρώτη προσπάθεια, μπορεί να φαίνεται κάπως μπακαλίστικη. Βέβαια τα παρακάνω θέλουν και μια απόδειξη της προκοπής.

Μιας και το p(0) δεν δίνει κάτι πέρα από τον σταθερό όρο (αν δεν πάρεις το 0 στους φυσικούς, ένας λόγος παραπάνω να το ξεχάσουμε) και το p(n) για n\geqslant 2 πρακτικά πρέπει να είναι εντελώς δύσχρηστο, ειδικά για μεγάλους βαθμούς πολυωνύμων, θα έλεγα ότι θα παίξει ρόλο το p(1) που είναι και το άθροισμα των συντελεστών. Πονηρά σκεπτόμενος, ίσως να είναι η p(p(1)) η δεύτερη τιμή που θέλει κανείς. Προς το παρόν, δεν έχω λόγο να το θεωρήσω σωστό, αλλά αν μου πεις να ποντάρω κάπου τα λεφτά μου, εκεί θα τα βάλω.

Σκέψη: Ένα πολυώνυμο ως προς x θυμίζει την ανάλυση ενός φυσικού σε x-αδική αναπαράσταση. Το γεγονός ότι οι συντελεστές είναι μη αρνητικοί είναι για να έχουμε μοναδική γραφή (από θεωρία αριθμών). Ίσως για να δοθεί μια απόδειξη να πρέπει να ανατρέξει κανείς στην απόδειξη της ύπαρξης και μοναδικότητας της αναπαράστασης αυτής.

Παράδειγμα: Ας πάρουμε το p(x)=5x^3+2x+6. Έχουμε p(1)=13 και p(p(1))=p(13)=5\cdot 13^3+2\cdot 13+6. Ξέχνα τώρα εσύ το πολυώνυμο και πες ότι είμαι ο Α και εσύ ο Β και με ρωτάς τις τιμές p(1) και p(p(1)). Σου λέω ότι είναι 13 και 11017 αντίστοιχα, άρα αναλύεις το 11017 στη 13-αδική του αναπαράσταση, δηλαδή 11017=5\cdot 13^3+2\cdot 13+6. Τότε μου λες ότι p(x)=5x^3+2x+6, πολυώνυμο το οποίο επαληθεύει τις παραπάνω τιμές. Οπότε, αν δεν είχαμε μη αρνητικούς συντελεστές, θα γράφαμε και με άλλους τρόπους το p(13)=11017 και έτσι θα βρίσκαμε ενδεχομένως και άλλο πολυώνυμο που κάνει τη δουλειά.

Βέβαια, αν κάνεις την ίδια διαδικασία με τις τιμές p(1)=5 και p(5)=12=2\cdot 5+2, παίρνεις το p(x)=2x+2, που δεν επαληθεύει την πρώτη σχέση. Αυτή τη στιγμή δεν βλέπω τι χρειάζεται για να δουλέψει. Επίσης, σκέτες δυνάμεις του x δεν δουλεύουν, αν π.χ. πάρεις p(1)=3 και p(3)=27=3^3, το p(x)=x^3 δεν κάνει, κάνει όμως το p(x)=3x^2, που είναι λογική σκέψη γιατί το εξαναγκάζεις να δουλέψει, ''τραβώντας'' τον ''σωστό'' συντελεστή μπροστά. Τέλος, αν p(1)=1 τα παραπάνω δεν δείχνουν να δίνουν κάτι, θα μπορούσε να είναι οποιοδήποτε πολυώνυμο της μορφής p(x)=x^k και από την στιγμή που ο Α έχει ήδη ένα στο μυαλό του, δύσκολο να το βρει ο Β.

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


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πολυώνυμο
ΔημοσίευσηΔημοσιεύτηκε: 08 Μαρ 2016, 03:36 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 05 Φεβ 2008, 03:03
Δημοσ.: 420
dmsx έγραψε:
Σκέψη: Ένα πολυώνυμο ως προς x θυμίζει την ανάλυση ενός φυσικού σε x-αδική αναπαράσταση. Το γεγονός ότι οι συντελεστές είναι μη αρνητικοί είναι για να έχουμε μοναδική γραφή (από θεωρία αριθμών). Ίσως για να δοθεί μια απόδειξη να πρέπει να ανατρέξει κανείς στην απόδειξη της ύπαρξης και μοναδικότητας της αναπαράστασης αυτής.


Πολύ ωραίος, η ιδέα είναι ακριβώς αυτή. Τα υπόλοιπα θέλουν ακόμα μία τροποποίηση.

_________________
\emptyset\not=\{\emptyset\}


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 9 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group