Φροντιστήριο #5 Ασκήσεις σε Συναρτήσεις – Αρχή του Περιστερώνα 7/4/2017 ΜΕΡΟΣ Α: ΣΥΝΑΡΤΗΣΕΙΣ
Άσκηση Φ5.1: (α) Έστω οι συναρτήσεις διάγραμμα.
f : A → B, g : B → C και h : C → D που ορίζονται στο παρακάτω
Υπολογίστε την συνάρτηση h g
f.
(β) Έστω οι συναρτήσεις f: ℝ → ℝ με f ( x) = x + 3x + 1 και g: ℝ → ℝ με g ( x) = 2 x − 3. Υπολογίστε τις συναρτήσεις f g και g f . 2
Λύση (α) Το ζητούμενο είναι μία συνάρτηση K:A → D, τέτοια ώστε Κ(x) = h(g(f(x))), ∀ x ∈ A. Διαδοχικά έχουμε: f(a) = 2, g(2) = g(f(a)) = x, h(x) = h(g(f(a))) = 4 f(b) = 1, g(1) = g(f(b)) = y, h(y) = h(g(f(b))) = 6 f(c) = 2, g(2) = g(f(c)) = x, h(x) = h(g(f(c))) = 4 Άρα για τα a, b, c ∈ A, ορίζονται αντίστοιχα οι εικόνες h(g(f(a))), h(g(f(b))), h(g(f(c))) ∈ D με: h(g(f(a))) = 4 h(g(f(b))) = 6 h(g(f(c))) = 4 (β)
fog = f ( g ( x)) = f (2 x − 3) = (2 x − 3)2 + 3(2 x − 3) + 1 = 4 x 2 − 12 x + 9 + 6 x − 9 + 1 = 4 x 2 − 6 x + 1 gof = g ( f ( x)) = g ( x 2 + 3x + 1) = 2( x 2 + 3x + 1) − 3 = 2 x 2 + 6 x − 1
Άσκηση Φ5.2: Έστω συναρτήσεις f : X → Y και g : Y → Z οι οποίες είναι και οι δύο ένα προς ένα. Αποδείξτε ότι σε αυτήν την περίπτωση, η σύνθεσή τους g f είναι επίσης ένα προς ένα.
Λύση Για να δείξουμε ότι η g f είναι 1 προς 1 αρκεί να δείξουμε ότι εάν τα x1, x2 με x1 ≠ x2, είναι δύο στοιχεία του Χ, τότε θα πρέπει και g(f(x1)) ≠ g(f(x2)). Επειδή η f είναι 1 προς 1, ισχύει ότι ∀ x1, x2 ∈ Χ, με x1 ≠ x2, f(x1) ≠ f(x2). Επειδή όμως και η συνάρτηση g είναι 1 προς 1, εφόσον f(x1), f(x2) ∈ Υ, και f(x1) ≠ f(x2) ισχύει ότι g(f(x1)) ≠ g(f(x2)), το οποίο είναι το ζητούμενο.
Άσκηση Φ5.3: Έστω συναρτήσεις f : X → Y και g : Y → Z οι οποίες είναι και οι δύο επί. Αποδείξτε ότι σε αυτήν την περίπτωση, η σύνθεσή τους g f είναι επίσης επί. Λύση Έστω x , z στοιχεία των συνόλων Χ , Z αντίστοιχα. Αρκεί να δείξουμε ότι: ∀ z ∈ Z, ∃ x ∈ X, τέτοιο ώστε, g(f(x)) = z. Επειδή η g είναι επί, τότε ∀ z ∈ Z, ∃ y ∈ Y, τέτοιο ώστε g(y) = z. Επειδή η f είναι επί, ∀ y ∈ Y, τότε ∃ x ∈ X, τέτοιο ώστε f(x) = y. Άρα όντως ισχύει ότι ∀ z ∈ Z, ∃ x ∈ X, τέτοιο ώστε, g(f(x)) = z.
Άσκηση Φ5.4: Έστω τα σύνολα A = {1, 2,3, 4,5, 6, 7,8} και B = {{1,8},{2, 7},{3, 6},{4,5}} . Ορίζουμε επίσης τη συνάρτηση f : A → B με βάση τον κανόνα « f ( x) = y όταν x ∈ y. » a) Βρέστε τα f (3) και f (6) . b) Είναι η συνάρτηση f ένα-προς-ένα; Είναι η συνάρτηση f επί; Δικαιολογείστε την απάντησή σας. Λύση (α)
f (3) = {3,6} f (6) = {3,6} (β) Η συνάρτηση δεν είναι ένα προς ένα γιατί από το (α) έχουμε ήδη ότι f (3)=f(6). Η συνάρτηση είναι επί γιατί κάθε στοιχείο του συνόλου Β αποτελεί εικόνα κάποιου στοιχείου του συνόλου Α.
Άσκηση Φ5.5: (α) Μπορεί μία συνάρτηση f:{α,β,γ,δ} {1,2,3,4} να μην είναι ούτε “επί”, ούτε “1-προς-1”; Αν ναι, δώστε παράδειγμα. Αν όχι, δικαιολογείστε την απάντησή σας. (β) Μπορεί μία συνάρτηση f:{α,β,γ,δ} {1,2,3,4} να είναι “επί”, αλλά να μην είναι “1-προς-1”; Αν ναι, δώστε παράδειγμα. Αν όχι, δικαιολογείστε την απάντησή σας. Λύση α)
Σύμφωνα με τον ορισμό, για να είναι η f, 1-προς-1 θα πρέπει: ∀ ∈ , , , ∀ ∈ 1,2,3,4 ( ( = ( → = .
Επίσης για να είναι επί θα πρέπει ∀ ∈ 1,2,3,4 ∃ ∈
, , ,
( (
=
Η f μπορεί να μην είναι ούτε “επί”, ούτε “1-προς-1”. Ένα παράδειγμα φαίνεται στο παρακάτω σχήμα:
α β γ δ
1 2 3 4
Σύμφωνα με τις παραπάνω εκχωρήσεις είναι: f(α) = 1, f(β) = 2, f(γ)=2, f(δ)=3. Παρατηρούμε ότι για f(β) = f(γ)=2 είναι x≠y, αφού x=β και y =γ, άρα η f δεν είναι “1-προς-1”. Παρατηρούμε επίσης ότι δεν υπάρχει x τέτοιο ώστε f(x) = 4, άρα η f δεν είναι ούτε “επί” . β) Έστω Α = {α,β,γ,δ} και Β = {1,2,3,4}. |Α|=|Β|=4. Έστω ότι υπάρχει f που είναι “επί” αλλά δεν είναι “1-προς-1”. Εφόσον είναι “επί” , κάθε στοιχείο y στο B είναι εικόνα κάποιου στοιχείου x του Α. Δεδομένου ότι |Α|=|Β|=4 η f είναι αναγκαστικά συνάρτηση “1-προς-1”.
Άσκηση Φ5.6: Έστω ότι οι συναρτήσεις f: A B και g: Β A ικανοποιούν τη σχέση g∘f = IA. Αποδείξτε ότι η f είναι συνάρτηση 1 προς 1 και ότι η g είναι επί. Λύση Αν η g δεν είναι επί, τότε υπάρχει κάποιο στοιχείο της σύνθεσης που δεν έχει εικόνα, πράγμα άτοπο (αφού η IA είναι 1 προς 1 και επί). Αν η f δεν είναι 1 προς 1, τότε υπάρχουν στοιχεία του Β στα οποία η f δεν έχει εικόνα και για τα οποία η g(f(x)) δεν ορίζεται. Άτοπο
Άσκηση Φ5.7: Αποδείξτε ότι αν μία σχέση ισοδυναμίας επί ενός συνόλου Α είναι και συνάρτηση από το Α στο Α, τότε αναγκαστικά είναι η ταυτοτική συνάρτηση. Λύση Μία διμελής σχέση R: AxA, επί ενός συνόλου A είναι σχέση ισοδυναμίας αν και μόνο αν έχει την ανακλαστική, συμμετρική και μεταβατική ιδιότητα. Συμμετρική : ∀a,b((a,b)∈R (b,a)∈R) Μεταβατική: ∀a,b,c(((a,b)∈R∧(b,c)∈R)→(a,c)∈R) Ανακλαστική: ∀a∈A(a, a) ∈R
Για να είναι η R συνάρτηση από το A στο A, θα πρέπει να ισχύει: R ={ (a, R(a)) | a∈A , R(a) ∈A}. Εφόσον η R είναι σχέση ισοδυναμίας και έχει την ανακλαστική ιδιότητα, όλα τα ζεύγη της μορφής (a, a) πρέπει να ανήκουν σε αυτή. Εφόσον η R είναι συνάρτηση, κανένα άλλο στοιχείο της μορφής (a, b) με (b≠a) δεν μπορεί να ανήκει σε αυτήν. Άρα η R περιλαμβάνει ακριβώς τα στοιχεία της μορφής (a, a). Άρα η R είναι η ταυτοτική συνάρτηση.
Άσκηση Φ5.8: Έστω h( x) = ( x + 6) − 9. Βρέστε δύο συναρτήσεις f και g τέτοιες ώστε h( x ) = f ( g ( x )). 2
Λύση f(x)= x-9 g(x) = x2+6
Άσκηση Φ5.9: Για καθεμία από τις παρακάτω συναρτήσεις υπολογίστε την αντίστροφή της
(a)
f1 ( x) = 3x + 4
(b)
f 2 ( x) = 3(2 x + 5)
(c )
f3 ( x) = (3x + 4) / 2 + 6
Λύση (a) f(x) = 3x + 4 y = 3x +4 y -4 = 3x (y-4)/3 = x x = (y-4)/3 (b) f(x)= 3(2x+5) = 6x + 15 y = 6x + 15 y -15 = 6x x = (y-15)/6 (c) f(x)= (3x + 4)/2 +6 y = (3x + 4)/2 +6 y-6 = (3x +4)/2 2y-12 = 3x +4 2y -16 =3x x = (2y-16)/3
Άσκηση Φ5.10 Υπολογίστε τις συναρτήσεις (a)
f1 f 2 , (b) f2 f3 , (c) f3 f1 , αν
(1)
f1 ( x) = 3x + 4
(2)
f 2 ( x) = 3(2 x + 5)
(3)
f3 ( x) = (3x + 4) / 2 + 6
Λύση (a) f1(f2(x)) = (3(6x + 15) + 4) = (18x + 45) +4 = 18x +49 (b) f2(f3(x))= (6((3x+4)/2 + 6) + 15) = (9x + 12 +36 +15) = 9x +63 (c) f3(f1(x)) = ((3(3x +4)+4)/2 +6) = ((9x + 12 + 4)/2 +6) = 9x/2 + 14
Άσκηση Φ5.11 Έστω η συνάρτηση f : ℕ → ℤ η οποία ορίζεται ως εξής:
n − αρτιος −n / 2 f (n) = (n + 1) / 2 n − περιττος Αποδείξτε ότι η f είναι αμφιμονοσήμαντη. Λύση Έστω k,m ∈N 1. k και m άρτιοι. Τότε f(k)=f(m) -k/2 = -m/2k=m 2. k και m περιττοί. Τότε f(k)=f(m) (k+1)/2 = (m+1)/2 k+1=m+1k=m 3. k άρτιος και m περιττός . Παρατηρώ ότι f(k) = -k/2 ≤0 ενώ (m+1)/2 > 0 . Άρα f(k)≠f(m) Τότε f(k)=f(m) . Το ίδιο προφανώςισχύει και για τη αντίστροφη περίπτωση (k περιττός και m άρτιος) Επομένως, αν κάποιος από δύο φυσικούς είναι άρτιος και ο άλλος περιττός, αποκλείεται να έχουν την ίδια εικόνα μέσω της f. Επομένως η f είναι “1-1”. Η f(n) είναι “επί” εφόσον κάθε στοιχείο του Ζ αποτελεί εικόνα κάποιου στοιχείου του Ν. Άρα η f(n) είναι αμφιμονοσήμαντη
Άσκηση Φ5.12 Έστω ℤ* το σύνολο των ακεραίων εκτός του μηδενός και ℚ το σύνολο των ρητών. Θεωρείστε τη συνάρτηση f : ℤ × ℤ → ℚ η οποία ορίζεται ως f ( n, m ) = n / m. Δείξτε συνάρτηση και προσδιορίστε αν είναι (a) “1 προς 1”, (b) “επί”. *
ότι η f είναι όντως
Λύση Η f(n,m) =n/m είναι συνάρτηση εφόσον κανένα ζευγάρι ακεραίων n, m δεν αντιστοιχεί σε 2 ή περισσότερους ρητούς και κάθε ζευγάρι ακεραίων του πεδίου ορισμού έχει εικόνα στο σύνολο των ρητών. Η f(n,m) δεν είναι “1-1” επειδή για f(1,1) = f(-1,-1) = 1 Η f(n,m) είναι “επί” επειδή εξ ορισμού, αναπαριστά όλους τους δυνατούς ρητούς αριθμούς.
Άσκηση Φ5.13 Προσδιορίστε ποιες από τις παρακάτω συναρτήσεις fi: ℝ⟶ℝ είναι “1-1”, ποιες είναι “επί” και ποιες είναι αμφιμονοσήμαντες. Για τις αμφιμονοσήμαντες βρείτε αντίστροφη συνάρτηση a. f1(x) = x-1 b. f2(x)=x3 c. f3(x)=x3 -x d. f4(x)=x3 -3x2+3x-1 e. f5(x)=ex , ≥0 f. f6(x)= − , <0 Λύση a. Είναι αμφιμονοσήμαντη. f1-1(x)=x+1 $ b. Είναι αμφιμονοσήμαντη. f2-1(x)= √ c. Είναι “επί” αλλά όχι “1-1” (π.χ. f(1)=f(0)) $ d. Είναι αμφιμονοσήμαντη. f4-1(x)= √ +1 e. Είναι “1-1” αλλά όχι “επί” (Όλα τα f5(x) είναι θετικά) ≥0 f. Είναι αμφιμονοσήμαντη. f6-1(x)= √ −√ − , <0 Άσκηση Φ5.14 Έστω συναρτήσεις f και g: ℝ⟶ℝ με f(x)= x2 και g(x)= x2 -1. Βρείτε τις συναρτήσεις f∘f, f∘g, g∘f, g∘g. Βρείτε τα στοιχεία του συνόλου {x∈ℝ|f(g(x))=g(f(x))} Λύση f∘f(x)=f(f(x))= x4 f∘g(x)=f(g(x))=( x2 -1)2= x4-2x2+1 g∘f(x)=g(f(x))= x4-1 g∘g(x)=g(g(x))=(x2 -1)2-1= x4-2x2+1-1= x4-2x2= x2 (x2 -2) f(g(x))=g(f(x))⟺x4-2x2+1= x4-1⟺-2x2=-2⟺x=±1
Άσκηση Φ5.15 Έστω f: A⟶B μια συνάρτηση και Α1, Α2⊆Α. Βρείτε αν f(Α1⋃ Α2) ⊆ f(Α1)⋃f (Α2) και αν f(Α1∩ Α2) ⊆ f(Α1) ∩f (Α2). Αν ναι, αποδείξτε το, αν όχι δώστε αντιπαράδειγμα. Λύση 1. Έστω y∈ f(Α1⋃ Α2). Τότε υπάρχει x ∈ Α1⋃ Α2 τέτοιο που f(x)=y. Αν x∈ Α1, τότε y∈ f(Α1) άρα y∈ f(Α1)⋃f (Α2). Ομοίως αν y∈ f(Α2). Συνεπώς f(Α1⋃ Α2) ⊆ f(Α1)⋃f (Α2) 2. Έστω t∈f( Α1∩ Α2) . Τότε t=f(s) για κάποιο s ∈ Α1∩ Α2. s∈ Α1 και s∈ Α2 άρα t∈ f(Α1) ∩f (Α2).
Άσκηση Φ5.16 Έστω συνάρτηση
f ( A1 ) ⊆ f ( A2 ).
f : A → B και σύνολα A1 ⊆ A, A2 ⊆ A. Αποδείξτε ότι εάν A1 ⊆ A2 , τότε
Λύση Έστω y ∈ f(Α1). Τότε y=f(x) για κάποιο x∈ Α1. Εφόσον A1 ⊆ A2 , τότε και x∈ Α2 άρα και y ∈ f(Α2) ο.ε.δ. Άσκηση Φ5.17 Βρείτε τις αντίστροφες συναρτήσεις των: a. f(x)=9-4x () b. f(x)= * c. f(x)= x2, x≤0 d. f(x)=√4 − 7 (./ e. f(x)= 0(. Λύση
a. f(x)=9-4x⇔ y=9-4x⇔ x= ()
() *
b. f(x)= * ⇔ y= c. f(x)= x2, x≤0
2)3 2)3 ⇔ f-1(y)= 4 4
⇔ x=6y+2⇔ f-1(y)= 6y+2
Ο περιορισμός x≤0 κάνει τη συνάρτηση αμφιμονοσήμαντη f(x)= x2⇔ y= x2⇔ 5 = √ ⇔ x=±5 Γνωρίζουμε ότι πεδίο τιμών της f-1(x) είναι το πεδίο ορισμού της f(x). Άρα οι πεδίο τιμών της f-1(y) είναι το (-∞,0]. Οπότε επιλέγουμε τις αρνητικές τιμές: f-1(y)= −5
d. f(x)=√4 − 7 ⇔ y=√4 − 7 ⇔ y2= (√4 − 7 ⇔ y2=4x-7 ⇔ y= (./
3 6 .7 ⇔ 4
f-1(y)=
36 .7 4
(./
/) 3
e. f(x)= 0(. ⇔ y= 0(. ⇔ y(3x+2)=x+1 ⇔ 3xy+2y=x+1⇔ 3xy-x=1-2y⇔ x(3y-1)=1-2y⇔ x= 03)/⇔ f1
(y)=
/) 3 03)/
Άσκηση Φ5.18 Σε κάθε μια από τις παρακάτω συναρτήσεις προσδιορίστε αν είναι “επί”, “ένα προς ένα”, ή αμφιμονοσήμαντη. Δικαιολογείστε την απάντησή σας 1. f: ℝ ℝ με f(x)=2-3x 2. f: ℝ ℝ με f(x)=2x2+3 3. f: ℝ ℝ≥3 με f(x)=2x2+3 4. f: ℤ ℤ με f(x)=x2+x ;./ , < =>
[email protected]όC 5. f: ℕ ℕ με f(n)=: ; , < ά
[email protected] Λύση 1. Αν f(x)=f(y) τότε 2 − 3x = 2 − 3y⇔ 3x = 3y ⇔ x = y. Άρα η f είναι “1-1” (1) )3 Αν y ∈ R, τότε υπάρχει x ∈ R τ.ω. f(x) = y: Θα πρέπει 2 − 3x = y ⇔ x = . Παρατηρούμε ότι 0
)3
f(x) = f( ) = 2 − 3( 0 αμφιμονοσήμαντη.
)3 ) 0
= 2 − 2 + y = y. Άρα η F είναι “επί” (2). Από (1) και (2) η f είναι
2. Η f δεν είναι “1-1”: f(1) = f(−1) = 5. To Πεδίο Τιμών της f είναι το σύνολο {f(x) | x ∈ R} = {2x2 + 3 | x ∈ R} =[3, +∞)≠ R. Άρα η f δεν είναι “επί”. 3. Όπως και στο προηγούμενο παράδειγμα η f δεν είναι “1-1”. Αλλά είναι “επί” εφόσον εδώ το Πεδίο Τιμών είναι το ℝ≥3. 4. Η f δεν είναι “1-1” μια και f(0) = f(−1) = 0. Η f δεν είναι “επί” μια και για παράδειγμα 1 ∈ Z αλλά δεν μπορούμε να βρούμε n ∈ Z τέτοιο που f(n) = n 2 + n = 1 (η εξίσωση n 2 + n -1 = 0 δεν έχει ακέραιες λύσεις). /./ 5. f(1) = = 1 και f(2) = = 1 δηλαδή f (1) = f(2). Άρα η f δεν είναι “1-1”
Έστω m∈ ℕ και έστω n=2m. Τότε f(n) =
F
= m. Άρα είναι “επί”.
Άσκηση Φ5.19 Έστω f: A⟶B μια συνάρτηση και Α1, Α2⊆Α. Αποδείξτε ότι η f είναι “ένα προς ένα” αν και μόνο αν f(Α1∩ Α2) = f(Α1) ∩f (Α2) . Λύση Έστω ότι η f είναι “1-1” Αποδεικνύω ότι (a) f(Α1∩ Α2) ⊆ f(Α1) ∩ f(Α2): Έστω t∈f( Α1∩ Α2) . Τότε t=f(s) για κάποιο s ∈ Α1∩ Α2. s∈ Α1 και s∈ Α2 άρα t∈ f(Α1) ∩f (Α2) Σημείωση:Η απόδειξη είναι γνωστή και από την άσκηση Φ5.15 του φροντιστηρίου και (b) f(Α1) ∩ f(Α2) ⊆ f(Α1∩ Α2): Αν t ∈ f(Α1) ∩ f(Α2), τότε t = f(a1) για κάποιο a1 ∈ Α1 και t = f(a2) για κάποιο a2 ∈ Α2. Αλλά η f είναι “1-1” άρα a1 = a2 οπότε t ∈ f(Α1∩ Α2). Αντίστροφα έστω ότι f(Α1∩ Α2) = f(Α1) ∩f (Α2) και ότι f(x1) = f(x2) για στοιχεία x1 ≠ x2 στο Α. Έστω Α1 = {x1} και Α2= {x2}. Τότε Α1∩ Α2= ∅, αλλά f(Α1) ∩ f(Α2) = {f(x1)} ≠ ∅= f(Α1∩ Α2) , γεγονός που έρχεται σε αντίθεση με την υπόθεση. Άρα η f είναι “1-1”
ΜΕΡΟΣ Β: ΑΡΧΗ ΤΟΥ ΠΕΡΙΣΤΕΡΩΝΑ Άσκηση Φ5.20: Ο Νίκος διαλέγει 5 διαφορετικούς αριθμούς από το 1 έως και το 8. Αποδείξτε ότι οποιουσδήποτε αριθμούς κι αν διαλέξει, θα υπάρχουν τουλάχιστον δύο που το άθροισμά τους θα είναι ίσο με 9. Λύση Ας θεωρήσουμε την συνάρτηση της άσκησης 5.4: f : A → B όπου f ( x) = y όταν x ∈ y με A = {1, 2,3, 4,5, 6, 7,8} και
B = {{1,8},{2, 7},{3, 6},{4,5}} Η συνάρτηση αυτή απεικονίζει τους αριθμούς 1 έως 8 σε 4 σύνολα. Επομένως, αν επιλέξουμε 5 αριθμούς, αναγκαστικά από την αρχή του περιστερώνα, 2 από αυτούς θα έχουν την ίδια εικόνα στο Β. Ωστόσο, αν ισχύει αυτό, είναι εξασφαλισμένο ότι δύο από τους πέντε αριθμούς θα έχουν άθροισμα 9, εφόσον τα στοιχεία οποιουδήποτε από τα σύνολα του Β αθροίζουν σε 9.
Άσκηση Φ5.21: Πέντε σημεία επιλέγονται τυχαία μέσα σε ένα ισόπλευρο τρίγωνο με μοναδιαίο μήκος πλευράς. Αποδείξτε ότι αναγκαστικά υπάρχει τουλάχιστον ένα ζευγάρι σημείων των οποίων η απόσταση δεν υπερβαίνει το ½. Λύση Περιστέρια: τα 5 σημεία Περιστερώνες: τα τέσσερα ισόπλευρα τρίγωνα με μήκος πλευράς 1/2 που σχηματίζονται εάν ενώσουμε τα μέσα των πλευρών του τριγώνου.
Δεδομένου ότι 5 περιστέρια τοποθετούνται σε 4 περιστερώνες, τουλάχιστον ένα ζεύγος περιστεριών θα τοποθετηθεί στον ίδιο ένα περιστερώνα. Γι’ αυτά τα σημεία, είναι προφανές ότι η απόστασή τους είναι μικρότερη από το μήκος των πλευρών του τριγωνικού περιστερώνα, το οποίο είναι ½.
Άσκηση Φ5.22: Έστω ότι το Α είναι ένα σύνολο έξι θετικών ακεραίων καθένας από τους οποίους είναι μικρότερος του 13. Δείξτε ότι υπάρχουν δύο διαφορετικά υποσύνολα του Α των οποίων όταν τα στοιχεία προστεθούν, δίνουν το ίδιο άθροισμα (για παράδειγμα, έστω Α={5, 12, 10, 1, 3, 4}. Παρατηρούμε ότι όντως μπορούμε να βρούμε υποσύνολα Α1={1, 4, 10} και Α2={5, 10} του Α καθένα από τα οποία έχει άθροισμα στοιχείων ίσο με το 15). Λύση To A είναι σύνολο 6 θετικών ακεραίων, υποχρεωτικά διαφορετικών μεταξύ τους, μικρότερων του 13. Τα δυνατά αθροίσματα στοιχείων των υποσυνόλων του Α κυμαίνονται από 0 (για το ∅) ως 57 (για το {7, 8, 9, 10, 11, 12}). Το πλήθος των διαφορετικών υποσυνόλων ενός συνόλου 6 στοιχείων είναι 26=64. Επομένως, αν τα περιστέρια είναι τα διαφορετικά υποσύνολα του Α και οι περιστερώνες τα αθροίσματα από 0 έως 57, γνωρίζουμε από την αρχή του περιστερώνα ότι θα υπάρχουν τουλάχιστον δύο υποσύνολα με ίδιο άθροισμα στοιχείων.
Άσκηση Φ5.23 Δείξτε ότι μέσα σε ένα σύνολο 52 διαφορετικών ακεραίων υπάρχουν τουλάχιστον 2 το άθροισμα ή η διαφορά των οποίων να διαιρείται με το 100. Λύση
Θεωρούμε τα σύνολα {50}, {49, 51}, {48, 52}, {47, 53}, …, {2, 98}, {1, 99}, {0, 100}. Παρατηρούμε ότι το άθροισμα των στοιχείων των συνόλων με δύο στοιχεία είναι 100. Ας θεωρήσουμε περιστέρια τα υπόλοιπα της ακέραιας διαίρεσης των 52 ακεραίων δια του 100 και περιστερώνες τα 51 σύνολα που σχηματίσαμε. Από την αρχή του περιστεριώνα προκύπτει ότι δύο τουλάχιστον από τους 52 ακεραίους θα απεικονιστούν στο ίδιο σύνολο. Σε αυτή την περίπτωση όμως είναι προφανές ότι είτε το άθροισμά τους είτε η διαφορά τους διαιρείται ακέραια με το 100.
Άσκηση Φ5.24: Αποδείξτε με βάση την αρχή του περιστεριώνα ότι σε κάθε σύνολο 100 ακεραίων, υπάρχουν δύο των οποίων η διαφορά είναι ακέραιο πολλαπλάσιο του 37. Λύση Τα περιστέρια είναι οι 100 ακέραιοι. Οι περιστεριώνες είναι οι αριθμοί από το 0 έως το 36. Απεικονίζουμε κάθε ακέραιο k στον k mod 37. Εφόσον υπάρχουν 100 περιστέρια και μόνο 37 περιστεριώνες, δύο περιστέρια τουλάχιστον θα μπούν στον ίδιο περιστεριώνα. Αυτό σημαίνει πως για τους δύο αυτούς ακέραιους k1 και k2, ισχύει ότι k1 mod 37 = k2 mod 37, το οποίο με τη σειρά του σημαίνει ότι ο k1−k2 είναι πολλαπλάσιο του 37.
Άσκηση Φ5.25: Έστω ένα τουρνουά στο οποίο καθένας από n παίκτες παίζει με όλους τους υπόλοιπους και κερδίζει τουλάχιστον έναν αγώνα. Δείξτε ότι υπάρχουν τουλάχιστον δύο παίκτες με ίδιο αριθμό νικών. Λύση Ο αριθμός των νικών για ένα παίκτη είναι από 1 έως n-1. Αυτοί οι n-1 αριθμοί αντιστοιχούν σε n-1 περιστεριώνες στους οποίους πρέπει να αντιστοιχηθούν n παίκτες (περιστέρια...) . Άρα, από την αρχή του περιστεριώνα ξέρουμε ότι τουλάχιστον δύο παίκτες θα έχουν τον ίδιο αριθμό νικών.
Άσκηση Φ5.26: Δείξτε ότι οποιοδήποτε σύνολο από επτά ακεραίους, περιέχει δύο ακεραίους x και y, τέτοιους ώστε είτε ο x+y να διαιρείται ακριβώς από τον 10, είτε ο x-y και διαιρείται ακριβώς από τον 10. Λύση Έστω Χ={x1, x2, x3, x4, x5, x6, x7} το σύνολο των επτά ακεραίων και ri το υπόλοιπο της ακέραιας διαίρεσης του xi με το 10. Έστω η ακόλουθη διαμέριση του X: H1 = {xi: ri=0} H2 = {xi: ri=5} H3 = {xi: ri=1 ή ri=9} H4 = {xi: ri=2 ή ri=8} H5 = {xi: ri=3 ή ri=7} H6 = {xi: ri=4 ή ri=6} Υπάρχουν 6 περιστεριώνες για 7 περιστέρια. Άρα, δύο από τους επτά ακεραίους θα πρέπει να ανήκουν στο ίδιο Ηi. Σε οποιοδήποτε όμως από τα έξι αυτά σύνολα κι αν ανήκουν δύο ακέραιοι, τότε το άθροισμά τους ή η διαφορά τους διαιρείται ακριβώς με το 10.
Άσκηση Φ5.27 Σε ένα οπωροπωλείο υπάρχουν 50 καλάθια με μήλα. Κανένα καλάθι δεν είναι άδειο και κάθε καλάθι περιέχει το πολύ 24 μήλα. Δείξτε ότι υπάρχουν τουλάχιστον τρία καλάθια με ίσο πλήθος μήλων. Λύση Έστω j τα καλάθια και aj τα μήλα σε κάθε καλάθι. 1 ≤aj ≤ 24 ∀j∈[1,50] Έχουμε 50 καλάθια (περιστέρια) τα οποία μπορούν να έχουν 24 διαφορετικές χωρητικότητες (περιστερώνες). Από την αρχή του περιστερώνα, γνωρίζουμε ότι τουλάχιστον IJ
ceiling(50/24) =H K = 3 καλάθια θα έχουν τον ίδιο αριθμό μήλων. 4
Άσκηση Φ5.28 Ένα παιδί πίνει τουλάχιστον ένα ποτήρι γάλα την ημέρα. Δεδομένου ότι έχει πιεί 700 ποτήρια γάλα σε μια χρονιά (365 ημέρες), αποδείξτε ότι υπάρχουν κάποιες συνεχόμενες ημέρες τη χρονιά αυτή κατά τις οποίες ήπιε ακριβώς 29 ποτήρια γάλα. Λύση Έστω j οι μέρες και aj τα ποτήρια γάλα μέχρι τη μέρα j. Τότε η a1 ,a2,. . . . . ., a365 Є Z+ είναι μια ακολουθία από 365 διαφορετικούς ακέραιους όπου 1≤aj≤700 Επομένως a1+29,a2+29,. . . . ,a365+29 είναι μια ακολουθία από 365 διαφορετικούς ακεραίους με 30≤aj+29≤729 Άρα (a1, a2, . . . . . . . ,a365, a1+29,. . . . . . . .,a365+29) είναι μια ακολουθία από 730 ακεραίους από το σύνολο {1,2,. . . . . .,729} Από την αρχή του περιστερώνα δύο από αυτές είναι ίσοι, αλλά a1, a2. . . . . ,a365 είναι διαφορετικοί μεταξύ τους και οι a1+29, a2+29,. . . . . a365+29 είναι διαφορετικοί μεταξύ τους.Επομένως υπάρχει i,j ai = aj + 29 άρα υπάρχειi,j τ.ω. ai - aj= 29 και επομένως υπάρχουν μέρες i,j τ.ω. μεταξύ τους να έχει πιει 29 ποτήρια γάλα.
Άσκηση Φ5.29 Έχουμε τοποθετήσει 13 τετράγωνα καθένα από τα οποία έχει μήκος πλευράς ίσο με 1, μέσα σε ένα κύκλο ακτίνας μήκους ίσου με 2. Δείξτε ότι τουλάχιστον δύο από τα τετράγωνα έχουν ένα κοινό σημείο. Λύση Η ακτίνα του κύκλου είναι 2. Άρα το εμβαδόν του κύκλου είναι π*r2 = 22*3,14159 = 12.56636 . Το εμβαδόν 13 τετραγώνων μήκους πλευράς 1 είναι 13*12 = 13. Άρα 13/12.56636 = 1,034 Άρα 2 τετράγωνα πρέπει να μπουν στο ίδιο χώρο άρα αναγκαστικά εφόσον έχουν το ίδιο μήκος πλευράς ένα σημείο τους θα είναι κοινό.
Άσκηση Φ5.30 Έστω 26 τυχαία, διαφορετικά υποσύνολα του {1, 2, 3, 4, 5, 6, 7, 8, 9} καθένα από τα οποία έχει 3 στοιχεία. Αποδείξτε ότι τουλάχιστον δύο από αυτά έχουν το ίδιο άθροισμα στοιχείων.
Λύση To υποσύνολο με το μικρότερο δυνατό άθροισμα είναι το {1,2,3}, με άθροισμα στοιχείων 6 και το αντίστοιχο με το μεγαλύτερο είναι το {7,8,9} με άθροισμα στοιχείων 24. Άρα τα δυνατά αθροίσματα είναι 19 (από 6 ως 24) Αν ορίσουμε περιστερώνες τα 19 διαφορετικά αθροίσματα και περιστέρια τα 26 υποσύνολα, τουλάχιστον δύο απ’ αυτά θα έχουν ίδιο άθροισμα στοιχείων
Άσκηση Φ5.31 Δείξτε ότι αν επιλέξω 7 τυχαίους, διαφορετικούς αριθμούς από το σύνολο Α= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, τότε υποχρεωτικά, σε αυτούς τους 7 αριθμούς υπάρχουν 2 το άθροισμα των οποίων είναι ίσο με 12. Λύση Ας θεωρήσουμε περιστερώνες τα υποσύνολα του Α: {6}, (1,11),{2,10},(3,9},{4,8},{5,7} (6 στον αριθμό) και περιστέρια τους 7 τυχαίους αριθμούς. Από την αρχή του περιστερώνα δύο τουλάχιστον από αυτούς θα αντιστοιχιστούν στο ίδιο σύνολο οπότε το άθροισμά τους θα ισούται με 12.
Άσκηση Φ5.32 Υποθέστε ότι η Ελλάδα έχει 10,000,000 κατοίκους. Αποδείξτε ότι στην Ελλάδα υπάρχουν τουλάχιστον 5 άνθρωποι με τα ίδια αρχικά ονόματος και επιθέτου και ίδια ημερομηνία γενεθλίων (δεν μας απασχολεί το έτος γέννησης, μόνο η ημέρα και ο μήνας). ΛΥΣΗ Υπάρχουν 24x24 =576 δυνατές περιπτώσεις για τα αρχικά των ονομάτων και των επιθέτων των κατοίκων της Ελλάδας. Υπάρχουν 365 διαφορετικές ημερομηνίες γενεθλίων σε ένα έτος. Άρα υπάρχουν 576x365=210.240 διαφορετικοί τρόποι με τους οποίους οποιαδήποτε αρχικά μπορούν να συσχετιστούν με μία ημερομηνία γενεθλίων. Θεωρούμε περιστέρια τους 10.000.000 κατοίκους και περιστερώνες τους 210.240 διαφορετικούς τρόπους συσχέτισης με ημερομηνία γενεθλίων. Σύμφωνα με την αρχή του /J.JJJ.JJJ
περιστερώνα, υπάρχουν H K = 48 περιστέρια που υποχρεωτικά θα πρέπει να βρίσκονται στον /J. 4J ίδιο περιστερώνα. Ο αριθμός αυτός είναι ασφαλώς μεγαλύτερος από τους 5 που ζητά η άσκηση και επομένως, τουλάχιστον 5 άτομα με τα ίδια αρχικά ονόματος και επιθέτου θα έχουν γενέθλια την ίδια ημερομηνία σε ένα έτος.
Άσκηση Φ5.33 Επιλέγουμε τυχαία 11 αριθμούς από το σύνολο {1, 2, 3, …, 99, 100}. Δείξτε ότι όποια και να είναι η επιλογή του συνόλου των 11 αριθμών, μπορούμε να βρούμε δύο μη-κενά, ξένα μεταξύ τους υποσύνολα (του συνόλου των 11 αριθμών) με ίσο άθροισμα στοιχείων. ΛΥΣΗ Έχουμε ένα σύνολο από 11 ακεραίους οι οποίοι επιλέγονται από το σύνολο {1, 2, 3, …, 99, 100}. Όλα τα 11 μη-κενά δυνατά υποσύνολα ενός συνόλου 11 αριθμών είναι 2 − 1 = 2047 . Όποια και να είναι η επιλογή των αρχικών 11 αριθμών το μεγαλύτερο δυνατό συνολικό τους άθροισμα είναι 90+91+92+93+94+95+96+97+98+99+100=1045. Επομένως, από την αρχή του περιστερώνα, υπάρχουν
2047
τουλάχιστον = 1,958852 = 2 υποσύνολα με το ίδιο άθροισμα στοιχείων. Αν αυτά τα 1045 υποσύνολα είναι ξένα μεταξύ τους, τότε έχουμε αποδείξει το ζητούμενο. Αν δεν είναι ξένα μεταξύ τους, τότε αρκεί να αφαιρέσουμε και από τα δύο τα κοινά τους στοιχεία. Τα σύνολα που προκύπτουν πληρούν τις απαιτήσεις του ζητήματος (είναι μη κενά, ξένα μεταξύ τους, είναι υποσύνολα ενός υποσυνόλου 11 στοιχείων του {1, 2, 3, …, 99, 100} και έχουν το ίδιο άθροισμα).
Άσκηση Φ5.34 Έστω ότι έχουμε τη δυνατότητα να συγκεντρώσουμε ένα τυχαίο πλήθος ατόμων. Πόσο πρέπει να είναι το πλήθος αυτό, προκειμένου να είμαστε σίγουροι ότι τουλάχιστον τέσσερις από αυτούς έχουν γεννηθεί την ίδια ώρα, λεπτό και δευτερόλεπτο της ημέρας; (μας ενδιαφέρει να συμπίπτει μόνο η ώρα/λεπτά/δευτερόλεπτα και όχι η ημερομηνία: δηλαδή μέρα/ μήνας/χρόνος). Λύση Κάθε μέρα έχει 24x60x60 = 86400 δευτερόλεπτα Αν “περιστέρια” είναι οι x ζητούμενοι άνθρωποι και “περιστερώνες” τα 86400 δευτερόλεπτα της μέρας, από τη γενικευμένη αρχή του περιστερώνα θέλουμε (
(
HL*4JJK ≥ 4 ⟺ L*4JJ >3⟺x>259200 άτομα
Άσκηση Φ5.35 Αποδείξτε ότι σε n+1 τυχαία επιλεγμένους ακεραίους, υπάρχουν δύο που η διαφορά τους διαιρείται ακριβώς δια του n Λύση Αν θεωρήσουμε περιστερώνες τα n διαφορετικά υπόλοιπα της ακέραιης διαίρεσης ενός αριθμού με το n (0,1,2,…,n-1) και αντιστοιχίσουμε τους n+1 τυχαίους ακεραίους στους “περιστερώνες” ανάλογα με το υπόλοιπο της ακέραιας διαίρεσής τους με το n, δύο τουλάχιστον από αυτούς, σύμφωνα με την αρχή του περιστερώνα, θα έχουν ίδιο υπόλοιπο. Θα υπάρχουν δηλαδή δύο τουλάχιστον ακέραιοι x1 και x2 τέτοιοι που x1 = a1n+ b και x2=a2n+b. Άρα x1 - x2= (a1 -a2)n που διαιρείται ακριβώς δια του n Εφαρμογή Αποδείξτε ότι υπάρχουν 2 τουλάχιστον δυνάμεις του 3 που η διαφορά τους διαιρείται ακριβώς με το 2016. Λύση Η ακέραια διαίρεση με το 2016 αφήνει 2016 διαφορετικά υπόλοιπα. Θεωρούμε μια ακολουθία δυνάμεων του 3: 1,3,32, 34,..,32016 που αποτελείται από 2017 αριθμούς. Κάποιοι απ’ αυτούς (ας πούμε οι 3n και 3m , n>m έχουν ίδιο υπόλοιπο διαιρούμενοι δια του 2016. Άρα η διαφορά του (3n - 3m) διαιρείται ακριβώς με το 2016.
Άσκηση Φ5.36
Σ΄ ένα δρόμο υπάρχουν 51 σπίτια. Κάθε σπίτι έχει μια διεύθυνση ανάμεσα στο 1000 και στο 1099, συμπεριλαμβανομένων των ακραίων τιμών. Να δείξετε ότι, τουλάχιστον δύο σπίτια έχουν διευθύνσεις που είναι συνεχόμενοι ακέραιοι Λύση Έστω Α’=a1,a2,…,a51 η ακολουθία των 51 διαφορετικών μεταξύ τους διευθύνσεων των 51 σπιτιών με 1000 ≤ a1,a2,…a51 ≤1099 Δημιουργώ την ακολουθία Α’’= a1+1,a2+1,…,a51+1. Η ακολουθία αυτή έχει 51 αριθμούς, διαφορετικούς μεταξύ τους με 1001≤ a1+1,a2+1,…,a51+1≤1100 Η ακολουθία Α= a1,a2,…a51,a1+1,a2+1,…,a51+1 περιλαμβάνει 102 αριθμούς οι οποίοι ανήκουν στο διάστημα [1000,1100] Θεωρώ “περιστέρια” τους 102 αριθμούς a1,a2,…a51, a1+1,a2+1,…,a51+1 και “περιστερώνες” τους 101 διαφορετικούς ακεραίους στο [1000,1100] Με βάση την αρχή του περιστερώνα 2 τουλάχιστον απ’ αυτούς θα συμπίπτουν. Μια και οι ακολουθίες Α’ και Α’’ περιλαμβάνουν διαφορετικούς μεταξύ τους αριθμούς αναγκαστικά θα υπάρχει τουλάχιστον ένας ai και ένας aj+1 τέτοιοι που ai =aj+1 ⇨ ai -aj=1, δηλαδή οι ai και aj είναι διαδοχικοί Άσκηση Φ5.37 Ένα τοπικό δίκτυο αποτελείται από 6 υπολογιστές. Κάθε υπολογιστής είναι άμεσα συνδεδεμένος με τουλάχιστον έναν από τους άλλους υπολογιστές. Να δείξετε ότι υπάρχουν τουλάχιστον δύο υπολογιστές που συνδέονται άμεσα στο ίδιο πλήθος άλλων υπολογιστών Λύση Έστω Ν(ai) o αριθμός των υπολογιστών με τους οποίους είναι άμεσα συνδεδεμένος ο υπολογιστής ai Γνωρίζουμε ότι 1≤ Ν(ai) ≤5 Αν ορίσουμε “περιστέρια” τους 6 υπολογιστές a1,a2,…a6 και “περιστερώνες” τις 5 διαφορετικές τιμές Ν(ai) :1,2,3,4,5 τότε με βάση την αρχή του περιστερώνα, τουλάχιστον 2 υπολογιστές θα είναι άμεσα συνδεδεμένοι με ίδιο αριθμό υπολογιστών
Άσκηση Φ5.38 Σε ένα κατάστημα ψιλικών υπάρχουν δέκα προϊόντα που κοστίζουν το πολύ ένα ευρώ. Δείξτε ότι σίγουρα μπορούμε να βρούμε δύο διαφορετικά υποσύνολα αυτών των προϊόντων που να έχουν το ίδιο συνολικό κόστος. Λύση Κάθε προϊόν μπορεί να κοστίζει από 1 έως 100 λεπτά του Ευρώ. Υπάρχουν 2 − 1 = 1023 δυνατά μη κενά υποσύνολα προϊόντων. Το μέγιστο συνολικό κόστος όλων των προϊόντων είναι 10x100=1000 10
1023
λεπτά. Επομένως, από την αρχή του περιστερώνα, υπάρχουν τουλάχιστον = 2 διαφορετικά 1000 υποσύνολα προϊόντων με το ίδιο συνολικό κόστος
Άσκηση Φ5.39
Ένας θεατρικός οργανισμός ανεβάζει 7 διαφορετικά έργα σε μια σεζόν. Στην ομάδα συμμετέχουν 5 γυναίκες ηθοποιοί που η καθεμιά παίζει σε 3 διαφορετικά έργα. Αποδείξτε ότι σε κάποιο έργο παίζουν τουλάχιστον 3 γυναίκες Λύση Εφόσον 5 γυναίκες παίζουν σε 3 έργα έχουμε 15 γυναικείους ρόλους στα 3 έργα. Περιστέρια: οι 15 ρόλοι Περιστερώνες: Τα 7 διαφορετικά έργα της σεζόν /I
Άρα H K =3 γυναίκες τουλάχιστον παίζουν σε κάποιο από τα 7 έργα. 7 Άσκηση Φ5.40 Σε ένα παιδικό πάρτι με 28 παιδάκια ο Γιαννάκης έφαγε 13 διαφορετικά γλυκά. Ολα τα υπόλοιπα παιδιά φάγανε λιγότερα. Αποδείξτε ότι τουλάχιστον 3 παιδιά φάγανε ίδιο ποσότητα γλυκών. Λύση Έστω ότι δεν ισχύει ο ισχυρισμός και ότι το πολύ 2 παιδιά φάγανε ίδιο αριθμό γλυκών. Ορίζω σαν περιστερώνες τους 13 δυνατούς αριθμούς γλυκών (0 – 12) και περιστέρια τα παιδάκια. Αν κάθε περιστερώνας έχει το πολύ 2 παιδάκια τότε συνολικά θα είχαμε το πολύ 26 παιδιά. Αλλά τα παιδιά (χωρίς το Γιαννάκη) είναι 27. Άτοπο!
Άσκηση Φ5.41 25 αγόρια και 25 κορίτσια σχηματίζουν ένα κύκλο. Αποδείξτε ότι πάντα μπορώ να βρω κάποιον που δεξιά και αριστερά του έχει κορίτσι. Λύση Έστω ότι η κατανομή είναι τέτοια που που κανείς δεν βρίσκεται ανάμεσα σε δύο κορίτσια. Από την υπόθεσή μας δεν μπορεί να βρίσκονται περισσότερα από 2 κορίτσια συνεχόμενα. (τότε θα είχαμε ένα τουλάχιστον κορίτσι που έχει άλλα κορίτσια δίπλα του) Άρα θα έχουμε «παρέες» της μορφής ΑΚΑ ή ΑΚΚΑ (Α: αγόρι, Κ: κορίτσι). Λόγω της υπόθεσής μας ανάμεσα σ’ αυτές τις παρέες θα είναι τουλάχιστον I
2 αγόρια. Άρα έχουμε τουλάχιστον H K =13 τέτοιες παρέες με τουλάχιστον 2⋅13 = 26 αγόρια ανάμεσά τους. Τα αγόρια όμως είναι 25. Άρα η υπόθεσή μας είναι λανθασμένη και πάντα μπορούμε να βρούμε κάποιον που κάθεται ανάμεσα σε 2 κορίτσια