Η συνδυαστική, το κακό πνεύμα , οι αριθμοί Ράμσεϊ και τα surprise πάρτι..

Mια ανάρτηση για τους αριθμούς Ράμσεϊ ,τα πάρτι και τους εξωγήινους.

  Παλιότερα είχα ανεβάσει ένα προβληματάκι  συνδυαστικής με μια heavy metal μπάντα  και την αμοιβαιότητα ή μη γνωριμίας (http://mathhmagic.blogspot.gr/2015/08/blog-post.html). Ουσιαστικά ήταν μια παραλλαγή  του κλασσικού προβλήματος συνδυαστικής, του προβλήματος του Ράμσεϊ.                     

 Ας υποθέσουμε ότι γίνεται μια κοσμική συγκέντρωση,ένα πάρτι,το ερώτημα που τίθεται είναι:

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

Η απάντηση είναι 6 άτομα.

Πως το προσεγγίζουμε; Είτε με την βοήθεια της περιστεροφωλιάς  (http://mathhmagic.blogspot.gr/2014/04/blog-post_16.html)  είτε με την βοήθεια γράφων.

   

   •Θέτουμε ως προϋπόθεση ότι υπάρχει αμοιβαιότητα γνωριμίας  ανάμεσα στους προσκεκλημένους δηλαδή αν ο Γιώργος γνωρίζει τον Γιάννη,τότε και ο Γιάννης γνωρίζει τον Γιώργο.Έχοντας αυτή την προϋπόθεση,ας εξετάσουμε μια πιο τετριμμένη περίπτωση,ένα πάρτι έξι ατόμων.Ας ονομάσουμε έναν από τους προσκεκλημένους Δημήτρη. Ο Δημήτρης θα πρέπει να γνωρίζει τουλάχιστον τρεις από αυτούς  ή να μην γνωρίζει τρεις  από αυτούς,ας υποθέσουμε ότι γνωρίζει τρεις από τους προσκεκλημένους. Ας αναλύσουμε τώρα ποια σχέση έχουν μεταξύ τους τα τρία άτομα που γνωρίζει ο Δημήτρης.

 Εάν οποιοιδήποτε δυο από αυτούς έχουν γνωριμία μεταξύ τους, αυτοί και  ο Δημήτρης  σχηματίζουν μια ομάδα τριών ατόμων που γνωρίζονται μεταξύ τους και,επομένως,φτάσαμε στο ζητούμενο.

Αν αντίθετα και οι τρεις είναι άγνωστοι μεταξύ τους πάλι ικανοποιείται η συνθήκη του προβλήματος  άρα σε κάθε περίπτωση  σε ένα πάρτι 6 ατόμων  ικανοποιεί τις συνθήκες του προβλήματος.

•Η άλλη  προσέγγιση όμως του προβλήματος  γίνεται με την βοήθεια γραφήματος.

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

Πριν χρωματιστεί το σχήμα έχει την μορφή:

 

Παρατηρούμε ότι κάθε κορυφή του σχήματος έχει πέντε συνδέσμους(5 γείτονες ).Ας επικεντρωθούμε όμως στην κορυφή Α

  Κάθε ένας από τους 5 γείτονες του Α θα είναι είτε γνωστός (μπλε) είτε παντελώς άγνωστος (κόκκινο) με τον Α. Υπάρχουν 5 γείτονες,τουλάχιστον τρεις από αυτούς θα είναι γνωστοί ή τουλάχιστον τρεις θα είναι παντελώς άγνωστοι.

Ας δούμε την περίπτωση που υπάρχουν 3 τουλάχιστον μπλε σύνδεσμοι (ακμές). 

Οι κορυφές Β,C και D  θα συνδεθούν από τρεις συνδέσμους ο καθένας από τους οποίους θα είναι είτε μπλε είτε κόκκινος.Θα δείξουμε ότι  τουλάχιστον ένα από τα τρίγωνα που σχηματίζονται  είναι ιδίου χρώματος.Πρέπει να λάβουμε υπ όψιν μας μόνο τις παρακάτω περιπτώσεις  των χρωμάτων των συνδέσμων που συνδέουν τις κορυφές B,C,D.

Οι περιπτώσεις χωρίς τις συμμετρίες είναι:

i. 2 μπλε,1 κόκκινη
ii. 2 κόκκινες ,1 μπλε
iii. 3  κόκκινες

 

  Παρατηρούμε  ότι αν κάποια από  τις ακμές που συνδέουν τις κορυφές B,C,D  είναι μπλε, ένα μπλε τρίγωνο σχηματίζεται, πράγμα που σημαίνει ότι οι τρεις  προσκεκλημένοι είναι αμοιβαία γνωστοί. Αντίστροφα ένα τρίγωνο κόκκινου χρώματος θα σηματοδοτεί μια τριάδα προσκεκλημένων παντελώς άγνωστων.Σε κάθε μια από τις παραπάνω περιπτώσεις έχουμε την δημιουργία είτε ενός μπλε είτε ενός κόκκινου τρίγωνου,ίδιο αποτέλεσμα θα είχαμε αν είχαμε βάλει τις ακμές AB,AC,AD αρχικά κόκκινες αντί για μπλε.

Tο πρόβλημα γενικεύεται ως εξής:

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

Οι αριθμοί που αποτελούν απαντήσεις στο παραπάνω πρόβλημα ονομάζονται αριθμοί Ράμσεϊ  και  συμβολίζονται R(μ,κ)=ν

Φρ. Πλ. Ράμσεϊ (1903-1930)

  Ο  Φρανκ Πλάμπτον Ράμσεϊ (1903-1930) υπήρξε καθολική ευφυΐα,γεννήθηκε το 1903 στο Κέιμπριτζ στην Αγγλία,χαρισματικό παιδί τέλειωσε το σχολείο του Γουίντσεστερ και γράφτηκε στο θρυλικό Τρίνιτυ Kολετζ  του Κέιμπριτζ.Διέπρεψε στα μαθηματικά,αλλά υπήρξε ένας  αεικίνητος και απόλυτα αναλυτικός νους καθώς πριν ακόμα κλείσει τα δεκαέξι, οι οικονομολόγοι  του Κέιμπριτζ  τον εμπιστεύονταν να ελέγξει τις θεωρίες τους.Ο γνωστός οικονομολόγος Μέυναρντ Κέυνς έγραφε για τον νεαρό Ράμσεϊ:

«..χειριζόταν τον τεχνικό εξοπλισμό της επιστήμης μας με την ευκολία κάποιου που ήταν συνηθισμένος σε κάτι πιο δύσκολο…». Γατάκια  οικονομολόγοι!! 

   O  θρυλικός Πωλ Έρντος συχνά διηγούνταν μια ιστορία σχετική με το πρόβλημα.Αν έχουμε μια ανώτερη  εξωγήινη δύναμη-ένα κακό πνεύμα- που φτάνει στην γη και θέτει στην ανθρωπότητα ένα ερώτημα ,αν δοθεί λάθος απάντηση  θα κατάστρεφε τον πλανήτη. Ας υποθέσουμε, επιχειρηματολογεί ο Ερντος,ότι οι εξωγήινοι αποφασίζουν  να  θέσουν ως ερώτημα το πρόβλημα του Ράμσεϊ με το πάρτι,θέτοντας ως προϋπόθεση το να γνωρίζονται ή να μην γνωρίζονται μεταξύ τους 5 άτομα.Η καλύτερη τακτική,σύμφωνα με τον Ούγγρο μαθηματικό, θα ήταν να συγκεντρώσουμε όλους τους μαθηματικούς του κόσμου, να τους ζητήσουμε να αφήσουν στην άκρη ότι κάνουν και με απλούς υπολογισμούς, να  απαριθμήσουν όλα τα δυνατά ενδεχόμενα είναι  2¹¹²⁸ ,ένα εξωφρενικό νούμερο. Σήμερα εικάζουμε ότι ο αριθμός  που αναζητούμε είναι  ανάμεσα στο 43 και στο 49 και αυτή είναι η καλύτερη προσέγγιση που έχουμε. Όμως,αν το κακό πνεύμα   έθετε το ίδιο πρόβλημα για 6 άτομα, ο Έρντος ισχυριζόταν  ότι  η καλύτερη μέθοδος θα ήταν να  του επιτεθούμε εμείς πρώτοι προτού μας  επιτεθεί εκείνο, ο συνδυασμός πιθανοτήτων θα ήταν υπερβολικά μεγάλος, ακόμη και για τους πιο ισχυρούς υπολογιστές, το πιο περίπλοκο πρόβλημα του πάρτι του Ράμσεϊ που μέχρι σήμερα έχει λυθεί, με την βοήθεια 100 υπολογιστών που λειτουργούσαν ταυτόχρονα-είναι το πρόβλημα του ελάχιστου αριθμού των προσκεκλημένων που χρειάζονται για να υπάρχουν τουλάχιστον 4 άτομα που γνωρίζονται μεταξύ τους ή 5 που δεν γνωρίζονται μεταξύ τους.

Η λύση βρέθηκε το 1995 και το αποτέλεσμα είναι 25.

 Δείτε και ένα εύληπτο cartoon video

 

                       

Από....surprise πάρτι κάτι ξέρει η Μήτση Κωνσταντάρα :) :)