Użytkownicy online
Naszą witrynę przegląda teraz 2 gości| Eliminacje do konkursu PTM dla klas pierwszych -- wersja 2 |
 |
 |
 |
| Zadania I |
| Wpisany przez Joachim Jelisiejew |
| sobota, 08 maja 2010 18:27 |
|
Źródło zadań w texu. % File: zad2.tex % Created: wto kwi 27 09:00 2010 C % Last Change: wto kwi 27 09:00 2010 C \documentclass[10pt]{article} \usepackage{amssymb} \usepackage{amsmath} \textwidth 16cm \textheight 24cm \oddsidemargin 0cm \topmargin 0pt \headheight 0pt \headsep 0pt \usepackage[polish]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{import} %\usepackage{MnSymbol} % ---------------------------------------------------------------- \vfuzz4pt % Don't report over-full v-boxes if over-edge is small \hfuzz4pt % Don't report over-full h-boxes if over-edge is small % THEOREMS ------------------------------------------------------- \newtheorem{thm}{Twierdzenie}[section] \newtheorem{cor}[thm]{Wniosek} \newtheorem{lem}[thm]{Lemat} \newtheorem{defn}[thm]{Definicja} \newtheorem{tozs}[thm]{Tożsamość} \newtheorem{hyp}[thm]{Hipoteza} \newtheorem{useless}[thm]{} \newtheorem{problem}[thm]{Zadanie} \newenvironment{proof}{\noindent\textsc{Dowód.}} {\nolinebreak[4]\hfill$\blacksquare$\\\par} \newenvironment{sol}{\noindent\textsc{Rozwiązanie. }} {\par} \def\rozw{$ $\\\textbf{Rozwiązanie}: \\} \def\deg{^{\circ}} \subimport{../}{style} %\include{style} \def\source#1{\\Źródło: #1} \begin{document} \section{Eliminacje do PTM} \begin{enumerate} \item Dany jest graf nieskierowany, prościej mówiąc wierzchołki połączone krawędziami (co najwyżej jedna krawędź pomiędzy dwoma różnych wierzchołkami, nie ma krawędzi prowadzących z wierzchołka do tego samego wierzchołka). \emph{Stopniem} wierzchołka nazywamy ilość krawędzi wychodzących z tego wierzchołka. Uzasadnić, że pewne dwa wierzchołki mają ten sam stopień. \item Uzasadnij, że liczba postaci $8k-1$ gdzie $k\in \mathbb{Z}$ nie może być przedstawiona w postaci sumy trzech kwadratów liczb całkowitych. \item Udowodnić, że dla dowolnej liczby naturalnej $n$ część całkowita liczby $$\frac{n^2 + n}{3}$$ jest parzysta. \item Dane są okręgi $O_1, O_2$, przecinające się w punktach $A,B$. Punkt $P$ leży na prostej $AB$, proste $PX$, $PY$ są styczne do $O_1$, $O_2$ odpowiednio. Uzasadnić, że $|PX| = |PY|$. \end{enumerate} \vskip 2cm \section{Eliminacje do PTM} \begin{enumerate} \item Dany jest graf nieskierowany, prościej mówiąc wierzchołki połączone krawędziami (co najwyżej jedna krawędź pomiędzy dwoma różnych wierzchołkami, nie ma krawędzi prowadzących z wierzchołka do tego samego wierzchołka). \emph{Stopniem} wierzchołka nazywamy ilość krawędzi wychodzących z tego wierzchołka. Uzasadnić, że pewne dwa wierzchołki mają ten sam stopień. \item Uzasadnij, że liczba postaci $8k-1$ gdzie $k\in \mathbb{Z}$ nie może być przedstawiona w postaci sumy trzech kwadratów liczb całkowitych. \item Udowodnić, że dla dowolnej liczby naturalnej $n$ część całkowita liczby $$\frac{n^2 + n}{3}$$ jest parzysta. \item Dane są okręgi $O_1, O_2$, przecinające się w punktach $A,B$. Punkt $P$ leży na prostej $AB$, proste $PX$, $PY$ są styczne do $O_1$, $O_2$ odpowiednio. Uzasadnić, że $|PX| = |PY|$. \end{enumerate} \end{document}
Źródło rozwiązań w texu. % File: zad2.tex % Created: wto kwi 27 09:00 2010 C % Last Change: wto kwi 27 09:00 2010 C \documentclass[10pt]{article} \usepackage{amssymb} \usepackage{amsmath} \textwidth 16cm \textheight 24cm \oddsidemargin 0cm \topmargin 0pt \headheight 0pt \headsep 0pt \usepackage[polish]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{import} %\usepackage{MnSymbol} % ---------------------------------------------------------------- \vfuzz4pt % Don't report over-full v-boxes if over-edge is small \hfuzz4pt % Don't report over-full h-boxes if over-edge is small % THEOREMS ------------------------------------------------------- \newtheorem{thm}{Twierdzenie}[section] \newtheorem{cor}[thm]{Wniosek} \newtheorem{lem}[thm]{Lemat} \newtheorem{defn}[thm]{Definicja} \newtheorem{tozs}[thm]{Tożsamość} \newtheorem{hyp}[thm]{Hipoteza} \newtheorem{useless}[thm]{} \newtheorem{problem}[thm]{Zadanie} \newenvironment{proof}{\noindent\textsc{Dowód.}} {\nolinebreak[4]\hfill$\blacksquare$\\\par} \newenvironment{sol}{\noindent\textsc{Rozwiązanie. }} {\par} \def\rozw{$ $\\\textbf{Rozwiązanie}: \\} \def\deg{^{\circ}} \def\floor#1{\left\lfloor #1\right\rfloor} \subimport{../}{style} %\include{style} \def\source#1{\\Źródło: #1} \begin{document} \section{Eliminacje do PTM} \begin{enumerate} \item Dany jest graf nieskierowany, prościej mówiąc wierzchołki połączone krawędziami (co najwyżej jedna krawędź pomiędzy dwoma różnych wierzchołkami, nie ma krawędzi prowadzących z wierzchołka do tego samego wierzchołka). \emph{Stopniem} wierzchołka nazywamy ilość krawędzi wychodzących z tego wierzchołka. Uzasadnić, że pewne dwa wierzchołki mają ten sam stopień. \begin{proof} Załóżmy, że graf ma $n \geq 1$ wierzchołków. Zauważmy, że z warunków zadania wynika, że wierzchołek może mieć stopień $$0,1,\dots,n-1$$ Rozważmy dwa przypadki: \begin{enumerate} \item Istnieje wierzchołek stopnia $0$. Wierzchołek stopnia $0$ nie jest połączony z żadnym wierzchołkiem, więc żaden wierzchołek nie jest połączony z nim, czyli nie istnieje wierzchołek stopnia $n-1$. Mamy $n$ wierzchołków i $n-1$ możliwych stopni: $0,1,\dots,n-2$. Któreś dwa wierzchołki muszą mieć ten sam stopień. \item Analogicznie jak w przypadku poprzednim -- mamy $n$ wierzchołków i $n-1$ możliwych stopni: $1,2,\dots,n-1$. \end{enumerate} $ $ \end{proof} \item Uzasadnij, że liczba postaci $8k-1$ gdzie $k\in \mathbb{Z}$ nie może być przedstawiona w postaci sumy trzech kwadratów liczb całkowitych. \begin{proof} Kwadraty liczb całkowitych dają reszty $0,1,4$ z dzielenia przez $8$: \begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline $n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline $n^2 \mod 8$ & 0 & 1 & 4 & 1 & 0 & 1 & 4 & 1\\ \hline \end{tabular} \emph{Zauważmy tutaj, że $(n-k)^2 \equiv k^2 \mod n$, więc wystarczyłoby policzyć reszty $0,1,2,3,4$, co jest krótsze :)} Gdyby zachodziła równość $$x^2 + y^2 + z^2 = 8k - 1$$ dla pewnych $x,y,z,k\in \mathbb{Z}$, to musiałaby także zajść równość $$r_x + r_y + r_z \equiv -1 \mod 8$$ gdzie $r_x,r_y,r_z\in \left\{ 0,1,4 \right\}$. Taka równość nie zachodzi -- bezpośrednio sprawdzamy wszystkie możliwości. \end{proof} \item Udowodnić, że dla dowolnej liczby naturalnej $n$ część całkowita liczby $$\frac{n^2 + n}{3}$$ jest parzysta. \begin{proof} Najprościej bezpośrednio to przeliczyć. Niech $n$ będzie dowolną liczbą całkowitą, $n = 3k + r$ gdzie $0\leq r\leq 2$. Obliczam: $$\floor{\frac{n^2 + n}{3}} = \floor{\frac{9k^2 + 6kr + r^2 + 3k + r}{3}} = (3k^2 + k) + 2kr + \floor{\frac{r^2 + r}{3}}$$ Wystarczy sprawdzić, że wszystkie wyrazy sumy po prawej są parzyste. $2kr$ jest parzyste. $3k^2 + k$ jest także parzyste, gdyż $$3k^2 = 2k^2 + k^2 \equiv k^2 \equiv k \mod 2$$ $$3k^2 + k \equiv 2k \equiv 0 \mod 2$$ Parzystość $\floor{\frac{r^2 + r}{3}}$ przeliczamy bezpośrednio podstawiając $r=0,1,2$. \end{proof} \item Dane są okręgi $O_1, O_2$, przecinające się w punktach $A,B$. Punkt $P$ leży na prostej $AB$, proste $PX$, $PY$ są styczne do $O_1$, $O_2$ odpowiednio. Uzasadnić, że $|PX| = |PY|$. \begin{proof} \begin{thm}[Twierdzenie o siecznych, wersja ze styczną] Niech dany będzie okrąg $o$ i punkt $P$ leżący poza okręgiem $o$. Prosta $PC$ jest styczna do $o$ w $C$, inna prosta przechodząca przez $P$ przecina $o$ w $A,B$. Wtedy $$|PA|\cdot |PB| = |PC|^2$$ \end{thm} Stosuję twierdzenie dla punktu $P$, okręgu $O_1$ i prostej $AB$: $$|PX|^2 = |PA|\cdot |PB|$$ oraz punktu $P$, okręgu $O_2$ i prostej $AB$: $$|PY|^2 = |PA|\cdot |PB|$$ \emph{Uwaga: tutaj po cichu korzystamy z założenia, że $AB$ jest wspólną cięciwą $O_1$ i $O_2$.} Łącząc powyższe równości: $|PX|^2 = |PY|^2$, a więc $|PX| = |PY|$. \end{proof} \end{enumerate} \end{document} |
