Ένα χαλασμένο ασανσέρ....και μια γραμμική διοφαντική εξίσωση!!!

     Ένα ωραίο πρόβλημα που βρήκα σε ενα μαθηματικό δελτίο  που εκδίδει το  τμήμα μαθηματικών του Augsburg  είναι το εξής :
   Το ασανσέρ ενός ουρανοξύστη  65 οροφών έχει χαλάσει .Όταν κάποιος θέλει να ανέβει , μπορεί να το κάνει ανεβαίνοντας  μόνο 8 ορόφους (ούτε λιγότερο ούτε περισσότερο) . Αν δεν μπορεί να ανέβει 8 ορόφους  παραμένει ακινητοποιημένο .
Για παράδειγμα, αν  το ασανσέρ βρίσκεται στο όροφο 61  και πατήσουμε το κουμπί να ανέβει  τότε παραμένει στον όροφο 61.

Όταν πάλι κάποιος θέλει να κατέβει  πρέπει να έχει υπ όψι του ότι το ασανσέρ κατεβαίνει μόνο  11 ορόφους (ούτε λιγότερο ουτε περισσότερο) αν δεν μπορεί να κατέβει 11 ορόφους παραμένει ακινητοποιημένο. Για παράδειγμα, αν το κουβούκλιο του ασανσέρ βρίσκεται στον όροφο 5 και πατήσουμε το κουμπί για κάτω  τότε παραμένει ακινητοποιημένο.

   Για ευκολία μπορούμε να φανταστούμε οτι υπάρχουν μόνο δυο κουμπιά ,ένα για άνοδο και ένα για κάθοδο.
  Το ασανσέρ  βρίσκεται στο πρώτο όροφο  . Το ερώτημα που τίθεται είναι αν με τις  συνθήκες που προαναφέραμε   ,μπορούμε να έχουμε πρόσβαση σε κάθε όροφο;

Λύση

  Είναι δυνατό να φτάσουμε σε κάθε όροφο του κτιρίου. Στον παρακάτω πίνακα  φαίνεται πως κάθε όροφος είναι προσβάσιμος .  Οι γραμμές  παριστάνουν την άνοδο του ασανσέρ κατά 8 ορόφους  ,ενώ οι στήλες  την κάθοδο κατά 11  ορόφους.  Με εκκίνηση το 1 στο παρακάτω πίνακα κινούμαστε δεξιά  ανεβαίνοντας κατά 8 ορόφους και κινούμενοι κάτω κατεβαίνουμε 11 ορόφους . Οι διαφορετικές διαδρομές που υπάρχουν στον πίνακα μπορούν να οδηγήσουν σε κάθε όροφο.

Πατάμε το κουμπί για άνοδο  ( 8 ορόφων)

Πατάμε το κουμπί για κάθοδο (11 ορόφων)

9  17  25   33   41   49  57  65       6   14  22  30    38  46   54   62              3    11  19    27  35   43   51    59                          8      16   24   32  40    48  56  64                                   5     13   21  29    37  45   53   61                                            2    10  18    26  34   42   50   56                                                          7     15   23   31  39    47  55  63                                                                  4     12   20  28   36   44  52  60

   Ουσιαστικά η λύση του προβλήματος  ανάγεται κάθε φορά στην λύση της εξίσωσης :

8χ-9ψ=αριθμός ορόφου       ή    8χ-9ψ= ν , ν=1,2,3…,64,65 

   Οι εξισώσεις αυτής της μορφής   αχ+βψ=γ  όπου α,β, γ ακέραιοι ονομάζονται  γραμμικές διοφαντικες εξισώσεις  και έχουν λύση αν ο μέγιστος κοινός  διαιρέτης των α, β  διαιρεί το γ.

   Στην εξίσωση του προβλήματος ο μέγιστος κοινός διαιρέτης των αριθμών 8,11 είναι το 1 που προφανώς διαιρεί κάθε αριθμό άρα η εξίσωση έχει πάντα λύση και κατ επέκταση  για κάθε αριθμό από 1 μέχρι το 65.

( περισσότερα για τις διοφαντικές γραμμικές εξισώσεις  ΠΑΤΗΣΤΕ ΕΔΩ)

Η μεγαλύτερη διαδρομή που πρέπει  να  κάνει κάποιος με  όροφο εκκίνησης τον πρώτο είναι να καταλήξει στον 60^ο όροφο. Δείτε την ακολουθία των οροφών που απαιτούνται.

1, 9, 17, 25, 33, 41, 49, 57, 65, 54, 43, 32, 21, 10, 18, 7, 15, 4, 12, 20, 28, 36, 44, 52, 60.