1. Καθένας από τους 41 ισοβίτες κρατούμενους μιας φυλακής είναι διαζευκτικά φίλος ή εχθρός με οποιονδήποτε άλλον. Μια μέρα, ο διευθυντής της φυλακής τούς ζήτησε να φτιάξουν ο καθένας από ένα κομπολόι με τις ελάχιστες χρωματιστές χάντρες που χρειάζονται συνολικά, έτσι ώστε για κάθε ζευγάρι φίλων να υπάρχει στα κομπολόγια τους χάντρα του ιδίου χρώματος και για κάθε ζευγάρι εχθρών να μην υπάρχει. Τα υλικά για την κατασκευή των κομπολογιών, σε επαρκείς ποσότητες και χρώματα, παρέχονται από τη φυλακή και εφόσον οι κρατούμενοι καταφέρουν το ζητούμενο, οι ποινές τους θα μετατραπούν από ισόβια σε φυλάκιση λίγων μηνών. Τι λέτε μπορούν να τα καταφέρουν και, αν ναι, πώς; Πόσα το πολύ χρώματα θα ήταν απαραίτητα για αυτό το σκοπό; Αιτιολογήστε.
2. Σε μια φυλακή με περισσότερους από 100 και λιγότερους από 200 κρατούμενους, κάθε κρατούμενος έχει διαζευκτικά φιλία ή έχθρα με κάθε άλλον. Στη φυλακή αυτή, ο φίλος του φίλου είναι φίλος, ο εχθρός του εχθρού είναι φίλος και οι φιλίες είναι όσες και οι έχθρες. Ποιος είναι ο ελάχιστος και ποιος ο μέγιστος δυνατός αριθμός κρατουμένων;
2.
Κατ’αρχήν θα δείξουμε ότι οι κρατούμενοι χωρίζονται σε δύο ομάδες Α και Β, όπου κάθε μέλος κάθε ομάδας, είναι φίλος με όλα τα μέλη της ίδιας ομάδας και εχθρός με όλα τα μέλη της άλλης ομάδας.
Προς τούτο, ας θεωρήσουμε τον πρώτο κρατούμενο Κ1 που τον τοποθετούμε έστω στην ομάδα Α. Κάθε επόμενο κρατούμενο, εάν είναι φίλος του, τον τοποθετούμε στην ομάδα Α, ενώ αν είναι εχθρός του, τον τοποθετούμε στην ομάδα Β. Επειδή ο φίλος φίλου είναι και αυτός φίλος, με το τρόπο αυτό όλοι οι κρατούμενοι της ομάδας Α είναι φίλοι μεταξύ τους. Επίσης όλοι οι κρατούμενοι της ομάδας Β είναι φίλοι μεταξύ τους γιατί έχουν ως κοινούς εχθρούς τους κρατούμενους της ομάδας Α.
Επομένως αν Κ ο συνολικός αριθμός των κρατουμένων, έστω Ν και (Κ-Ν) ο αριθμός των κρατουμένων σε κάθε μία από τις δύο ομάδες.
Οι συνολικές σχέσεις (φιλίες+έχθρες) είναι Κ*(Κ-1)/2. Οι συνολικές εχθρικές σχέσεις είναι Ν*(Κ-Ν). Επομένως:
Κ*(Κ-1)/2=2*Ν*(Κ-Ν), από όπου επιλύοντας ως προς Ν, προκύπτει:
Ν=(Κ+Κ^1/2)/2, είτε Ν= (Κ-Κ^1/2)/2.
Αρα ο Κ πρέπει να είναι τέλειο τετράγωνο. Επομένως ο ελάχιστος αριθμός κρατουμένων είναι 121 (με δύο ομάδες των 66 και 55 ατόμων), και ο μέγιστος αριθμός 196 (με δύο ομάδες των 105 και 91 ατόμων)
ΚΣ
Πρόβλημα 2.
Παρατηρούμε ότι σε μια οποιαδήποτε τριάδα φυλακισμένων είτε θα είναι και οι 3 φίλοι μεταξύ τους είτε θα υπάρχουν 2 εχθρικές σχέσεις και μια φιλική. Σε οποιαδήποτε άλλη περίπτωση καταστρατηγούνται οι κανόνες που έχουν τεθεί.
Για να ισχύουν οι κανόνες της φυλακής θα πρέπει να έχουν συγκροτηθεί δύο ομάδες φυλακισμένων των οποίων τα μέλη είναι φίλοι μεταξύ τους αλλά είναι εχθροί με τα μέλη της άλλης ομάδας.
Εστω α το πλήθος των μελών της ομάδας Α και β το πλήθος της ομάδας Β.
Εφόσον οι έχθρες είναι όσες και οι φιλίες θα ισχύει
α!/(α-2)!*2 +β!/(β-2)=α*β , με α+β μικρότερο από 200 και μεγαλύτερο από 100 Ο ελάχιστος αριθμός εντοπίζεται στο 121 με α=55 και β=66 ο μέγιστος στο 196 με α=91 και β=105
Πρόβλημα1
Κατασκευή κομπολογιού=> Αν δώσουμε από ένα χρώμα σε κάθε μια φιλική σχέση μεταξύ 2 φυλακισμένων τότε μπορούν οι φυλακισμένοι να κατασκευάσουν τα κομπολόγια που ζητάμε. Για παράδειγμα έχουμε 3 φυλακισμένους, όπου
1-2 είναι φίλοι => χρώμα Χ1
2-3 είναι φίλοι => χρώμα Χ2
1-3 είναι εχθροί
Τότε 1=> Χ1, 2=>Χ1Χ2, 3=>Χ2
Παρατηρούμε ότι μπορούμε να μεγιστοποιησουμε τα ελάχιστα χρώματα εφόσον δεν υπάρχουν 3 ή παραπάνω φιλακισμένοι που είναι φίλοι μεταξύ τους, αφού το χρώμα της κάθε αμοιβαίας φιλίας μπορεί να αντικατασταθεί με ένα κοινό χρώμα. Για παράδειγμα αν υπάρχουν τριεις κοινοί φίλοι τότε τα χρώματα που αντιπροσωπεύουν τις 3 φιλικές σχέσεις μπορούν να αντικατασταθούν με 1 χρώμα.
Αριθμούμε τους φυλακισμένους 1-41 και τους χωρίζουμε σε 3 ομάδες Α,Β,Γ
όπου η Α= 1, η Β =2-21 και γ=22-41 όπου τα μέλη της κάθε ομάδες ΔΕΝ είναι φίλοι μεταξύ τους μπορούμε να έχουμε την εξής κατάσταση
ο 1 είναι φίλος με τους 20 της ομάδας Β αλλά εχθρός με τους Γ,
οι Β φίλοι με τα μέλη της ομάδας Γ
Με βάση αυτή τη διάταξη δεν υπάρχουν 3 ή παραπάνω που να είναι φίλοι μεταξύ τους.
Συνολικά τα χρώματα που θα χρειαστούν είναι
20+20*20=420 χρώματα
Θανάσης Παπαδημητρίου
Συγχαίρω κι ευχαριστώ θερμά για μια φορά ακόμα τους φίλους Κωστή και Στράτο για τις πληρέστατες, εξαιρετικές και κομψεπίκομψες λύσεις τους!!
Εκ περισσού, δύο λόγια ακόμα:
1. Στην περίπτωση του μέγιστου των χρωμάτων, έχοντας αποκλείσει την ύπαρξη ομάδων 3 ή περισσότερων αμοιβαία φίλων, μπορούμε να χωρίσουμε τους 41 κρατούμενους σε δύο ομάδες, με τρόπο ώστε καθένας που βρίσκεται σε μία ομάδα να έχει στην άλλη ομάδα όλους του τους φίλους και στην ίδια ομάδα όλους του τους εχθρούς. Αν λοιπόν στη μία ομάδα έχουμε κ κρατούμενους (0≤κ≤41), στην άλλη θα έχουμε 41-κ κρατούμενους και σχηματίζονται συνολικά κ(41-κ) ζευγάρια φίλων – χρώματα. Το γινόμενο αυτό μεγιστοποιείται για κ=20 ή 21, οπότε και γίνεται 20*21=420.
2. Αν οι κρατούμενοι είναι ν στο πλήθος και οι δύο ομάδες αμοιβαία φίλων έχουν χ και ψ μέλη αντιστοίχως, τότε η ισότητα φιλιών με έχθρες δίνει:
χ(χ-1)/2+ψ(ψ-1)/2 = χψ =>
χ^2-χ+ψ^2-ψ = 2χψ =>
χ^2+ψ^2-2χψ = χ+ψ = ν =>
ν = (χ-ψ)^2, τ.τ.
2.
Κατ’αρχήν θα δείξουμε ότι οι κρατούμενοι χωρίζονται σε δύο ομάδες Α και Β, όπου κάθε μέλος κάθε ομάδας, είναι φίλος με όλα τα μέλη της ίδιας ομάδας και εχθρός με όλα τα μέλη της άλλης ομάδας.
Προς τούτο, ας θεωρήσουμε τον πρώτο κρατούμενο Κ1 που τον τοποθετούμε έστω στην ομάδα Α. Κάθε επόμενο κρατούμενο, εάν είναι φίλος του, τον τοποθετούμε στην ομάδα Α, ενώ αν είναι εχθρός του, τον τοποθετούμε στην ομάδα Β. Επειδή ο φίλος φίλου είναι και αυτός φίλος, με το τρόπο αυτό όλοι οι κρατούμενοι της ομάδας Α είναι φίλοι μεταξύ τους. Επίσης όλοι οι κρατούμενοι της ομάδας Β είναι φίλοι μεταξύ τους γιατί έχουν ως κοινούς εχθρούς τους κρατούμενους της ομάδας Α.
Επομένως αν Κ ο συνολικός αριθμός των κρατουμένων, έστω Ν και (Κ-Ν) ο αριθμός των κρατουμένων σε κάθε μία από τις δύο ομάδες.
Οι συνολικές σχέσεις (φιλίες+έχθρες) είναι Κ*(Κ-1)/2. Οι συνολικές εχθρικές σχέσεις είναι Ν*(Κ-Ν). Επομένως:
Κ*(Κ-1)/2=2*Ν*(Κ-Ν), από όπου επιλύοντας ως προς Ν, προκύπτει:
Ν=(Κ+Κ^1/2)/2, είτε Ν= (Κ-Κ^1/2)/2.
Αρα ο Κ πρέπει να είναι τέλειο τετράγωνο. Επομένως ο ελάχιστος αριθμός κρατουμένων είναι 121 (με δύο ομάδες των 66 και 55 ατόμων), και ο μέγιστος αριθμός 196 (με δύο ομάδες των 105 και 91 ατόμων)
Πρόβλημα 2.
Παρατηρούμε ότι σε μια οποιαδήποτε τριάδα φυλακισμένων είτε θα είναι και οι 3 φίλοι μεταξύ τους είτε θα υπάρχουν 2 εχθρικές σχέσεις και μια φιλική. Σε οποιαδήποτε άλλη περίπτωση καταστρατηγούνται οι κανόνες που έχουν τεθεί.
Για να ισχύουν οι κανόνες της φυλακής θα πρέπει να έχουν συγκροτηθεί δύο ομάδες φυλακισμένων των οποίων τα μέλη είναι φίλοι μεταξύ τους αλλά είναι εχθροί με τα μέλη της άλλης ομάδας.
Εστω α το πλήθος των μελών της ομάδας Α και β το πλήθος της ομάδας Β.
Εφόσον οι έχθρες είναι όσες και οι φιλίες θα ισχύει
α!/(α-2)!*2 +β!/(β-2)=α*β , με α+β μικρότερο από 200 και μεγαλύτερο από 100 Ο ελάχιστος αριθμός εντοπίζεται στο 121 με α=55 και β=66 ο μέγιστος στο 196 με α=91 και β=105
Πρόβλημα1
Κατασκευή κομπολογιού=> Αν δώσουμε από ένα χρώμα σε κάθε μια φιλική σχέση μεταξύ 2 φυλακισμένων τότε μπορούν οι φυλακισμένοι να κατασκευάσουν τα κομπολόγια που ζητάμε. Για παράδειγμα έχουμε 3 φυλακισμένους, όπου
1-2 είναι φίλοι => χρώμα Χ1
2-3 είναι φίλοι => χρώμα Χ2
1-3 είναι εχθροί
Τότε 1=> Χ1, 2=>Χ1Χ2, 3=>Χ2
Παρατηρούμε ότι μπορούμε να μεγιστοποιησουμε τα ελάχιστα χρώματα εφόσον δεν υπάρχουν 3 ή παραπάνω φιλακισμένοι που είναι φίλοι μεταξύ τους, αφού το χρώμα της κάθε αμοιβαίας φιλίας μπορεί να αντικατασταθεί με ένα κοινό χρώμα. Για παράδειγμα αν υπάρχουν τριεις κοινοί φίλοι τότε τα χρώματα που αντιπροσωπεύουν τις 3 φιλικές σχέσεις μπορούν να αντικατασταθούν με 1 χρώμα.
Αριθμούμε τους φυλακισμένους 1-41 και τους χωρίζουμε σε 3 ομάδες Α,Β,Γ
όπου η Α= 1, η Β =2-21 και γ=22-41 όπου τα μέλη της κάθε ομάδες ΔΕΝ είναι φίλοι μεταξύ τους μπορούμε να έχουμε την εξής κατάσταση
ο 1 είναι φίλος με τους 20 της ομάδας Β αλλά εχθρός με τους Γ,
οι Β φίλοι με τα μέλη της ομάδας Γ
Με βάση αυτή τη διάταξη δεν υπάρχουν 3 ή παραπάνω που να είναι φίλοι μεταξύ τους.
Συνολικά τα χρώματα που θα χρειαστούν είναι
20+20*20=420 χρώματα
Συγχαίρω κι ευχαριστώ θερμά για μια φορά ακόμα τους φίλους Κωστή και Στράτο για τις πληρέστατες, εξαιρετικές και κομψεπίκομψες λύσεις τους!!
Εκ περισσού, δύο λόγια ακόμα:
1. Στην περίπτωση του μέγιστου των χρωμάτων, έχοντας αποκλείσει την ύπαρξη ομάδων 3 ή περισσότερων αμοιβαία φίλων, μπορούμε να χωρίσουμε τους 41 κρατούμενους σε δύο ομάδες, με τρόπο ώστε καθένας που βρίσκεται σε μία ομάδα να έχει στην άλλη ομάδα όλους του τους φίλους και στην ίδια ομάδα όλους του τους εχθρούς. Αν λοιπόν στη μία ομάδα έχουμε κ κρατούμενους (0≤κ≤41), στην άλλη θα έχουμε 41-κ κρατούμενους και σχηματίζονται συνολικά κ(41-κ) ζευγάρια φίλων – χρώματα. Το γινόμενο αυτό μεγιστοποιείται για κ=20 ή 21, οπότε και γίνεται 20*21=420.
2. Αν οι κρατούμενοι είναι ν στο πλήθος και οι δύο ομάδες αμοιβαία φίλων έχουν χ και ψ μέλη αντιστοίχως, τότε η ισότητα φιλιών με έχθρες δίνει:
χ(χ-1)/2+ψ(ψ-1)/2 = χψ =>
χ^2-χ+ψ^2-ψ = 2χψ =>
χ^2+ψ^2-2χψ = χ+ψ = ν =>
ν = (χ-ψ)^2, τ.τ.