Σάββατο, 27 Οκτωβρίου 2012

Το Πρόβλημα του Κινέζου Μάγειρα

Σε μία επιδρομή 17 πειρατές αρπάζουν ένα μπαούλο γεμάτο με χρυσές λίρες (ίσης αξίας). Αποφασίζουν να τις μοιραστούν σε ίσα μέρη και να δώσουν το υπόλοιπο στον Κινέζο μάγειρα του καραβιού τους. Σ΄ αυτόν αντιστοιχούν 3 λίρες. Σε μία μάχη που έδωσαν οι πειρατές σκοτώθηκαν έξι από αυτούς. Στον μάγειρα τότε αντιστοιχούν 4 λίρες. Κατόπιν σε ένα ναυάγιο σώθηκαν μόνο έξι από αυτούς, το μπαούλο και ο μάγειρας. Στο μάγειρα τότε αντιστοιχούν 5 λίρες. Κατόπιν ο μάγειρας δηλητηριάζει τους πειρατές και παίρνει το μπαούλο. Πόσες λίρες τουλάχιστον περιέχει το μπαούλο; (Κατ.34/Νο.531)


Λύση

Λύση του Γιώργου Ριζόπουλου. Αν «x» o αριθμός (αναγκαστικά ακέραιος) των λιρών ,ψάχνουμε μια λύση (αν υπάρχει!) στο σύστημα x=17*a+3, x=11*b+4, x=6*c+5 Αυτό το σύστημα γράφεται: x=3 mod(17) x=4 mod(11) x=5 mod(6) Οι αριθμοί 17, 11 είναι πρώτοι και ο 6 αναλύεται στο γινόμενο πρώτων 2*3 ,έτσι οι 17,11,6 είναι relatively primes και σύμφωνα με το Θεώρημα του Κινέζικου Υπολοίπου (δεν ξέρω αν είναι δόκιμος στα ελληνικά ο όρος: Chinese Remainder Theorem ) υπάρχει λύση με mod το γινόμενο τους. mod(17*11*6) = mod(1122) 1.122/17= 66, 1.122/11=102, 1.122/6=187 Άρα προκύπτει το σύστημα: 66*x1=1 (mod17) (με λύση x1=8) 102*x2=1 (mod11) (με λύση x2=4) 187*x3=1 (mod6) (με λύση x3=1) Άρα τελικά η λύση x που ψάχνουμε είναι: x= 8* 66 * 3 + 4*102*4 + 1*187 *5= 4.151 (νομίσματα) Υπάρχουν άπειρες της μορφής 4.151 (mod 1.122), δηλαδή όλοι οι αριθμοί ν (θετικοί και αρνητικοί) της μορφής 4.151+ ν*1122 αποτελούν λύση του συστήματος. Για "ν" μικρότερο του μηδενός,λόγω του ότι το πρόβλημα ζητάει τον ελάχιστο αριθμό νομισμάτων, οι τιμές του ν θα είναι αρνητικές, έχουμε: Α.) x="17*a+3"> 785=17*a+3 --> a=(785-3)/17 --> a=782/17 --> a=46, Β.) x=11*b+4 --> 785=11*b+4 --> b=(785-4)/11 --> b=781/11 --> b=71, Γ.) x=6*c+5 --> 785=6*c+5 --> c=(785-5)/6 --> c=780/6 --> c=130 ΕΠΑΛΗΘΕΥΣΗ: A.) x=17*a+3 --> 785=17*46+3, B.) x=11*b+4 --> 785=11*71+4, Γ.) x=6*c+5 --> 785=6*130+5

7 σχόλια:

Γιώργος Ριζόπουλος είπε...

Αν X o αριθμός (αναγκαστικά ακέραιος) των λιρών ,ψάχνουμε μια λύση (αν υπάρχει!) στο σύστημα x=17*a+3, x=11*b+4, x=6*c+5
Aυτό το σύστημα γράφεται:
x=3 mod(17)
X=4 mod(11)
X=5 mod(6)
Οι αριθμοί 17, 11 είναι πρώτοι και ο 6 αναλύεται στο γινόμενο πρώτων 2*3 ,έτσι οι 17,11,6 είναι relatively primes και σύμφωνα με το Θεώρημα του Κινέζικου Υπολοίπου (δεν ξέρω αν είναι δόκιμος στα ελλην. ο όρος: Chinese Remainder Theorem ) υπάρχει λύση με mod το γινόμενό τους mod (17*11*6) = mod(1122)
1122/17= 66, 1122/11=102, 1122/6=187
Άρα προκύπτει το σύστημα
66*x1=1 (mod17) (με λύση x1=8)
102*x2=1 (mod11) (με λύση χ2=4)
187*χ3=1 (mod6) (με λύση χ3=1)
Άρα τελικά η λύση x που ψάχνουμε είναι:
X= 8* 66 * 3 + 4*102*4 + 1*187 *5= 4151 (νομίσματα)
ΕΠΑΛΗΘΕΥΣΗ: Α. 244 *17=4148 (υπολ. 3 )

Β. 377*11= 4147 (υπολ. 4)

Γ. 691*6=4146 (υπολ.5)

Γιώργος Ριζόπουλος είπε...

Να συμπληρώσω στο προηγούμενο σχόλιό μου βέβαια, ότι αυτή είναι η ελάχιστη δυνατή λύση. Υπάρχουν άπειρες της μορφής 4151 (mod 1122), δηλαδή όλοι οι αριθμοί ν (και οι αρνητικοί ,αλλά προφανώς δεν μας ενδιαφέρουν) της μορφής 4151+ ν*1122 αποτελούν λύση του συστήματος ,άρα ικανοποιούν τις συνθήκες του προβλήματος. Πχ. για ν=1 έχουμε 5273, για ν=2 έχουμε 6395 κλπ.
Ίσως θα έπρεπε να ξέρουμε το μέγεθος του σεντουκιού για να κάνουμε μια πιο ακριβή εκτίμηση.:-)

Γιώργος Ριζόπουλος είπε...

Mόλις πόσταρα το προηγούμενο συνειδητοποίησα το λάθος (που βασικά ξεκινάει από τον λάθος αρχικό προσδιορισμό των ελαχίστων «πρώτων ανα δύο» που έκανα στο αρχικό σχόλιο. Η συνέχεια και η μέθοδος(και το 1ο αποτέλεσμα) είναι σωστή βεβαία).
Οπότε επανέρχομαι από κεί που σταμάτησα πριν ,και έχουμε
Για ν=-1 3029
Για ν=-2 1907
Για ν=-3 785 (που είναι και η ελάχιστη λύση , μετά περνάμε σε αρνητικούς αριθμούς)
Δύσκολο πράμα οι διοφαντικές εξισώσεις με άρωμα άπω ανατολής!

Ανώνυμος είπε...

O ελάχιστος αριθμός των νομισμάτων είναι 785.
Επαλήθευση:
785=17*46+3
785=11*71+4
785=6*130+5

Μια άλλη λύση είναι 1907(δεν είναι όμως η ελαχίστη).
Επαλήθευση:
1907=17*112+3
1907=11*173+4
1907=6*317+5.

Οι λύσεις είναι άπειρες.
Το πρόβλημα όμως με την έκφραση "Πόσες λίρες τουλάχιστον περιέχει το μπαούλο"; υπονοεί τον ελάχιστο αριθμό νομισμάτων με τις δοθείσες ιδιότητες.

@Γιώργο Ριζόπουλο.
Ο αριθμός 4148 είναι λύση, δεν είναι όμως η ελάχιστη.

Ν.Lntzs

Γιώργος Ριζόπουλος είπε...

Kαλημέρα σε όλους!
@N.Lintzs: Η παρατήρησή σας στο τέλος, υποθέτω ότι έγινε έχοντας υπόψι σας μόνο το αρχικό μου σχόλιο. Γιατί αλλιώς δεν βγαίνει νόημα.
Ίσως ο αγαπητός papaveri να έβρισκε έναν τρόπο, τα σχόλια των "συνήθων υπόπτων" (=μόνιμοι θαμώνες/λύτες) να δημοσιεύονται σε real time?

batman1986 είπε...

@Γιώργος Ριζόπουλος

Η ένσταση μου είναι ότι δεν μπορούμε όλοι να είμαστε απίκο πάνω από τον υπολογιστή.Το πιο δίκαιο θα ήταν να δίνει ένα χρονικό όριο προκαθορισμένο από τα πριν για την λύση του γρίφου και εν συνεχεία να δημοσιεύει τις απαντήσεις(μίας μέρας το μάξιμουμ ξέρω γω...)

Papaveri είπε...

@batman1986
Ας μου γράψει ο καθ' ένας πόσο χρόνο προτιμάτε πριν τη δημοσίευση της λύσης. Περιμένω γνώμες.

 

Papaveri48 © 2010

PSD to Blogger Templates by OOruc & PSDTheme by PSDThemes