Πώς να βρεις τρεις άγνωστους αριθμούς με δύο ερωτήσεις 🔍🔢

Φανταστείτε ότι κάποιος σκέφτηκε τρεις φυσικούς αριθμούς x, y, z. Εσείς δεν ξέρετε τις τιμές τους, αλλά σας επιτρέπεται να κάνετε δύο ερωτήσεις.

Κάθε ερώτηση έχει τη μορφή:

$$S=a\cdot x+b\cdot y+c\cdot z$$

όπου επιλέγετε εσείς τους συντελεστές $a$, $b$, $c$, και το άτομο σας απαντάει με το αποτέλεσμα $S$.

Στόχος: να βρείτε με βεβαιότητα τις τιμές των $x$, $y$ και $z$.

---

Έξυπνη στρατηγική ✅

Αν γνωρίζετε ένα άνω όριο $M$ για τους αριθμούς (δηλαδή ξέρετε ότι $0 \le x,y,z \le M$), τότε αρκεί μόνο μία ερώτηση!

1. Επιλέξτε:

   $$(a,b,c)=(1,B,B^2)$$

   όπου $B = M + 1$.

2. Κάνετε την ερώτηση και παίρνετε:

   $$S=x+By+B^{2}z$$

3. Βρίσκετε τους αριθμούς απευθείας από το $S$:

   $$x=S<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>B$$$$y=\lfloor \frac{S}{B}\rfloor <mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>B$$$$z=\lfloor \frac{S}{B^2}\rfloor$$

Η τιμή του $S$ λειτουργεί σαν αναπαράσταση σε βάση $B$, άρα οι τρεις αριθμοί προκύπτουν αμέσως!

---

Παράδειγμα

Ας πούμε ότι $x=7$, $y=13$, $z=25$, και ξέρουμε ότι κανένας αριθμός δεν ξεπερνά το $M=500$.

• Διαλέγουμε $B = 501$.

• Ρωτάμε:

  $$S=x+501y+{501}^{2}z$$

• Η απάντηση είναι:

  $$S=7+13\cdot 501+25\cdot {501}^2$$

• Από το $S$, βρίσκουμε:

  $$x=S<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>501,y=\lfloor \frac{S}{501}\rfloor <mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>501,z=\lfloor \frac{S}{{501}^2}\rfloor$$

---

Αν δεν γνωρίζετε άνω όριο

Όταν δεν γνωρίζουμε άνω όριο, επιλέγουμε δύο διαφορετικούς αριθμούς $B$ και $B'$ που είναι αμοιβαία πρώτοι (δηλαδή $\gcd(B,B')=1$).
Μετά, εφαρμόζουμε το Κινέζικο Θεώρημα Υπολοίπων (CRT) για να βρούμε μοναδικά τις τιμές των $x,y,z$.