Guzicki W - O dwóch metodach rozwiązywania zadań.pdf

(137 KB) Pobierz
O dwóch metodach rozwiązywania zadań
Wojciech Guzicki
Wiele zadań matematycznych można rozwiązać za pomocą podobnych metod. W tym
wykładzie zostaną omówione dwie metody rozwiązywania zadań. Pierwsza z nich – me-
toda ekstremum – polega na tym, że w rozwiązaniu wybieramy obiekt najmniejszy lub
największy pod pewnym względem, a następnie, analizując jego własności, dochodzimy
do rozwiązania. Ta metoda ma więc charakter matematyczny. Druga metoda, będąca ra-
czej tzw. dyrektywą heurystyczną, pokazuje pewną ogólną strategię postępowania przy
rozwiązywaniu zadań. Strategia, która będzie tu omówiona, polega na tym, że rozwiąza-
nie zadania rozpoczynamy od przeanalizowania szeregu przykładów, dostrzeżenia pewnych
prawidłowości występujących w tych przykładach i sformułowania hipotezy. Postawienie
trafnej hipotezy, którą musimy udowodnić już w tradycyjny sposób, znacznie przybliża nas
do rozwiązania.
Pierwszą z omawianych w tym wykładzie metod rozwiązywania zadań matematycz-
nych jest tzw. metoda ekstremum. Polega ona na tym, że w rozważanej sytuacji wybieramy
obiekt największy (lub najmniejszy) pod pewnym względem. Następnie analizujemy wła-
sności tego wybranego obiektu; ta analiza doprowadza nas do rozwiązania. Bardzo często
(będzie tak w wielu przykładach, które wskażemy) przyjmujemy, że teza dowodzonego
twierdzenia nie jest prawdziwa i doprowadzamy do sprzeczności wskazując obiekt większy
(ew. mniejszy) od wybranego.
W rozwiązaniu zadania metodą ekstremum podstawowym problemem jest kwestia
istnienia obiektu największego lub najmniejszego. Na ogół istnienie tego obiektu będzie
wynikało stąd, że istnieje tylko skończenie wiele obiektów, które rozważamy. Wszystkie
niejasności najlepiej jednak wyjaśnią przykładowe zadania.
1.
Na płaszczyźnie danych jest
n
punktów. Każde trzy punkty są wierzchołkami trójkąta
o polu
≤
1. Udowodnij, że wszystkie punkty leżą w pewnym trójkącie o polu
≤
4.
Rozwiązanie.
Rozważamy wszystkie trójkąty, których wierzchołkami są trzy z roz-
ważanych
n
punktów. Oczywiście istnieje skończenie wiele takich trójkątów (z pewnością
jest ich mniej niż
n
3
). Zatem wśród tych trójkątów istnieje trójkąt o największym polu.
Niech trójkąt
ABC
ma zatem największe pole (jeśli istnieje kilka trójkątów o tym sa-
mym największym polu, to wybieramy którykolwiek z nich). Oczywiście
P
ABC
≤
1. Przez
1
2
Wojciech Guzicki
wierzchołek
C
prowadzimy prostą
m
równoległą do prostej
AB.
Wtedy wszystkie punkty
rozważanego zbioru leżą po tej samej stronie prostej
m,
co punkty
A
i
B
(z włączeniem
prostej
m).
Przypuśćmy bowiem, że pewien punkt
D
leży po przeciwnej stronie prostej
m.
D
C
m
A
B
Wówczas
P
ABD
> P
ABC
, gdyż trójkąty
ABC
i
ABD
mają wspólną podstawę
AB,
ale
wysokość trójkąta
ABD
jest większa od wysokości trójkąta
ABC.
To jednak jest sprzeczne
z wyborem trójkąta
ABC,
którego pole miało być największe. Poprowadźmy teraz prostą
k
przechodzącą przez wierzchołek
A
i równoległą do prostej
BC
oraz prostą
l
przechodzącą
przez wierzchołek
B
i równoległą do prostej
AC.
Punkty przecięcia prostych
k, l
i
m
są
wierzchołkami trójkąta
KLM
.
C
L
K
m
A
B
M
l
k
Tak jak wyżej dowodzimy, że wszystkie rozważane punkty leżą po tej stronie prostej
k
co punkty
B
i
C
oraz po tej samej stronie prostej
l
co punkty
A
i
C
(z włączeniem tych
prostych). Inaczej mówiąc, wszystkie te punkty leżą w trójkącie
KLM
(w jego wnętrzu
lub na brzegu). Do zakończenia rozwiązania wystarczy zauważyć, że
ABC
≡
KBC
≡
CAL
≡
BM A,
O dwóch metodach rozwiązywania zadań
skąd wynika, że
P
KLM
= 4
·
P
ABC
≤
4, c. b. b. o.
3
2.
(I OMG) W przestrzeni danych jest takich
n
punktów (n
≥
4), że żadne cztery nie leżą
na jednej płaszczyźnie. Każde dwa z tych punktów połączono odcinkiem niebieskim lub
czerwonym. Udowodnij, że można tak wybrać jeden z tych kolorów, aby każde dwa punkty
były połączone odcinkiem lub łamaną wybranego koloru.
Rozwiązanie.
To zadanie, pochodzące z pierwszej Olimpiady Matematycznej Gimna-
zjalistów, rozwiążemy trzema sposobami. Dwa pierwsze wykorzystują metodę ekstremum.
Sposób I.
Wybieramy punkt
A,
z którego wychodzi najwięcej odcinków jednego
koloru. Bez zmniejszenia ogólności możemy założyć, że z punktu
A
wychodzi
k
odcinków
czerwonych oraz że z żadnego punktu nie wychodzi więcej niż
k
odcinków tego samego
koloru. Niech
S
będzie zbiorem punktów połączonych czerwonym odcinkiem z punktem
A.
Jeśli
S
jest zbiorem wszystkich pozostałych punktów, to każde dwa punkty można połączyć
albo odcinkiem czerwonym, albo łamaną złożoną z dwóch odcinków czerwonych: z jednego z
tych punktów do punktu
A
i następnie z punktu
A
do drugiego z tych punktów. Przypuśćmy
zatem, że istnieje punkt
B
∈
S.
Oczywiście odcinek
AB
jest niebieski. Pokażemy, że w
zbiorze
S
istnieje punkt
C
połączony z punktem
B
odcinkem czerwonym. Wtedy punkty
A
i
B
będą połączone łamaną
ACB
złożoną z dwóch odcinków czerwonych. Zatem każdy
punkt będzie połączony z punktem
A
albo odcinkiem czerwonym, albo łamaną złożoną z
dwóch odcinków czerwonych. Stąd tak jak wyżej wynika, że każde dwa punkty są połączone
łamaną złożoną z co najwyżej czterech odcinków czerwonych.
Przypuśćmy zatem, że taki punkt
C
nie istnieje. Punkt
B
jest zatem połączony od-
cinkiem niebieskim z punktem
A
oraz z każdym punktem zbioru
C.
A więc z punktu
B
wychodzi co najmniej
k
+ 1 odcinków niebieskich. To jednak jest sprzeczne z wyborem
punktu
A.
Ta sprzeczność kończy rozwiązanie.
Sposób II.
Wybieramy punkt
A,
który jest połączony z największą liczbą punktów
łamaną złożoną z odcinków (lub tylko z jednego odcinka) jednego koloru. Dokładniej, dla
każdego punktu
P
rozważamy dwa zbiory: zbiór
C
P
punktów połączonych z punktem
P
łamaną złożoną z odcinków czerwonych oraz zbiór
N
P
punktów połączonych z punktem
P
łamaną złożoną z odcinków niebieskich. Niech
c
P
oznacza liczbę punktów w zbiorze
C
P
i
n
P
liczbę punktów w zbiorze
N
P
. Niech wreszcie
m
P
będzie większą z liczb
c
P
i
n
P
.
4
Wojciech Guzicki
Wybieramy ten punkt
A,
dla którego liczba
m
A
jest największa (taki punkt
A
istnieje, bo
mamy tylko
n
punktów, a wśród
n
liczb naturalnych istnieje liczba największa).
Bez zmniejszenia ogólności możemy założyć, że punkt
A
jest połączony z
k
punktami
łamaną złożoną z odcinków koloru czerwonego i żaden punkt nie jest połączony z większą
liczbą punktów łamaną złożoną z odcinków ustalonego koloru. Jeśli
k
=
n−1,
to znaczy, że
punkt
A
jest połączony ze wszystkimi punktami łamaną koloru czerwonego i stąd łatwo
wynika, że każde dwa punkty są połączone łamaną koloru czerwonego.
Przypuśćmy zatem, że
k <n−1,
tzn. istnieje punkt
B,
który nie jest połączony z punk-
tem
A
łamaną koloru czerwonego. Niech
S
będzie zbiorem punktów połączonych z punktem
A
łamaną koloru czerwonego. Oczywiście odcinek
AB
jest niebieski. Ponadto dla dowol-
nego punktu
C
∈
S
odcinek
BC
też jest niebieski; w przeciwnym razie punkt
A
byłby
połączony z punktem
B
łamaną czerwoną. Zatem z punktu
B
wychodzi co najmniej
k
+ 1
odcinków niebieskich (k odcinków do punktów zbioru
S
oraz odcinek
AB),
co jest sprzeczne
z wyborem punktu
A.
Ta sprzeczność kończy rozwiązanie zadania.
Sposób III.
Ten sposób nie wymaga metody ekstremum. Wybierzmy dowolny punkt
A.
Niech
S
będzie zbiorem punktów połączonych z punktem
A
łamaną złożoną z odcinków
(lub tylko z jednego odcinka) czerwonych. Jeśli do zbioru
S
należą wszystkie pozostałe
punkty, to każde dwa punkty są połączone łamaną czerwoną. Przypuśćmy zatem, że istnieje
punkt
B
∈
S.
Oczywiście odcinek
AB
jest niebieski. Pokażemy, że każde dwa punkty można
połączyć łamaną koloru niebieskiego.
Zauważmy najpierw, że jeśli
C
∈
S,
to odcinek
BC
jest niebieski. W przeciwnym razie
punkt
A
byłby połączony z punktem
B
łamaną koloru czerwonego. Stąd wynika, że jeśli
C
∈
S,
to punkty
A
i
C
można połączyć łamaną
ABC
koloru niebieskiego. Jeśli zaś
C
∈
S,
to oczywiście odcinek
AC
jest niebieski. Ponieważ każdy punkt jest połączony z punktem
A
łamaną niebieską, więc dowolne dwa punkty można połączyć łamaną tego koloru.
3.
(II OMG) W przestrzeni danych jest 6 punktów, z których żadne cztery nie leżą na
jednej płaszczyźnie. Łącząc niektóre z tych punktów narysowano 10 odcinków. Wykaż,
że w ten sposób uzyskano co najmniej jeden trójkąt.
Rozwiązanie.
Wybieramy punkt
A,
z którego wychodzi najwięcej narysowanych od-
cinków. Pokażemy najpierw, że z punktu
A
wychodzą co najmniej 4 odcinki. Przypuśćmy
O dwóch metodach rozwiązywania zadań
5
więc, że jest inaczej. Z każdego punktu wychodzą zatem co najwyżej 3 odcinki. Ponieważ
mamy 6 punktów, więc łącznie mamy co najwyżej 6
·
3 = 18 końców tych odcinków, a więc
mamy co najwyżej 9 narysowanych odcinków. To jednak jest sprzeczne z założeniem.
Z punktu
A
wychodzą zatem co najmniej 4 odcinki:
AB, AC, AD
i
AE.
Teraz zauwa-
żamy, że 6 punktów można połączyć dokładnie
6
2
=15 odcinkami. Zatem wśród 6 odcinków
BC, BD, BE, CD, CE
i
DE
narysowano co najmniej jeden. Końce tego odcinka wraz z
punktem
A
są wierzchołkami narysowanego trójkąta, c. b. d. o.
4.
(II OMG) Każdemu wierzchołkowi 100-kąta foremnego trzeba przyporządkować pew-
ną dodatnią liczbę rzeczywistą. Czy możliwe jest takie przyporządkowanie, w którym
każda liczba jest równa wartości bezwzględnej różnicy liczb, które z nią sąsiadują?
Odpowiedź uzasadnij.
Rozwiązanie.
Przypuśćmy, że takie przyporządkowanie jest możliwe. Niech
a
będzie
największą spośród liczb przyporządkowanych wierzchołkom. Niech
b
i
c
będą liczbami
przyporządkowanymi wierzchołkom sąsiednim, przy czym
b≥c.
Ponieważ
c>0,
więc
a=b−
c<b,
co jest sprzeczne z wyborem punktu
a.
Ta sprzeczność dowodzi, że przyporządkowanie
spełniające warunki zadania nie jest możliwe.
5.
W pewnym kraju jest skończona liczba miast, które połączono siecią dróg jedno-
kierunkowych. Wiadomo, że każde dwa miasta łączy pewna droga jednokierunkowa.
Udowodnij, że istnieje miasto, z którego można odbyć podróż do każdego innego mia-
sta.
Rozwiązanie.
Wybieramy miasto
A,
z którego wychodzi najwięcej bezpośrednich
dróg do innych miast. Niech
S
będzie zbiorem wszystkich miast, do których można doje-
chać z miasta
A
bezpośrednią drogą. Jeśli każde miasto (oprócz
A)
należy do zbioru
S,
to
A
jest szukanym miastem. W przeciwnym razie bierzemy dowolne miasto
B
∈
S.
Oczy-
wiście z miasta
B
wychodzi bezpośrednia droga do miasta
A.
Pokażemy, że w zbiorze
S
istnieje miasto
C,
z którego prowadzi bezpośrednia droga do
B
(a więc z miasta
A
można
dojechać do
B
przez miasto
C).
Gdyby bowiem tak nie było, to z miasta
B
prowadziłaby
bezpośrednia droga do każdego miasta ze zbioru
S
oraz do miasta
A,
czyli co najmniej
o jedną drogę więcej niż z miasta
A.
To jednak przeczy temu, że z miasta
A
wychodzi
najwięcej dróg. Ta sprzeczność kończy dowód twierdzenia.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin