hikikosite

Ένας χρήστης παίζει με τον υπολογιστή ως εξής:

Σε κάθε γύρο, ο χρήστης λέει έναν ακέραιο αριθμό από το 1 έως το 10 και ο υπολογιστής λέει έναν άλλο. Το παιχνίδι συνεχίζεται ώσπου όλοι οι αριθμοί που έχει πει ο χρήστης σε όλους τους γύρους να δίνουν άθροισμα με όλους τους αριθμούς που έχει πει ο υπολογιστής σε όλους τους γύρους τον αριθμό 101. Ο χρήστης και ο υπολογιστής παίζουν εναλλάξ σε κάθε γύρο. Το πλήθος των γύρων μπορεί να διαφέρει από παιχνίδι σε παιχνίδι, ανάλογα με τους αριθμούς που επιλέγει ο καθένας.

Αν για παράδειγμα στο τέλος κάποιου γύρου το άθροισμα των αριθμών που έχουν πει οι δύο παίκτες είναι 98 και ο παίκτης που παίζει πει τον αριθμό 2, ο επόμενος παίκτης είναι αναγκασμένος να επιλέξει τον αριθμό 1, ώστε το συνολικό άθροισμα να μην ξεπεράσει το 101, αν ο παίκτης πει 3 το παιχνίδι σταματά, αν πει 4 είναι άκυρη επιλογή και πρέπει να ξαναεπιλέξει αριθμό.

Πώς επιλέγεται ο νικητής:
Όταν και οι 2 παίκτες (υπολογιστής και χρήστης) έχουν πει όλους τους αριθμούς και το άθροισμα έχει φτάσει 101, υπολογίζεται το άθροισμα των αριθμών που είπε ο χρήστης (έστω sumA) και το άθροισμα των αριθμών που είπε ο υπολογιστής (έστω sumB) σε κάθε γύρο. Αν οι αριθμοί sumA και sumB είναι πρώτοι μεταξύ τους, τότε κερδίζει ο υπολογιστής. Αν όχι, κερδίζει ο χρήστης.

Η ερώτηση είναι:
Με ποιο τρόπο (αλγόριθμο) μπορεί να παιχτεί το παιχνίδι από τον υπολογιστή ώστε ο χρήστης να μην έχει καμιά ελπίδα να κερδίσει;

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

Λύση… (Μην κλέβετε!)

Αν οι αριθμοί sumA και sumB είχαν έναν κοινό διαιρέτη μεγαλύτερο του 1, τότε αυτός θα διαιρούσε το άθροισμά τους και τη διαφορά τους. Έτσι θα διαιρούσε και το sumA+sumB=101. Το 101 όμως είναι πρώτος αριθμός και διαιρείται μόνο από τον εαυτό του και τη μονάδα. Άρα οι sumA και sumB δεν μπορούν να έχουν κοινό διαιρέτη και θα είναι πάντα πρώτοι μεταξύ τους. Επομένως η τακτική που μπορεί να χρησιμοποιήσει ο υπολογιστής είναι η εξής: Λέγε τυχαίους αριθμούς από το 1 ως το 10 ώσπου το sumA+sumB να είναι 101 και θα κερδίσεις…