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

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

Πηγή:http://eisatopon.blogspot.gr/2012/08/blog-post_8656.html

Λύση

Λύση του Γιώργου Ριζόπουλου. Αν «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