Χριστός Ανέστη, Χρόνια πολλά με υγεία στους συντελεστές του ιστολογίου, τους φίλους λύτες και σε όλο τον κόσμο!
1. Σε ένα πασχαλινό τραπέζι παρευρέθηκαν 45 άτομα και καθένα από αυτά τσούγκρισε αβγό μία το πολύ φορά με κάθε άλλο. Κάθε άτομο κατέγραψε τα τσουγκρίσματα που έκανε και προέκυψε ότι όσα άτομα έκαναν ίσο αριθμό τσουγκρισμάτων δεν τσούγκρισαν αβγά μεταξύ τους. Πόσα το πολύ τσουγκρίσματα έγιναν συνολικά;
2. Σε ένα άλλο πασχαλινό τραπέζι παρευρέθηκαν επίσης 45 άτομα. Προέκυψε ότι σε οποιαδήποτε τετράδα αυτών των ατόμων, υπήρξε άτομο που τσούγκρισε αβγά και με τα τρία άλλα άτομα. Πόσα τουλάχιστον από τα 45 άτομα του τραπεζιού τσούγκρισαν αβγά και με τα 44 άλλα άτομα;
1. Ο μέγιστος αριθμός τσουγκρισμάτων επιτυγχάνεται αν ο 1ος τσούγκρισε με τους 2-45 (44 τσουγκρίσματα), ο 2ος και ο 3ος επιπλέον με τους 4-45 (43 τσουγκρίσματα), ο 4ος, ο 5ος και ο 6ος επιπλέον με τους 7-45 (42 τσουγκρίσματα) κ.ο.κ. μέχρι τους 37 έως 45 που δεν τσούγκρισαν με κανέναν επιπλέον. Συνολικά μπορεί να τσουγκρίστηκαν μέχρι Σ(ν=1 έως 9) ν*(45-ν) = 1740 αυγά και να έγιναν μέχρι 1740/2 = 870 τσουγκρίσματα.
2. Εάν ο Α δεν έχει τσουγκρίσει με τον Β και ο Γ δεν έχει τσουγκρίσει με τον Δ τότε στην τετράδα (Α,Β,Γ,Δ) δεν υπάρχει κάποιος που έχει τσουγκρίσει με όλους τους άλλους. Επίσης εάν ο Α δεν έχει τσουγκρίσει με τους Β,Γ,Δ τότε πάλι στην τετράδα (Α,Β,Γ,Δ) δεν υπάρχει κάποιος που έχει τσουγκρίσει με όλους τους άλλους. Οπότε για να ισχύει πως σε κάθε τετράδα υπάρχει κάποιος που έχει τσουγκρίσει με όλους, μπορούν να μην έχουν γίνει το πολύ δύο τσουγκρίσματα, π.χ. του Α με τον Β και του Α με τον Γ. Άρα ο ελάχιστος αριθμός ατόμων που τσούγκρισαν με 44 άτομα είναι 42.
ΚΣ
Πρόβλημα 2
Μας αρκούν 42 ομοτράπεζοι για πετύχουμε το ζητούμενο. Σε περίπτωση που έχουμε 41 το ζητούμενο υπάρχει η περίπτωση να μη πραγματοποιηθεί . Ας σκεφτούμε την περίπτωση όπου ότι οι 4 δεν τσούγκρισαν αβγά μεταξύ τους , αλλά μόνο με τους υπόλοιπους.
Θανάσης Παπαδημητρίου
Ας παρατείνουμε τη δημοσίευση σχολίων / λύσεων μέχρι την Κυριακή 5/5/19 για τους φίλους που ήθελαν και δεν πρόλαβαν να ασχοληθούν..
Θανάσης Παπαδημητρίου
Άψογος ο Πάνος και στα δύο, ολόσωστος κι ο Κωστής στο 2 !!
Θα δώσω μόνο μια απλή αιτιολόγηση στο 1:
Υπολογίζουμε το μέγιστο αριθμό τσουγκρισμάτων που θα μπορούσε να έχουν γίνει αν αγνοούσαμε τον περιορισμό και αφαιρούμε από αυτόν τον ελάχιστο αριθμό τσουγκρισμάτων που πρέπει να ΜΗΝ έχουν γίνει για να ικανοποιείται ο περιορισμός. Αν μια ομάδα περιέχει όλα τα χ στο πλήθος άτομα που έχουν ίσο αριθμό τσουγκρισμάτων, τότε εξ ορισμού κανένα ζευγάρι από αυτά τα χ άτομα δεν έχουν τσουγκρίσει αβγά μεταξύ τους. Αρκεί επομένως όλα αυτά τα μη γενόμενα τσουγκρίσματα, που είναι ΣC(χ,2) στο πλήθος, για όλες τις δυνατές τιμές χ, να είναι τα μόνα που λείπουν. Ο αριθμός χ μπορεί να πάρει διαδοχικά:
τιμή 1 για 1 άτομο με C(1,2)=0,
τιμή 2 για 2 άτομα με C(2,2)=1,
………………….
τιμή 8 για 8 άτομα με C(8,2)=28
τιμή 9 για 9 άτομα με C(9,2)=36
Έτσι καλύπτεται το σύνολο των 1+2+3+4+5+6+7+8+9 = 45 ατόμων με ταυτόχρονη ελαχιστοποίηση των μη γενομένων τσουγκρισμάτων, άρα ο αριθμός των τσουγκρισμάτων που έγιναν δεν μπορεί να είναι μεγαλύτερος από:
C(45,2)-C(2,2)-C(3,2)-C(4,2)-C(5,2)-C(6,2)-C(7,2)-C(8,2)-C(9,2) = 990-1-3-6-10-15-21-28-36 = 990-120 = 870
Ο αριθμός αυτός είναι εφικτός ως εξής:
Αριθμούμε τα άτομα από 1 έως 45.
Ο 1 τσουγκρίζει με όλους τους άλλους.
Οι 2,3 όχι μεταξύτους και ναι με όλους τους υπόλοιπους.
Οι 4,5,6 όχι μεταξύ τους και ναι με όλους τους υπόλοιπους.
Οι 7,8,9,10 όχι μεταξύ τους και ναι με όλους τους υπόλοιπους.
………………..
Οι 37,38,39,40,41,42,43,44,45 όχι μεταξύ τους και ναι με όλους τους υπόλοιπους.
1. Ο μέγιστος αριθμός τσουγκρισμάτων επιτυγχάνεται αν ο 1ος τσούγκρισε με τους 2-45 (44 τσουγκρίσματα), ο 2ος και ο 3ος επιπλέον με τους 4-45 (43 τσουγκρίσματα), ο 4ος, ο 5ος και ο 6ος επιπλέον με τους 7-45 (42 τσουγκρίσματα) κ.ο.κ. μέχρι τους 37 έως 45 που δεν τσούγκρισαν με κανέναν επιπλέον. Συνολικά μπορεί να τσουγκρίστηκαν μέχρι Σ(ν=1 έως 9) ν*(45-ν) = 1740 αυγά και να έγιναν μέχρι 1740/2 = 870 τσουγκρίσματα.
2. Εάν ο Α δεν έχει τσουγκρίσει με τον Β και ο Γ δεν έχει τσουγκρίσει με τον Δ τότε στην τετράδα (Α,Β,Γ,Δ) δεν υπάρχει κάποιος που έχει τσουγκρίσει με όλους τους άλλους. Επίσης εάν ο Α δεν έχει τσουγκρίσει με τους Β,Γ,Δ τότε πάλι στην τετράδα (Α,Β,Γ,Δ) δεν υπάρχει κάποιος που έχει τσουγκρίσει με όλους τους άλλους. Οπότε για να ισχύει πως σε κάθε τετράδα υπάρχει κάποιος που έχει τσουγκρίσει με όλους, μπορούν να μην έχουν γίνει το πολύ δύο τσουγκρίσματα, π.χ. του Α με τον Β και του Α με τον Γ. Άρα ο ελάχιστος αριθμός ατόμων που τσούγκρισαν με 44 άτομα είναι 42.
Πρόβλημα 2
Μας αρκούν 42 ομοτράπεζοι για πετύχουμε το ζητούμενο. Σε περίπτωση που έχουμε 41 το ζητούμενο υπάρχει η περίπτωση να μη πραγματοποιηθεί . Ας σκεφτούμε την περίπτωση όπου ότι οι 4 δεν τσούγκρισαν αβγά μεταξύ τους , αλλά μόνο με τους υπόλοιπους.
Ας παρατείνουμε τη δημοσίευση σχολίων / λύσεων μέχρι την Κυριακή 5/5/19 για τους φίλους που ήθελαν και δεν πρόλαβαν να ασχοληθούν..
Άψογος ο Πάνος και στα δύο, ολόσωστος κι ο Κωστής στο 2 !!
Θα δώσω μόνο μια απλή αιτιολόγηση στο 1:
Υπολογίζουμε το μέγιστο αριθμό τσουγκρισμάτων που θα μπορούσε να έχουν γίνει αν αγνοούσαμε τον περιορισμό και αφαιρούμε από αυτόν τον ελάχιστο αριθμό τσουγκρισμάτων που πρέπει να ΜΗΝ έχουν γίνει για να ικανοποιείται ο περιορισμός. Αν μια ομάδα περιέχει όλα τα χ στο πλήθος άτομα που έχουν ίσο αριθμό τσουγκρισμάτων, τότε εξ ορισμού κανένα ζευγάρι από αυτά τα χ άτομα δεν έχουν τσουγκρίσει αβγά μεταξύ τους. Αρκεί επομένως όλα αυτά τα μη γενόμενα τσουγκρίσματα, που είναι ΣC(χ,2) στο πλήθος, για όλες τις δυνατές τιμές χ, να είναι τα μόνα που λείπουν. Ο αριθμός χ μπορεί να πάρει διαδοχικά:
τιμή 1 για 1 άτομο με C(1,2)=0,
τιμή 2 για 2 άτομα με C(2,2)=1,
………………….
τιμή 8 για 8 άτομα με C(8,2)=28
τιμή 9 για 9 άτομα με C(9,2)=36
Έτσι καλύπτεται το σύνολο των 1+2+3+4+5+6+7+8+9 = 45 ατόμων με ταυτόχρονη ελαχιστοποίηση των μη γενομένων τσουγκρισμάτων, άρα ο αριθμός των τσουγκρισμάτων που έγιναν δεν μπορεί να είναι μεγαλύτερος από:
C(45,2)-C(2,2)-C(3,2)-C(4,2)-C(5,2)-C(6,2)-C(7,2)-C(8,2)-C(9,2) = 990-1-3-6-10-15-21-28-36 = 990-120 = 870
Ο αριθμός αυτός είναι εφικτός ως εξής:
Αριθμούμε τα άτομα από 1 έως 45.
Ο 1 τσουγκρίζει με όλους τους άλλους.
Οι 2,3 όχι μεταξύτους και ναι με όλους τους υπόλοιπους.
Οι 4,5,6 όχι μεταξύ τους και ναι με όλους τους υπόλοιπους.
Οι 7,8,9,10 όχι μεταξύ τους και ναι με όλους τους υπόλοιπους.
………………..
Οι 37,38,39,40,41,42,43,44,45 όχι μεταξύ τους και ναι με όλους τους υπόλοιπους.