Blog Μαθηματικών και Εκπαιδευτικών Θεμάτων

Από, Fédération Suisse des Jeux Mathématiques 2017-18, 320, finale suisse, prob. 16

Το πρόβλημα: Στον στόχο, ο κεντρικός δίσκος αξίζει 31 πόντους, o ενδιάμεσoς δίσκος 24 πόντους και ο εξωτερικός 13 πόντους. Προσδιορίστε¹ τον μεγαλύτερο ακέραιο συνολικό αριθμό πόντων που είναι αδύνατο να επιτευχθεί².

Υπολογισμός: H επίλυση του προβλήματος με τη βοήθεια ενός Η/Υ είναι πολύ απλή. Οι διαγωνιζόμενοι όμως δεν είχαν αυτή τη δυνατότητα. Αν αντιγράψτε τον κώδικα και τον τρέξετε σε ένα compiler (π.χ. εδώ compiler python), θα δείτε ότι αυτός δίνει τον αριθμό \(F(13,24,31) = 121\).

def find_largest_unreachable_sum(scores):
  """
  Υπολογίζει τον μεγαλύτερο αριθμό (Αριθμός Frobenius) που δεν μπορεί να
  δημιουργηθεί από το άθροισμα των αριθμών στη λίστα 'scores'.
  Αυτή η υλοποίηση είναι αποδοτική για μικρά σύνολα αριθμών.
  """
  # Ορίζουμε ένα όριο για την αναζήτηση. Πρέπει να είναι αρκετά μεγάλο
  # για να είμαστε σίγουροι ότι έχουμε βρει τον αριθμό. 250 είναι υπεραρκετό.
  limit = 250
  # Δημιουργούμε μια λίστα boolean όπου θα σημειώνουμε τους αριθμούς που πετυχαίνουμε.
  # Ξεκινάμε με όλους τους αριθμούς ως "False" (μη επιτεύξιμοι).
  reachable = [False] * limit
  # Το 0 είναι πάντα επιτεύξιμο (0 βολές).
  reachable[0] = True
  # Για κάθε αριθμό 'i' από το 1 μέχρι το όριό μας...
  for i in range(1, limit):
    #...ελέγχουμε αν μπορούμε να τον φτάσουμε.
    # Για κάθε πόντο στη λίστα μας...
    for score in scores:
      #...αν ο αριθμός 'i' είναι μεγαλύτερος ή ίσος του πόντου,
      # και αν ο αριθμός (i - score) ήταν ήδη επιτεύξιμος...
      if i >= score and reachable[i - score]:
        #...τότε και ο 'i' είναι επιτεύξιμος.
        reachable[i] = True
        # Δεν χρειάζεται να ελέγξουμε τους υπόλοιπους πόντους, οπότε προχωράμε στον επόμενο 'i'.
        break
  # Τώρα, ψάχνουμε από το τέλος της λίστας προς την αρχή
  # για να βρούμε τον μεγαλύτερο αριθμό που παρέμεινε "False".
  largest_unreachable = -1
  for i in range(limit - 1, -1, -1):
    if not reachable[i]:
      largest_unreachable = i
      break
  return largest_unreachable
# Οι πόντοι από το πρόβλημα
points = [13, 24, 31]
result = find_largest_unreachable_sum(points)
print(f"Οι πόντοι είναι: {points}")
print(f"Ο μεγαλύτερος αριθμός που δεν μπορεί να επιτευχθεί είναι: {result}")

Για την εύρεση του αριθμού που ζητάει το πρόβλημα θα εφαρμόσουμε 2 εργαλεία: το θεώρημα Frobenius και τοn αλγόριθμο Rodserth.

Θεώρημα Frobenius: Όλα τα αθροίσματα \(ax+by+cz\), \(a,b,c,x,y,z\in\mathbb{N}\), \(MΚ\Delta(a,b,c)=1\), είναι πιθανά πάνω από έναν αριθμό F που ονομάζεται αριθμός Frobenius. \(\square\)

Αλγόριθμος Rødseth³:

1. Επίλυση βασικής εξίσωσης: \(24y\equiv c\pmod a\) βρίσκοντας τον ελάχιστο \(x_0\).
2. Κατασκευή του λόγου \(\frac{a}{x_0}\)
3. Αναδρομική διαδικασία
4. Τελικός τύπος $$F(a,b,c)=-a+b(s_n-1)+c(p_{n+1}-1)-\min (bs_{n+1},cp_n)$$

1. Επίλυση βασικής εξίσωσης

Υπολογισμός του μικρότερου \(s_0\), \(0\leq s_0<a\), τέτοιου ώστε \(bs\equiv a\pmod a\). $$24s\equiv 31 \pmod {13}\Leftrightarrow 11 s \equiv 5 \pmod {13} \Leftrightarrow 66s \equiv 30\pmod {13} \Leftrightarrow s \equiv 4\pmod {13}$$ Άρα, \(s+0=4<13\).

2. Υπολογισμός των αρνητικών υπολοίπων \(-s_i\) του Ευκλειδείου αλγορίθμου \(a\div s_0\) και αναδρομική διαδικασία

$$\begin{array}{l} a=q_1s_0-s_1\text{ με } 0\leq s_1<s_0\Rightarrow 13=4q_1-s_1,\ 0\leq s_1<4\text{ άρα, } \boxed{q_1=4, s_1=3}\\ s_0=q_2s_1-s_2\text{ με } 0\leq s_2<s_1\Rightarrow 4=3q_2-s_2,\ 0\leq s_2<3\text{ άρα, } \boxed{q_2=2, s_2=2}\\ s_1=q_3s_2-s_3\text{ με } 0\leq s_3<s_2\Rightarrow 3=2q_3-s_3,\ 0\leq s_3<2\text{ άρα, } \boxed{q_3=2, s_3=1}\\ s_2=q_4s_3-s_4\text{ με } 0\leq s_4<s_3\Rightarrow 2=2q_4-s_4,\ 0\leq s_4<2\text{ άρα, } \boxed{q_4=2, s_4=0} \end{array}$$

Εύρεση δείκτη \(n\). Υπολογισμός \(p_i\) και \(r_i\) με \(i=0\dots n\), έτσι ώστε \(r_{n+1}\leq 0<r_n\). Επίσης, \(p_{i+1}=p_iq_{i+1}-p_{i-1}\) με \(p_{-1}=0,\ p_0=1\). $$ar_i-s_ib+p_ic=0\Leftrightarrow r_i=\frac{s_ib-p_ic}{a}$$

‘Αρα,

$$\begin{array}{rl} p_1=p_0q_1-p_{-1}=4,& r_0=\displaystyle{\frac{s_0b-p_0c}{a}=\frac{4\cdot 24 -31}{13}}=\displaystyle{\frac{65}{13}}=5\\ p_2=p_1q_2-p_0=4\cdot 2 -1 =7, & r_1=\displaystyle{\frac{s_1b-p_1c}{a}=\frac{3\cdot 24-4\cdot 31}{13}=-4}\end{array}$$

Επειδή, \(r_1=-4\leq 0<r_0=5\) άρα \(n=0\).

3. Τελικός τύπος

$$\begin{array}{lcl} F(13,24,31)&=&-13+24(s_0-1)+31(p_1-1)-\min (24s_1,31p_0)\\ &=& -13+24(4-1)+31(4-1)-\min(24\cdot 3, 31\cdot 1)\\ &=& 121 \end{array}$$

Συμπέρασμα: Ο μεγαλύτερος ακέραιος συνολικός αριθμός πόντων που είναι αδύνατο να επιτευχθεί είναι 121. \(\blacksquare\)

1. Γνωστός σαν αριθμός του Frobenius (Ferdinand Georg Frobenius, 1849-1917). ↩︎
2. μτφρ. Λυγάτσικας Ζ. ↩︎
3. Rødseth (1978) On a linear Diophantine problem of Frobenius Journal für die reine und angewandte Mathematik.
   Rødseth (1979) On a linear Diophantine problem of Frobenius II ↩︎