13 ιππότες κάθονται γύρω από ένα στρογγυλό τραπέζι.
Κάθε ιππότης είναι εχθρός με τους γείτονές του και φίλος με όλους τους άλλους.
Η πριγκίπισσα θέλει να επιλέξει ανάμεσά τους μια ομάδα 5 ιπποτών που να είναι όλοι φίλοι μεταξύ τους, για να την προστατεύουν. Πόσες τέτοιες ομάδες υπάρχουν;
Θέλουμε οι πεντάδες που θα σχηματιστούν να μην περιέχουν γείτονες. Ο τύπος που δίνει τους τρόπους που μπορούν να επιλεγούν κ στοιχεία από ένα σύνολο ν στοιχείων έτσι ώστε να μην υπάρχουν γειτονικές επιλογές είναι ο C(ν-κ+1, κ). Στην περίπτωσή μας έχουμε ν=13 και κ=5, οπότε C(ν-κ+1, κ)=126. Επειδή όμως οι ιππότες βρίσκονται σε κύκλο και εγώ τους υπολόγισα σαν να βρίσκονταν στη σειρά, από τους συνδυασμούς που υπολογίσαμε πρέπει να αφαιρέσουμε αυτούς που έχουν ιππότες στα άκρα, δηλαδή στις θέσεις 1 και 13. Με τον ίδιο τύπο, αυτοί οι συνδυασμοί είναι C(7,3)=35. Οπότε συνολικά έχουμε 126-35 = 91 ομάδες.
Μας αρκεί να δούμε πόσες δυνατές πεντάδες υπάρχουν με τη συμμετοχή ενός συγκεκριμενου ιππότη, για παράδειγμα του ιππότη νούμερο 1. Αυτές είναι συνολικά 35. Αυτό σημαίνει ότι συνολικά για όλους τους ιππότες οι πιθανές ομάδες είναι 35*13=455. Εδώ όμως πρέπει να προσέξουμε ότι ο κάθε συνδυασμός έχει αναφερθεί πεντε φορές ! Συνεπώς 455/5=91.
Σε αυτόν τον αριθμό υπάρχουν οι συνδυασμοί που εμπεριέχουν τον ιππότη 35 και αυτοί χωρίς τη συμμετοχή του δηλαδή 56. (56+35=91)
Συνδυασμοί των 11 ανά 5 = 462
Εδω το κλειδι ειναι να μετρησουμε τον αριθμο των συνδυασμων με βάση τα κενα μεταξύ των ιπποτων που για ένα πιθανό συνδυασμό
(5-άδες)
Το μάξιμουμ των αποστάσεων μεταξύ 2 φίλων μιας πιθανής 5 άδας είναι 4
Οι δυνατές θέσεις αυτης της 4-άδας κενών είναι 13
Επίσης μπορούμε να έχουμε 3 κενά μεταξύ 2 φίλων της 5 άδας και άλλοι 2 να απέχουν 2 θέσεις
Οι πιθανές θέσεις αυτής της2 άδας είναι 4 και έχουμε συνολικά 13 στροφές δεξιόστροφα όλης της διάταξης άρα 13*4=52
Τελος μπορεί να έχουμε 3 ζεύγη κενών μεταξύ φίλων και να απομένουν 2 κενά με απόσταση 1
Εδω έχουμε ειτε 3 συνεχόμενα ζεύγη κενων είτε 2+1 .Και στις 2 περιπτώσεις έχουμε 13 θέσεις αν κινηθούμε δεξιόστροφα στον κύκλο αρα 2*13=26
==2
Οπότε συνολικα η συνδυασμοί -ομάδες 5 αδων είναι 13+52+26=91
Η απάντηση είναι 91 και πολλά μπράβο στους φίλους για τις λύσεις τους!
Δίνω μία ακόμα:
Διαλέγουμε για ‘πρώτο’ της 5άδας έναν οποιονδήποτε ιππότη (13 επιλογές). Τώρα, αποκλείοντας τους 2 διπλανούς του ‘πρώτου’, μένει πλέον να διαλέξουμε άλλους 4 μεταξύ 10 διαθέσιμων ιπποτών σε σειρά, με τον περιορισμό να μην υπάρχει ζευγάρι γειτόνων στους 4 που θα επιλεγούν. Αν {1,2,..,10} οι 10 ιππότες σε σειρά και α,β,γ,δ οι 4 που επιλέγονται μεταξύ αυτών, κατά αύξουσα σειρά, τότε η επιλογή των α,β,γ αποκλείει αντίστοιχα τους ιππότες α+1, β+1, γ+1 και έτσι ουσιαστικά επιλέγουμε 4 από 10-3=7, πράγμα που μπορεί να γίνει με C(7,4)=35 τρόπους. Έτσι έχουμε καταρχάς 13*35=455 συνδυασμένους τρόπους, αλλά καθένας από αυτούς έχει μετρηθεί 5 φορές (μία για κάθε ιππότη μιας πεντάδας που έχουμε διαλέξει για ‘πρώτο’), άρα τελικά υπάρχουν 455/5=91 ομάδες των 5 φίλων.