Μαθηματικά για όλους!!

[Μάκης Χατζόπουλος]

Εγκαινιάζουμε ένα νέο θέμα, το Μαθηματικά για όλους‼

Αυτό που θα κάνουμε εδώ είναι να προτείνουμε θέματα ή να λύνουμε θέματα που δίνονται από τους συμφουρίστες, με όποιο τρόπο επιθυμούμε, μαθηματικό ή μη!

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

Τον τίτλο τον σκέφτηκα από το περιοδικό "φ" του Βασίλη Βισκαδουράκη όταν παρακολουθούσα την συγκέντρωση που έγινε πρόσφατα στην Αθήνα και αναφέρθηκε ότι υπάρχει ένα αντίστοιχο άρθρο (Μαθηματικά για την οικογένεια). Επειδή δεν έχω διαβάσει τα εν λόγω κείμενα, φαντάστηκα ότι κάτι ανάλογο θα έχει, ας με διαψεύσει κάποιος αν κάνω λάθος...

Αν συνδράμουμε όλοι, πιστεύω ότι θα δούμε ωραία και απολαυστικά θέματα-προβλήματα που θα ενδιαφέρουν όλη την οικογένεια!

Ξεκινάω με το πρώτο πρόβλημα!

Πρόβλημα 1
Οι αξία των τεσσάρων ζώων (πρόβατο, κόκκορας, πουλί, αγγελάδα) σε ένα χωριό της Νάξου, δίνεται από τις παρακάτω ισότητες (όπως φαίνεται στο σχήμα). Βρείτε τη σχέση που υπάρχει το πουλί (Σπίνος) με την αγγελάδα

Υ.Γ: Η μαθηματική εξήγηση του εν λόγου πρωβλήματος νομίζω ότι είναι φανερή για τους μαθητές της Β' Γυμνασίου και άνω...

[Γιώργος Ρίζος]

Μάκη, μόλις γύρισα από το χωριό μου κι έφερα κι ένα προβατάκι (σαν αυτό της Νάξου), έναν κόκορα κι ένα σπίνο. Βλέπω ότι η ισοτιμία είναι ένα πρόβατο για δυο κόκορες (κι όχι κότες, ψάξε από κάτω και θα δεις τη διαφορά) και ένα σπιούνο.

Κάνω την ανταλλαγή (δίνω το πρόβατό μου), οπότε έχω τρεις κόκορες και δυο σπίνους.
Οι κόκορες κάνουν εξαιρετική κερκυραϊκή παστιτσάδα, οπότε τους ανταλλάσσω εύκολα με έξι σπίνους. Έχω οκτώ σπίνους! Τι να τους κάνω; Τους δίνω και παίρνω μια αγελαδίτσα. Ξαναγυρνώ στο χωριό μου, πανευτυχής. Πάω να μαζέψω σανό για το χειμώνα.

Γιώργος Ρίζος

[chris]

Πολύ ωραίο θέμα κ.Μάκη . Να δούμε και κάτι πιο μαθηματικό γιατί η αναλυτική περιγραφή του κ.Ρίζου με έκανε να πεινάσω(παστιτσάδα...μιαμ )

Αν ονομάσουμε Κ τις κότες,Σ τους σπίνους,Π τα πρόβατα και Α την αγελάδα τότε οδηγούμαστε στις εξείς σχέσεις:



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

[Μάκης Χατζόπουλος]

Όπως πάντα απολαυστική απάντηση του Γιώργου ,έχεις δίκιο Γιώργο για τον Κόκορα (κρασάτος είναι η σπεσιαλιτέ της Ζακύνθου όπως και το κουνέλι), εξού και η ακριβή ισοτιμία που έβαλα!

Αλλά εμείς οι Αθηναίοι που από ζώα! Άσε που δεν έβαλα και χέρι να δω την διαφορά!!

Αυτή είναι η μαθηματική αντιμετώπιση Χρήστο!! Πολύ καλά!!

Συνεχίζω στο επόμενο...

Πρόβλημα 2 - Λαβυρ-άριθμοι!!
Ακολουθώντας την παρακάτω διαδρομή μεταξύ των τετραγώνων, οριζόντια ή κάθετα αλλά προσοχή μην περάσετε δύο τουλάχιστον φορές από το ίδιο τετράγωνο (όπως μας καθοδηγούν τα βελάκια), προσπαθήστε να βρείτε τις διαδρομές που δίνουν άθροισμα:
α) 68
β) 94
γ) Μέγιστο άθροισμα
δ) Ελάχιστο άθροισμα

Υ.Γ: Υπάρχει και εδώ μαθηματική δικαιολόγηση

[Γιώργος Ρίζος]

Για να επαναφέρουμε το πρόβλημα που έθεσε ο Μάκης.

13 >10 > 15 > 12 > 7 >5 > 6
Σύνολο: 68

Διαδρομή με σύνολο 94 δεν βρήκα. Αν θες με ... 95 γίνεται !

Μέγιστη διαδρομή:
Περνάμε από όλα τα τετράγωνα εκτός από το 4 (κάτω αριστερά)
13 > 10 > 1 > 8 > 11 > 5 > 7 > 12 > 15 > 9 > 3 > 16 > 14 > 6 > 6
Σύνολο: 136


Ελάχιστη διαδρομή:
13 > 10 > 1 > 8 > 11> 5 > 6
Σύνολο: 54

Μια μπελαλίδικη διαδικασία θα ήταν η καταγραφή όλων των διαδρομών με έναν κανόνα:
Π.χ. κινούμαι πάντα δεξιά. Αν δεν γίνεται τότε κάτω. Αν δεν γίνεται (ή έχει ήδη καταγραφεί η διαδρομή) τότε αριστερά κι αν δεν γίνεται πάμε επάνω, καταγράφοντας έτσι όλες τις διαδρομές (περίπου όπως περιέγραφε ο Ουμπέρτο Έκο στο λαβύρινθο στο "Όνομα του Ρόδου". Με την ευκαιρία: Έχει ασχοληθεί κανείς με την καταγραφή των διαδρομών του λαβυρίνθου, που είναι σε μακέτα στο βιβλίο;).
Μάκη, δεν έχω τόση υπομονή
Υπάρχει πιο απλή μαθηματική απόδειξη για τη μέγιστη και ελάχιστη διαδρομή;

Γιώργος Ρίζος

[Μάκης Χατζόπουλος]

Για να επαναφέρουμε το πρόβλημα που έθεσε ο Μάκης.

13 >10 > 15 > 12 > 7 >5 > 6
Σύνολο: 68

Διαδρομή με σύνολο 94 δεν βρήκα. Αν θες με ... 95 γίνεται !

Υπάρχει 94, θέλει λίγο ψάξιμο... Εγώ δεν βρήκα το 95!!!

Μάκη, δεν έχω τόση υπομονή
Υπάρχει πιο απλή μαθηματική απόδειξη για τη μέγιστη και ελάχιστη διαδρομή;

Γιώργος Ρίζος

Νομίζω κάτι υπάρχει, θα πω την σκέψη μου αν δεν ενδιαφερθεί κάποιος άλλος... Πάντως θα είχε ενδιαφέρον η μελέτη του προβλήματος με Μαθηματικά δεδομένα, λίγο γραμμικό προγραμματισμό μου κάνει...

Μέγιστη διαδρομή:
Περνάμε από όλα τα τετράγωνα εκτός από το 4 (κάτω αριστερά)
13 > 10 > 1 > 8 > 11 > 5 > 7 > 12 > 15 > 9 > 3 > 16 > 14 > 6 > 6
Σύνολο: 136

Πάρα πολύ ωραία Γιώργο, κανονικά έπρεπε να περάσουμε από όλα τα τετράγωνα για να έχουμε το μέγιστο άθροισμα, αλλά αυτό δεν γίνεται, άρα πρέπει να βρούμε το ελάχιστο άθροισμα τετραγώνων που δεν μπορούμε να περάσουμε, άρα η αρχική σκέψη λέει να αφήσουμε το τετράγωνο 1, αλλά δεν είναι εφικτό, αφού η διαδρομή του είναι μοναδική και αν παρακαφθεί το άθροισμα που θα χάσουμε θα είναι μεγάλο!! Ομοίως σκεφτόμαστε και για το 3, άρα καταλήγουμε να αφήσουμε το 4 όπως πολύ όμορφα σημείωσες Γιώργο και όπερ το άθροισμα 136!!

[Demetres]

Υπάρχει πιο απλή μαθηματική απόδειξη για τη μέγιστη και ελάχιστη διαδρομή;

Για την ελάχιστη διαδρομή υπάρχει ο αλγόριθμος του Dijkstra. Υπολογίζει την ελάχιστη διαδρομή από μια κορυφή σε όλες τις υπόλοιπες κορυφές. Ο αλγόριθμος δουλεύει ως εξής:

- Κάνουμε μια λίστα με όλες τις κορυφές.
- Σε κάθε σημείο του αλγόριθμου θα έχουμε ένα σύνολο κορυφών που περιέχει την . Για όλες τις κορυφές που ανήκουν στο θα έχουμε καταγραμμένες και τις συντομότερες αποστάσεις τους από το .
- Ο αλγόριθμος ξεκινάει με .
- Σε κάθε βήμα του αλγορίθμου κάνουμε το εξής: Για κάθε κορυφή που δεν ανήκει στο , βρίσκουμε την συντομότερη απόσταση του από το μόνο μέσω των κορυφών που βρίσκονται στο . Βρίσκουμε την κορυφή έξω από το που έχει την μικρότερη τέτοια απόσταση και την προσθέτουμε στο .

Στο παράδειγμά μας συμβολίζω την πάνω αριστερά κορυφή με την δεξιά του με την από κάτω του με κ.τ.λ

Η πρώτη κορυφή που θα προσθέσουμε είναι είτε η είτε η . Η πρώτη έχει «δυνητική» απόσταση 10 και η δεύτερη 9. Προσθέτουμε στην λίστα την δεύτερη. (Μιλάω για δυνητικές αποστάσεις διότι εκτός από την κορυφή που θα προστεθεί οι αποστάσεις από τις υπόλοιπες κορυφές μπορεί να είναι πιο μικρές.) Μετά έχουμε τρεις κορυφές να ελέγξουμε. Τις και οι οποίες έχουν δυνητικές αποστάσεις και . Προσθέτουμε την πρώτη και συνεχίσουμε.

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

Υπάρχει αλγόριθμος που να τρέχει σε πολυωνυμικό χρόνο και να υπολογίζει την μέγιστη απόσταση μεταξύ δυο κορυφών σε οποιοδήποτε γράφημα;

Το πρόβλημα είναι ανοικτό. Οι περισσότεροι πιστεύουν πως η απάντηση είναι όχι. Όποιος δώσει σωστή μαθηματική απάντηση στο ερώτημα (είτε θετική είτε αρνητική) δικαιούται να ζητήσει $1000000 από το Clay Mathematics Institute μιας και θα έχει λύσει αυτό το πρόβλημα: P vs NP.

[Μάκης Χατζόπουλος]

Ελάχιστη διαδρομή:
13 > 10 > 1 > 8 > 11> 5 > 6
Σύνολο: 54

Μπράβο Γιώργο, δεν την πάτησες που περίμενα να το κάνουν όλοι!! Δηλ. να πάνε από την πρώτη στήλη και ύστερα στην τελευταία γραμμή, έτσι προκύπτει άθροισμα 55 (δηλ. ένα παραπάνω από το δικό σου)!!

Για την ελάχιστη διαδρομή υπάρχει ο αλγόριθμος του Dijkstra. Υπολογίζει την ελάχιστη διαδρομή από μια κορυφή σε όλες τις υπόλοιπες κορυφές. Ο αλγόριθμος δουλεύει ως εξής:

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

Το πρόβλημα είναι ανοικτό. Οι περισσότεροι πιστεύουν πως η απάντηση είναι όχι. Όποιος δώσει σωστή μαθηματική απάντηση στο ερώτημα (είτε θετική είτε αρνητική) δικαιούται να ζητήσει $1000000 από το Clay Mathematics Institute μιας και θα έχει λύσει αυτό το πρόβλημα: P vs NP.

Ήρθε η ώρα να λυθεί και αυτό!! Ελπίζω το κλίμα της Ζακύνθου να με βοηθήσει !!!

[Μάκης Χατζόπουλος]

Δίνω το άθροισμα 94

[manos1992]

Υπάρχει αλγόριθμος που να τρέχει σε πολυωνυμικό χρόνο και να υπολογίζει την μέγιστη απόσταση μεταξύ δυο κορυφών σε οποιοδήποτε γράφημα;

Κύριε Δημήτρη καλημέρα! λογικά κάτι δεν καταλαβαίνω σωστά ή αυτά που λέω ισχύουν σε κάποια μόνο γραφήματα...ο αλγόριθμος Bellman Ford που υπολογίζει ελάχιστη αποστάση με αρνητικά βάρη αν πολλαπλασιαστεί επι -1 δε δείνει μέγιστο;;
Ο Bellman Ford τρέχει με όπου V o αριθμός των κορυφών και E o αριθμός των ακμών

[Demetres]

Υπάρχει αλγόριθμος που να τρέχει σε πολυωνυμικό χρόνο και να υπολογίζει την μέγιστη απόσταση μεταξύ δυο κορυφών σε οποιοδήποτε γράφημα;

Κύριε Δημήτρη καλημέρα! λογικά κάτι δεν καταλαβαίνω σωστά ή αυτά που λέω ισχύουν σε κάποια μόνο γραφήματα...ο αλγόριθμος Bellman Ford που υπολογίζει ελάχιστη αποστάση με αρνητικά βάρη αν πολλαπλασιαστεί επι -1 δε δείνει μέγιστο;;
Ο Bellman Ford τρέχει με όπου V o αριθμός των κορυφών και E o αριθμός των ακμών

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

Στην περίπτωση που μας ενδιαφέρει (μέγιστη διαδρομή, όλες οι τιμές θετικές <-> ελάχιστη διαδρομή, όλες οι τιμές αρνητικές) ο αλγόριθμός θα βρει την διαδρομή αν και μόνο αν το γράφημα δεν έχει κύκλους. (Κάτι απλό αφού υπάρχει το πολύ μια διαδρομή μεταξύ δυο κορυφών!)

[manos1992]

Τώρα που το ξαναβλέπω έχεις απόλυτο δίκιο! Έχοντας υπ όψιν μου μόνο τον Dijkstra, συζήτησα με ένα φίλο μου ξέρει πολύ καλό προγραμματισμό και μου είπε να κοιτάξω αν δουλεύει ο Bellman Ford...Δεν τον βρήκα ούτε εγώ σε βιβλιογραφία οπότε το googlαρα μου βγαλε wikipedia και κατάλαβα ότι να ναι αφού κι εγώ έκανα ώρα να καταλάβω...Κακογραμμένο άρθρο όσο δεν πάει...Συμπεραίνουμε αποτυχία!