XLII OM - II etap

II etap XLII Olimpiady Matematycznej

XLII OM - II - Zadanie 1

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Liczby $a_i$ , $b_i$ , $c_i$ , $d_i$ spełniają warunki $0\leq c_i \leq a_i \leq b_i \leq d_i$ oraz $a_i+b_i = c_i+d_i$ dla $i=1,2,\ldots,n$ . Udowodnić, że

$ \prod_{i=1}^n a_i + \prod_{i=1}^n b_i \leq \prod_{i=1}^n c_i + \prod_{i=1}^n d_i $

Rozwiązanie

Indukcja. Dla $n = 1$ dana do udowodnienia nierówność zachodzi (ze znakiem równości; bowiem $a_1+b_1 =c_1+d_1$ , zgodnie z założeniem).

Ustalmy liczbę naturalną $n \geq 1$ i przyjmijmy słuszność podanego twierdzenia dla tej właśnie liczby $n$ . Mamy wykazać jego słuszność dla $n + 1$ .

Niech więc dane będą liczby $a_i$ , $b_i$ , $c_i$ , $d_i$ ( $i = 1,\ldots,n +1$ ) spełniające warunki $0 \leq c_i \leq a_i \leq b_i \leq d_i$ oraz $a_i + b_i= c_i + d_i$ . Oznaczmy

$ A = \prod_{i=1}^n a_i, \quad B = \prod_{i=1}^n b_i, \quad C = \prod_{i=1}^n c_i, \quad D = \prod_{i=1}^n d_i. $

Z założenia indukcyjnego mamy nierówność $A + B \leq C + D$ , czyli

$ (1) \qquad A-C \leq D-B; $

mamy zaś dowieść, że

$ (2) \qquad Aa_{n+1} + Bb_{n+1 } \leq Cc_{n+1} + Dd_{n+1}. $

Na mocy warunków spełnianych przez liczby $a_i$ , $b_i$ , $c_i$ , $d_i$ zachodzą następujące równości i nierówności:

$ \begin{split} (3) \qquad a_{n+1}-c_{n+1} & =d_{n+1}-b_{n+1},\\ (4) \qquad a_{n+1} & \leq b_{n+1}, \\ (5) \qquad C & \leq D, \end{split} $

przy czym wyrażenia występujące po obu stronach każdej z relacji (1), (3), (4), (5) są nieujemne. Nierówności zgodnie skierowane, wiążące liczby nieujemne, wolno mnożyć stronami. Mnożymy więc stronami (1) przez (4) oraz (3) przez (5):

$ \begin{split} (A-C)a_{n+1} & \leq (D-B)b_{n+1},\\ (a_{n+1}- c_{n+1})C & \leq (d_{n+1} - b_{n+1})D. \end{split} $

Otrzymane nierówności dodajemy:

$ Aa_{n+1} -Cc_{n+1} \leq Dd_{n+1}- Bb_{n+1}. $

Uzyskaliśmy tezę indukcyjną (2).

Na mocy zasady indukcji twierdzenie zachodzi dla dowolnej liczby naturalnej $n$ .

XLII OM - II - Zadanie 2

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Na bokach $BC$ , $CA$ , $AB$ trójkąta $ABC$ obrano odpowiednio takie punkty $D$ , $E$ , $F$ , że

$ \frac{|DB|}{|DC|} = \frac{|EC|}{|EA|} = \frac{|FA|}{|FB|} $

Dowieść, że jeżeli trójkąt $DEF$ jest równoboczny, to także trójkąt, $ABC$ jest równoboczny.

Rozwiązanie

Oznaczmy wspólną wartość podanych stosunków przez $\lambda$ :

$ (1) \qquad \frac{|DB|}{|DC|} = \frac{|EC|}{|EA|} = \frac{|FA|}{|FB|} = \lambda. $

Zakładamy, że trójkąt $DEF$ jest równoboczny. Przedstawimy dowód foremności trójkąta $ABC$ , zachęcając Czytelnika do znajdowania innych metod rozwiązania (np. przez rachunki na wektorach; na liczbach zespolonych; przez porównywanie różnych kątów; itd.).

Użyjemy pojęcia i własności przekształceń afinicznych (por. np.: J. Bednarczuk, Urok przekształceń afinicznych, Warszawa 1978).

Istnieje przekształcenie afiniczne $h$ przeprowadzające trójkąt $ABC$ na pewien trójkąt równoboczny $A'B'C'$ . Przekształcenie afiniczne zachowuje współliniowość punktów oraz stosunek podziału odcinka. Zatem punkty $D'=h(D)$ , $E'=h(E)$ , $F' = h(F)$ leżą na bokach $B'C'$ , $C'A'$ , $A'B'$ trójkąta $A'B'C'$ i dzielą je w tych samych stosunkach, w jakich punkty $D$ , $E$ , $F$ dzielą boki trójkąta $ABC$ - czyli w równych stosunkach. Stąd wniosek, że trójkąt $D'E'F'$ jest równoboczny.

Istnieje w takim razie podobieństwo $g$ takie, że $g(D) = D'$ , $g(E)= E'$ , $g(F)=F'$ . Obrazy punktów $D$ , $E$ , $F$ są w obu tych przekształceniach ( $g$ i $h$ ) takie same. Ale przekształcenie afiniczne jest wyznaczone jednoznacznie przez swe wartości w dowolnych trzech niewspółliniowych punktach. To znaczy, że rozważane tu przekształcenia $g$ i $h$ są tym samym przekształceniem - czyli że $h$ jest podobieństwem.

Obrazem trójkąta $ABC$ w przekształceniu $h$ jest trójkąt równoboczny $A'B'C'$ . Skoro zaś $h$ jest podobieństwem, zatem i trójkąt $ABC$ jest równoboczny.

XLII OM - II - Zadanie 3

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Dane są liczby całkowite dodatnie $a$ , $b$ , $c$ , $d$ , $e$ , $f$ takie, że $a+b = c+d = e+f = 101$ . Udowodnić, że liczby $\frac{ace}{bdf}$ nie można zapisać w postaci ułamka $\frac{m}{n}$ gdzie $m$ , $n$ są liczbami całkowitymi dodatnimi o sumie mniejszej od $101$ .

Rozwiązanie

Z założenia zadania wynika, że zachodzą kongruencje

$ a \equiv -b, \quad c \equiv -d, \quad e \equiv -f \pmod{101}. $

Mnożymy te trzy związki stronami:

$ ace \equiv -bdf \pmod{101}. $

Przypuśćmy, wbrew tezie, że

$ \frac{ace}{bdf} = \frac{m}{n}, $

gdzie $m$ , $n$ są liczbami całkowitymi dodatnimi takimi, że $m + n< 101$ . Mamy więc zależność

$ mbdf = nace \equiv -nbdf \pmod{101}, $

czyli

$ (m + n)bdf \equiv 0 \pmod{101}. $

To znaczy, że liczba $101$ jest dzielnikiem iloczynu $(m + n)bdf$ . Musi więc, jako liczba pierwsza, dzielić któryś z czynników. Otrzymaliśmy sprzeczność, bo każda z liczb $b$ , $d$ , $f$ , $m + n$ jest dodatnia oraz mniejsza od $101$ . Sprzeczność kończy dowód.

Uwaga 1. W udowodnionym twierdzeniu można oczywiście zastąpić liczbę $101$ dowolną liczbą pierwszą, a zamiast trzech ułamków - rozpatrywać dowolną nieparzystą liczbę ułamków.

Uwaga 2. Użycie języka i własności kongruencji jest w rozwiązaniu wygodne, ale nie jest niezbędne; były one przydatne do uzasadnienia podzielności iloczynu $(m + n)bdf$ przez $101$ .

Konkluzję tę można, nie używając pojęcia kongruencji, uzyskać następująco: w myśl założenia, $a = p - b$ , $c = p- d$ , $e = p - f$ (rozumowanie prowadzimy od razu dla dowolnej liczby pierwszej $p$ , zgodnie z Uwagą 1). Zatem

$ ace = (p-b)(p-d)(p-f) = p^3 - (b + d+f)p^2 +(df + fb + bd)p-bdf. $

Zakładając, jak poprzednio, że $mbdf = nace$ , mamy

$ (m + n)bdf = n(ace +bdf) = np(p^2 -(b + d + f)p + (df + fb + bd)). $

Prawa strona tej równości jest liczbą podzielną przez $p$ , więc lewa też.

XLII OM - II - Zadanie 4

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Znaleźć wszystkie funkcje monotoniczne $f: \mathbb{R} \to \mathbb{R}$ spełniające równanie

$ f(4x)-f(3x) = 2x \quad \text{ dla } \quad x \in \mathbb{R}. $

Rozwiązanie

Sposób I

Dla dowolnego $x > 0$ mamy nierówność $f(4x) - f(3x) > 0$ , z której wynika, że funkcja (monotoniczna) $f$ jest rosnąca w przedziale $(0;\infty)$ . Analogicznie, dla $x < 0$ zachodzi nierówność $f(3x) -f(4x) > 0$ , więc $f$ jest rosnąca także w $(-\infty;0)$ .

Zastępując $4x$ literą $z$ przepisujemy podane równanie jako

$ (1) \qquad f(z) = \tfrac{1}{2} z + f\left(\tfrac{3}{4}z\right) \ \textrm{dla}\ z \in \mathbf{R}. $

Weźmy dowolną liczbę $x \ne 0$ oraz dowolną liczbę naturalną $n$ . Stosując $n$ -krotnie wzór (1) otrzymujemy równość

$ \begin{split} f(x) & = \tfrac{1}{2}x + f(\tfrac{3}{4}x)=\\ & = \tfrac{1}{2}x + \tfrac{1}{2} \cdot \tfrac{3}{4}x + f((\tfrac{3}{4})^2x) =\\ & = \tfrac{1}{2}x + \tfrac{1}{2} \cdot \tfrac{3}{4}x + \tfrac{1}{2} \cdot ( \tfrac{3}{4})^2 x + f((\tfrac{3}{4})^3x) =\\ & = \ldots = \\ & = \tfrac{1}{2}x + \tfrac{1}{2} \cdot \tfrac{3}{4}x + \tfrac{1}{2} \cdot ( \tfrac{3}{4})^2 x + \ldots + \tfrac{1}{2} \cdot (\tfrac{3}{4})^{n-1}x + f((\tfrac{3}{4})^nx) =\\ & = \tfrac{1}{2} x \cdot \tfrac{1-\left(\tfrac{3}{4}\right)^n}{1-\tfrac{3}{4}} + f((\tfrac{3}{4})^nx), \end{split} $

czyli

$ (2) \qquad f(x)= 2x\left(1-\left(\tfrac{3}{4}\right)^n\right) + f\left(\left(\tfrac{3}{4}\right)^nx\right). $

Chcemy teraz przejść z $n$ do nieskończoności. Dla $x > 0$ ciąg $((\frac{3}{4})^nx)$ jest malejący, więc i ciąg wartości $f((\frac{3}{4})^nx)$ jest malejący, a ponadto ograniczony z dołu przez wartość $f(0)$ (w tym miejscu korzystamy z założenia monotoniczności funkcji $f$ w całym zbiorze $\mathbf{R}$ ). Podobnie, dla $x < 0$ ciąg $((\frac{3}{4})^nx)$ jest rosnący, więc i ciąg $(f(\frac{3}{4})^n x)$ jest rosnący, ograniczony z góry przez $f(0)$ . W każdym przypadku ciąg ten jest zbieżny. Jego granica może {\it a priori} zależeć od $x$ ; oznaczmy jej wartość przez $g(x)$ :

$ g(x) = \lim_{n \to \infty} f\left(\left(\tfrac{3}{4}\right)^nx\right). $

Przypuśćmy, że dla pewnych dwóch liczb dodatnich $u$ , $v$ zachodzi nierówność

$ g(u) < g(v). $

Weźmy liczbę $\varepsilon$ taką, że

$ (3) \qquad 0<\varepsilon < \tfrac{1}{2}(g(v)-g(u)). $

W myśl definicji granicy ciągu,

$ (4) \qquad f\left(\left(\tfrac{3}{4}\right)^nu\right)<g(u) + \varepsilon \quad \textrm{dla dostatecznie dużych} \ n $

oraz

$ (5) \qquad f\left(\left(\tfrac{3}{4}\right)^nv\right)>g(v) - \varepsilon \quad \textrm{dla dostatecznie dużych} \ n. $

Znajdujemy teraz liczbę naturalną $k$ tak dużą, żeby dla $n = k$ zachodziła nierówność (4). Następnie znajdujemy liczbę naturalną $m$ tak dużą, żeby dla $n = m$ zachodziła nierówność (5) oraz, ponadto, żeby było

$ (6) \qquad \left(\tfrac{3}{4}\right)^mv < \left(\tfrac{3}{4}\right)^ku. $

Mamy wówczas (wobec (3))

$ f\left(\left(\tfrac{3}{4}\right)^{m\vphantom{k}} v\right)- f\left(\left(\tfrac{3}{4}\right)^k u\right) > (g(v)-\varepsilon)-(g(u) + \varepsilon) = g(v)-g(u) - 2\varepsilon > 0. $

To się jednak kłóci z nierównością (6); pamiętamy, że funkcja $f$ jest rosnąca w $(0;\infty)$ .

Otrzymana sprzeczność dowodzi, że nierówność $g(u)<g(v)$ nie jest możliwa dla żadnej pary liczb $u, v > 0$ . Stąd wniosek, że wartość $g(x)$ jest ta sama dla wszystkich $x > 0$ . Oznaczmy tę wartość przez $c$ . Zatem

$ (7) \qquad \lim_{n \to \infty} f\left(\left(\tfrac{3}{4}\right)^nx\right) = c \quad \textrm{dla} \ x > 0. $

Zupełnie analogicznie dowodzimy, że wartość granicy $g(x)$ jest wspólna dla wszystkich $x < 0$ . Oznaczając ją przez $a$ mamy więc

$ (8) \qquad \lim_{n \to \infty} f\left(\left(\tfrac{3}{4}\right)^nx\right) = a \quad \textrm{dla} \ x < 0. $

Możemy teraz we wzorze (2) przejść do granicy (gdy $n \to \infty$ ). Otrzymujemy

$ f(x) = 2x+a \ \textrm{dla} \ x < 0 \quad \textrm{oraz} \quad f(x) = 2x + c \ \textrm{dla} \ x > 0. $

Z uwagi na żądanie monotoniczności funkcji $f$ na zbiorze $\mathbf{R}$ , musi zachodzić nierówność $a \leq c$ , zaś wartość $f(0)$ musi leżeć między $a$ i $c$ . Ostatecznie więc

$ (9) \qquad f(x) = \left\{ \begin{array}{lcl} 2x+a & \textrm{dla} & x<0, \\ b & \textrm{dla} & x=0, \\ 2x+c & \textrm{dla} & x>0, \end{array} \right. $

gdzie $a$ , $b$ , $c$ są dowolnymi stałymi takimi, że $a \leq b \leq c$ .

Sprawdzenie, że istotnie każda funkcja tej postaci spełnia podane równanie funkcyjne, jest natychmiastowe.

Sposób II

Rozwiązanie zadania można znacznie uprościć korzystając z twierdzenia analizy, które mówi, że

jeśli funkcja $f$ jest ograniczona i rosnąca w pewnym przedziale $(\alpha;\beta)$ , to istnieją skończone granice jednostronne

$ \lim_{x \to \alpha+} f(x) \quad \textrm{oraz} \quad \lim_{x \to \beta-} f(x). $

(Dowód można znaleźć w dowolnym uniwersyteckim podręczniku analizy matematycznej.)

W rozważanym zadaniu rozpoczynamy (jak w sposobie I) od stwierdzenia, że $f$ jest funkcją rosnącą dla $x > 0$ i dla $x < 0$ . Ponadto z założenia monotoniczności $f$ na zbiorze $\mathbf{R}$ mamy

$ f(x) \geq f(0) \ \textrm{dla} \ x>0 \quad \textrm{oraz} \quad f(x) \leq f(0) \ \textrm{dla} \ x < 0. $

Biorąc więc jako przedział $(\alpha;\beta)$ w cytowanym wyżej twierdzeniu najpierw przedział $(0;1)$ , a następnie $(-1;0)$ , widzimy, że funkcja $f$ jest w każdym z tych przedziałów rosnąca i ograniczona, i wobec tego istnieją skończone granice

$ (10) \qquad a = \lim_{x \to 0-} f(x), \quad c = \lim_{x \to 0+} f(x). $

Oczywiście monotoniczność funkcji $f$ na $\mathbf{R}$ pociąga za sobą nierówność $a \leq c$ . Oznaczając $f(0)$ przez $b$ , jak poprzednio, mamy $a \leq b \leq c$ .

Dalej można powtórzyć pierwszy sposób rozwiązania, pomijając cały fragment środkowy (od wzoru (2) do wzorów (7) i (8)). Można też, zamiast tego, rozumować następująco:

Określamy funkcję $h: \mathbf{R} \to \mathbf{R}$ wzorem

$ (11) \qquad h(x) = f(x)-2x. $

Z istnienia granic (10) wynika, że również

$ (12) \qquad \lim_{x \to 0-} h(x) =a, \quad \lim_{x \to 0+} h(x) = c. $

Dane w zadaniu równanie funkcyjne przybiera postać

$ (h(4x) + 2(4x))-(h(3x)+2(3x)) = 2x, $

czyli po prostu

$ h(4x) = h(3x) \quad \textrm{dla}\ x \in \mathbf{R}, $

lub pisząc inaczej:

$ h(z) = h(\tfrac{3}{4}z) \quad \textrm{dla}\ z \in \mathbf{R}. $

Dla dowolnej liczby rzeczywistej $x$ i dla dowolnej liczby naturalnej $n$ mamy zatem

$ h(x) = h(\tfrac{3}{4}x) = h((\tfrac{3}{4})^2x)=h((\tfrac{3}{4})^3x) = \ldots = h((\tfrac{3}{4})^nx). $

Gdy $n$ dąży do nieskończoności, ciąg $h((\frac{3}{4})^nx)$ dąży - zgodnie z (12) - do wartości $a$ , jeśli $x$ jest ujemne, oraz do wartości $c$ , jeśli $x$ jest dodatnie; dla $x=0$ ciąg ten jest stały, równy $b$ . W granicy otrzymujemy więc równość

$ h(x) = \left\{\begin{array}{ccl} a &\textrm{dla} & x < 0,\\ b &\textrm{dla} & x = 0,\\ c &\textrm{dla} & x > 0. \end{array} \right. $

Po uwzględnieniu definicji (11) dostajemy stąd wzór (9), przedstawiający ogólne rozwiązanie rozważanego równania funkcyjnego w klasie funkcji monotonicznych.

XLII OM - II - Zadanie 5

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

$P_1, P_2, \ldots, P_n$ są różnymi podzbiorami dwuelementowymi zbioru $\{1,2,\ldots,n\}$ . Zbiory $P_i$ , $P_j$ dla $i\neq j$ mają element wspólny wtedy i tylko wtedy, gdy zbiór $\{i,j\}$ jest jednym ze zbiorów $P_1, P_2, \ldots, P_n$ . Dowieść, że każda z liczb $1,2,\ldots,n$ jest elementem wspólnym dokładnie dwóch zbiorów spośród $P_1, P_2, \ldots, P_n$ .

Rozwiązanie

Dla każdego $k \in \{1,2,\ldots,n\}$ oznaczmy przez $m_k$ liczbę tych zbiorów $P_i$ , które zawierają element $k$ . Suma tych liczb (gdy $k$ przebiega wartości od $1$ do $n$ ) równa się $2n$ , bo każdy ze zbiorów $P_1,\ldots, P_n$ ma dwa elementy, jest więc liczony dwukrotnie. Mamy zatem równość

$ (1) \qquad \sum_{k=1}^n m_k = 2n. $

Należy zaś udowodnić, że $m_k=2$ dla $k = 1, \ldots, n$ .

Zgodnie z warunkiem zadania, rozważana rodzina $n$ zbiorów $P_1,\ldots, P_n$ składa się dokładnie z tych par $\{i,j\}$ elementów zbioru $\{1,2,\ldots,n\}$ , dla których zbiory $P_i$ , $P_j$ mają wspólny element. Tym wspólnym elementem może być dowolna liczba $k \in \{1,2,\ldots,n\}$ . Dla ustalonego $k$ istnieje $m_k$ zbiorów $P_i$ zawierających $k$ ; istnieje więc

$ (2) \qquad \binom{m_k}{2} = \frac{m_k(m_k-1)}{2} $

par $\{ i,j \}$ takich, że $P_i \cap P_j = \{k\}$ . Liczba wszystkich rozważanych par jest sumą wyrażeń (2) gdy $k$ przebiega wartości od $1$ do $n$ . Ponieważ każda taka para $\{i,j\}$ jest jednym ze zbiorów $P_1,\ldots, P_n$ , liczba tych par wynosi $n$ . Otrzymujemy równość

$ n = \sum_{k=1}^n \binom{m_k}{2} = \frac{1}{2} \sum_{k=1}^n m_k(m_k-1), $

czyli

$ \sum_{k=1}^n m_k^2 - \sum_{k=1}^n m_k =2n. $

Stąd, wobec (1),

$ (3) \qquad \sum_{k=1}^n m_k^2 = 4n. $

Chcemy dowieść, że wszystkie liczby $m_k$ równają się $2$ . Rozważmy wobec tego różnice $m_k - 2$ . Obliczmy sumę kwadratów tych różnic, korzystając ze związków (1) i (3):

$ \sum_{k=1}^n (m_k-2)^2 = \sum_{k=1}^n m_k^2 - 4 \sum_{k=1}^n m_k + 4\sum_{k=1}^n 1 = 4n-8n+4n=0. $

Suma liczb nieujemnych równa się zeru tylko wtedy, gdy wszystkie te liczby są zerami. Zatem $m_1 = \ldots = m_n = 2$ .

To znaczy, że każda liczba $k \in \{1,2,\ldots,n\}$ należy do dokładnie dwóch
zbiorów $P_i$ . Dowód jest zakończony.

Uwaga 1. Modyfikując przekształcenie zastosowane w końcówce rozwiązania łatwo możemy otrzymać dowód nierówności między {\it średnią arytmetyczną}

$ A(x_1, \ldots, x_n) = \frac{1}{n} \sum_{k=1}^n x_k $

układu liczb $x_1,\ldots,x_n \geq 0$ a {\it średnią kwadratową} tych liczb, określoną wzorem

$ Q(x_1, \ldots, x_n) = \sqrt{\frac{1}{n} \sum_{k=1}^n x_k^2}. $

Pisząc krótko $A$ i $Q$ zamiast $A(x_1,\ldots,x_n)$ i $Q(x_1,\ldots,x_n)$ mamy:

$ \begin{split} 0 & \leq \sum_{k=1}^n (x_k - A)^2 =\sum_{k=1}^n x_k^2 - 2A \sum_{k=1}^n x_k + \sum_{k=1}^n A^2=\\ & = nQ^2 - 2A \cdot nA + nA^2 = n(Q^2-A^2) = n(Q+A)(Q-A), \end{split} $

skąd

$ (4) \qquad Q(x_1, \ldots, x_n) \geq A(x_1, \ldots, x_n); $

równość zachodzi tylko dla $x_1 = \ldots = x_n = A$ .

Na odwrót: przyjmując nierówność (4) (wraz z informacją, kiedy przechodzi ona w równość) za fakt znany, możemy dowodzoną tezę ( $m_1 = \ldots = m_n = 2$ ) wydedukować natychmiast z wzorów (1) i (3).

Uwaga 2. W tym zadaniu mamy do czynienia z parą $(V,E)$ , gdzie $V$ jest zbiorem $\{1,2,\ldots,n\}$ , a $E$ jest rodziną zbiorów dwuelementowych $P_1,\ldots,P_n$ , z których każdy jest zawarty w $V$ . Tego typu konfiguracja tworzy graf. Ogólnie, {\it grafem} nazywamy parę $(V,E)$ , gdzie $V$ jest dowolnym zbiorem, a $E$ jest pewną rodziną wyróżnionych dwuelementowych podzbiorów $V$ . (W zastosowaniach najczęściej $V$ jest zbiorem skończonym.) Wygodnie jest interpretować $V$ jako pewien zbiór punktów (na płaszczyźnie lub w przestrzeni), a każdy zbiór dwuelementowy $\{u,v\}$ należący do rodziny $E$ - jako odcinek łączący punkty $u$ i $v$ . Taka interpretacja uzasadnia stosowaną w teorii grafów terminologię: elementy zbioru $V$ nazywa się wierzchołkami rozważanego grafu, a elementy zbioru $E$ - jego krawędziami (por. zadanie 4 z XXXII Międzynarodowej Olimpiady Matematycznej).

Liczbę krawędzi, których końcem jest ustalony wierzchołek grafu, nazywa się {\it krotnością} tego wierzchołka.

Dwie krawędzie grafu nazywamy przyległymi, jeśli mają wspólny koniec. Dwa wierzchołki grafu nazywamy przyległymi, jeśli łączy je pewna krawędź.

Należy podkreślić, że taka interpretacja ma jedynie ułatwiać wyobrażanie sobie danych zbiorów i ich wzajemnych relacji (o charakterze mnogościowo-kombinatorycznym); nie ma w tym żadnej ,,geometrii''. Abstrahuje się od długości krawędzi i kątów między nimi oraz ich ewentualnych przecięć poza wierzchołkami grafu. Na przykład graf $(V_1,E_1)$ , gdzie $V_1$ jest zbiorem wierzchołków kwadratu, a $E_1$ składa się z jego trzech boków oraz obu przekątnych, jest nieodróżnialny od grafu $(V_2, E_2)$ , gdzie $V_2$ jest zbiorem wierzchołków czworościanu, a $E_2$ - zbiorem dowolnych jego pięciu krawędzi.

Twierdzenie podane do udowodnienia w tym zadaniu formułuje się w języku grafów następująco:

Dany jest graf $(V,E)$ , w którym zbiory $V$ i $E$ mają jednakową, skończoną liczbę elementów, ponumerowanych liczbami naturalnymi od $1$ do $n$ . Dla każdej pary różnych liczb naturalnych $i,j \in \{1,2,\ldots,n\}$ wierzchołki o numerach $i$ , $j$ są przyległe wtedy i tylko wtedy, gdy krawędzie o numerach $i$ , $j$ są przylegle. Przy tych założeniach krotność każdego wierzchołka wynosi $2$ .

XLII OM - II - Zadanie 6

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Równoległościan zawiera kulę o promieniu $r$ i jest zawarty w kuli o promieniu $R$ . Dowieść, że $\frac{R}{r} \geq \sqrt{3}$ .

Rozwiązanie

Wybierzmy dowolną ścianę równoległościanu i oznaczmy jej wierzchołki przez $A$ , $B$ , $C$ , $D$ tak, by odcinek $AC$ był dłuższą (tzn.: ,,nie krótszą'') przekątną równoległoboku $ABCD$ . Pozostałe wierzchołki równoległościanu oznaczmy przez $E$ , $F$ , $G$ , $H$ tak, by odcinki $AE$ , $BF$ , $CG$ , $DH$ były jego czterema równoległymi krawędziami (rysunek 8). Przyjmijmy wreszcie, że $AG$ jest dłuższą przekątną równoległoboku $ACGE$ ; jeśli jest przeciwnie, zamieniamy oznaczenia: $A \longleftrightarrow C$ , $E \longleftrightarrow G$ .

Z takiego ustalenia oznaczeń wynika, że $|\measuredangle ABC| \geq 90^\circ$ , $|\measuredangle ACG| \geq 90^\circ$ . Stosując do trójkątów $ACG$ i $ABC$ wzór cosinusów dostajemy związek

$ \begin{split} |AG|^2 & = |AC|^2 + |CG|^2 -2\cdot |AC|\cdot |CG| \cdot \cos(\measuredangle ACG) \geq |AC|^2 + |CG|^2 = \\ & = (|AB|^2 + |BC|^2 -2 \cdot |AC| \cdot |BC|\cdot \cos(\measuredangle ABC)) +|CG|^2 \geq \\ & \geq |AB|^2 + |BC|^2 + |CG|^2. \end{split} $

Zauważmy, że każdy z odcinków $AB$ , $BC$ , $CG$ ma końce położone na pewnych dwóch równoległych ścianach równoległościanu $ABCDEFGH$ . Skoro zaś równoległościan zawiera kulę o promieniu $r$ , odległość każdej pary ścian równoległych jest nie mniejsza niż $2r$ . Wobec tego mamy nierówności

$ |AB| \geq 2r, \quad |BC| \geq 2r, \quad |CG| \geq 2r. $

Z drugiej strony, długość przekątnej $AG$ nie przekracza średnicy kuli, w której równoległościan jest zawarty: $|AG| \leq 2R$ . Uwzględniając wszystkie te nierówności dochodzimy do wniosku, że $(2R)^2 \geq (2r)^2 + (2r)^2 + (2r)^2$ , a stąd $R^2 \geq 3r^2$ , czyli $R/r \geq \sqrt{3}$ .

Uwaga. Wielu uczestników Olimpiady rozpoczynało rozwiązanie od wybrania takiego wierzchołka równoległościanu, że trzy ściany spotykające się przy tym wierzchołku mają przy nim kąty ostre (lub proste). Otóż wierzchołek taki może nie istnieć; dzieje się tak wówczas, gdy istnieje wierzchołek, przy którym kąty płaskie trzech ścian równoległościanu są rozwarte.