Koło matematyczne I LO w Białymstoku

 
Zadania PDF.

Źródło zadań w texu.

%        File: zad.tex
%     Created: Sat Nov 13 02:00 PM 2010 C
% Last Change: Sat Nov 13 02:00 PM 2010 C
\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\textwidth 16cm
\textheight 25.5cm
\oddsidemargin 0cm
\topmargin 0pt
\headheight 0pt
\headsep 0pt
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{import}
\usepackage[pdfborder={0 0 0}]{hyperref}
%\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]{}
 
\newenvironment{proof}[1][Dowód. ]{\noindent\textsc{#1}}
{\nolinebreak[4]\hfill$\blacksquare$\\\par}
\newenvironment{sol}[1][Rozwiązanie. ]{
\noindent\textsc{#1}}
{\hfill\par}
 
\newenvironment{problem}{\noindent\textsc{Zadanie}\\}
{\hfill\par}
 
\def\deg{^{\circ}}
\def\source#1{\\Źródło: #1}
 
 
%\subimport{../}{style}
\include{style}
 
\begin{document}
 
\setlength{\topmargin}{-1.2cm}
 
\section{ {\normalsize W ciągu $n$ kółek są dwa mówiące o tym samym,
czyli}\\[-1cm]
Dirichlet!}
 
\renewcommand{\thethm}{}
\begin{thm}[Zasada szufladkowa Dirichleta] Jeżeli $kn+1$ przedmiotów wkładamy
    do $n$ szufladek, to w przynajmniej jednej szufladce będzie przynajmniej
    $k+1$ przedmiotów.\end{thm}
 
\subsection{Prostsze}
\begin{enumerate}
    \item \begin{problem}
            $200$ różnych punktów zostało wybranych na okręgu tak, że kąt środkowy
            oparty na dowolnych dwóch z nich ma całkowitą ilość stopni.
            Dowiedź, że wśród nich istnieją punkty antypodyczne (tzn.
            symetrycznie względem środka okręgu).
        \end{problem}
    \item \begin{problem}
            Pokaż, że istnieją dwie różne potęgi $3$, których różnica jest
            podzielna przez $2010$.
        \end{problem}
    \item \begin{problem}
            Liczby $1,2,3,\dots,10$ zostały umieszczone w~pewnym porządku na
            okręgu. Udowodnij, że istnieją 3 kolejne liczby, których suma jest
            nie mniejsza niż $17$.
        \end{problem}
    \item \begin{problem}
            Dany jest zbiór $2011$ punktów na płaszczyźnie. Z~każdej trójki
            punktów da się wybrać dwa odległe od siebie o~mniej niż $1$
            stańkometr.
            Udowodnij, że pewne $1006$ punktów leży w~pewnym kole o~promieniu
            $1$ stańkometra.
        \end{problem}
    \item \begin{problem}
            Wykaż, że w dowolnym wielościanie istnieją dwie ściany o tej samej liczbie
            krawędzi.
        \end{problem}
\end{enumerate}
 
\subsection{Średnie i trudniejsze}
 
%Niektóre zadania są wzięte z książki Musztariego.
%\emph{Wśród poniższych zadań nie ma naprawdę trudnych, ale i naprawdę łatwych.
%Osobom, które nie zetknęły się jeszcze z Dirciem sugeruję pomyśleć najpierw
%nad zadaniami z \url{http://matma.ilo.pl/images/pros09_diri.pdf}. Jeżeli
%chcecie jeszcze więcej zadań polecam wpisać w wyszukiwarce \url{matma.ilo.pl}
%``Dirichlet''.}
 
\begin{enumerate}
%    \item
%        \begin{problem}
%            \emph{Resztka teorii liczb -- fakt potrzebny do rozwiązania
%            zadania z poprzedniego kółka.}
 
%            Niech $a,b\in \mathbb{Z}$, niech liczba $d$ będzie całkowita.
%            Udowodnij, że następujące warunki są równoważne:
%            \begin{enumerate}
%                \item $NWD(a,b) \Big| d$.
%                \item Istnieją liczby $x,y\in \mathbb{Z}$, takie, że
%                    \[ax + by = d.\]
%            \end{enumerate}
 
%            \emph{Wskazówki (niektóre podpunkty warto narysować na osi
%            liczbowej).}
 
%                Dla zwięzłości oznaczamy $(a,b) := \{ax + by\ |\ x,y\in
%                \mathbb{Z}\}$, czyli zbiór liczb całkowitych dających się
%                zapisać w postaci $ax+by$ dla pewnych $x,y$ całkowitych.
 
%                Analogicznie oznaczam $(NWD(a,b)) := \left\{ NWD(a,b)x\ |\ x\in \mathbb{Z}
%                \right\}$.
%            \begin{enumerate}
%                \item Wykaż, że $(b) \Rightarrow (a)$, innymi słowy, że
%                    $d\in (a,b)$ implikuje $NWD(a,b) \Big|d$.
%                \item \emph{Przetrawianie definicji. Wszystkie poniższe
%                    stwierdzenia są ``udowadnialne'' drogą
%                    podstawiania definicji $(a,b)$.}
 
%                    Uzasadnij, że
%                    \begin{enumerate}
%                        \item $0\in (a,b)$.
%                        \item Jeżeli $t\in (a,b)$ i $r\in \mathbb{Z}$ to
%                            $rt\in (a,b)$, innymi słowy $t\in (a,b)$ i
%                            $t\Big|u$ implikuje $u\in (a,b)$.
%                        \item Jeżeli $t,u\in (a,b)$ to $t+u, t-u\in (a,b)$.
%                    \end{enumerate}
%                \item Uzasadnij, że jeżeli $d \in (a,b)$  to
%                    również $a \mod d, b\mod d\in (a,b)$
%                \item
%                    Niech $d_0$ będzie najmniejszą liczbą dodatnią z
%                    $(a,b)$.
 
%                    Zrozum, że skoro $a\mod d_0 < d_0$ i~$a\mod
%                    d_0\in (a,b)$ to $a\mod d_0 = 0$ i analogicznie $b\mod d_0
%                    = 0$, czyli $d_0\Big|a$ i $d_0\Big|b$, zatem
%                    $d_0\Big|NWD(a,b)$, z poprzedniego punktu ($d\in (a,b)$)
%                    mamy $NWD(a,b)\Big|d_0$, czyli $d_0 = NWD(a,b)$.
%                \item \emph{Dowód $(a) \Rightarrow (b).$}
%                    Niech $d$ będzie dowolną liczbą podzielną przez
%                    $NWD(a,b)$. Skorzystaj z poprzednich podpunktów aby
%                    dowieść, że $d\in (a,b)$.
%                \item \emph{Bonus.} Zauważ, że teza mówi dokładnie, że zachodzi równość
%                    $(NWD(a,b)) = (a,b)$.
%            \end{enumerate}
%        \end{problem}
    \item
        \begin{problem}
            \emph{Resztka teorii liczb -- fakt potrzebny do rozwiązania
            zadania z poprzedniego kółka.}
 
            Niech $a,b\in \mathbb{Z}$, niech liczba $d$ będzie całkowita.
            Udowodnij, że następujące warunki są równoważne:
            \begin{enumerate}
                \item $NWD(a,b) \Big| d$.
                \item Istnieją liczby $x,y\in \mathbb{Z}$, takie, że
                    \[ax + by = d.\]
            \end{enumerate}
 
            \emph{Wskazówki: }
            \begin{enumerate}
                \item Wykaż, że $(b)  \Rightarrow (a)$.
                \item \emph{$(a)  \Rightarrow (b).$}
 
                    Załóż, że $NWD(a,b) = 1$.
 
                    Z twierdzenia chińskiego o resztach wynika, że istnieją:
                    \[
                    A: A \equiv 0 \mod a,\ A \equiv 1 \mod b,
                    \]
                    \[
                    B: B \equiv 1 \mod a,\ B \equiv 0 \mod b.
                    \]
                    Oczywiście $A + B \equiv 1 \mod a$ i $A + B \equiv 1 \mod
                    b$. Uzasadnij, że $A + B \equiv 1 \mod ab$.
 
                    Zauważ, że stąd wynika przedstawienie $1 = ax + by$ dla
                    pewnych $x,y\in \mathbb{Z}$, a przez domnożenie ---
                    przedstawienie dowolnej liczby naturalnej w tej postaci. 
                \item Udowodnij twierdzenie w ogólnej postaci, bez założenia
                    $NWD(a,b) = 1$.
 
                    \emph{Wskazówka: Podziel przez $NWD(a,b)$.}
            \end{enumerate}
        \end{problem}
    \item
        \begin{problem}
            W ILO powołano komitety wyborcze. Każdy komitet skupia ponad połowę
            uczniów. Udowodnić, że istnieje uczeń, który należy do ponad
            połowy komitetów.
        \end{problem}
    \item
        \begin{problem}
            Każdy punkt płaszczyzny malujemy na sebowo lub hubowo. Udowodnić,
            że istnieje prostokąt o osiach równoległych do układu
            współrzędnych, którego wszystkie wierzchołki są tego
            samego koloru.
        \end{problem}
    \item
        \begin{problem}
            Yogi zjada co najmniej jeden piknik dziennie. Jeżeli przez
            ostatni miesiąc ($30$ dni) zjadł on $45$ pikników udowodnij, że od
            pewnego dnia A do dnia B zjadł dokładnie $14$ pikników.
        \end{problem}
    \item
        \begin{problem}
            Oznaczam $\left\{ x \right\}$ część ułamkową liczby $x$, tzn. taką
            liczbę $r\in [0,1)$, że $x - r$ jest całkowita. Np. $\{3.5\} =
            0.5$, $\{-1.2\} = 0.8$.
 
            Niech $\alpha$ będzie liczbą niewymierną. Udowodnić, że w dowolnym
            przedziale $(a,b) \subseteq [0,1)$, ($a < b$) istnieje nieskończenie wiele
            liczb postaci $\left\{ n\alpha \right\} (*)$ dla $n\in \mathbb{N}$.
 
            \emph{Wskazówki:}
            \begin{enumerate}
                \item Weź liczby $\{\alpha\}, \{2\alpha\}, \{3\alpha\},
                    \cdots, \{n\alpha\},
                    \{(n+1)\alpha\}$, udowodnij, że dwie różne z nich leżą w odległości
                    nie większej niż $1/n$, stwierdź że wobec tego istnieje
                    liczba postaci * w przedziale $(0, \frac{1}{n})$ lub w
                    przedziale $(1-\frac{1}{n}, 1)$. Udowodnij, że jeżeli
                    istnieje liczba w przedziale $(1-\frac{1}{n}, 1)$ to i
                    w~$(0, \frac{1}{n})$, zatem zawsze istnieje liczba w $(0,
                    \frac{1}{n})$.
                \item Obierz dowolne $0<a><strong><1,k\in \mathbb{N}$ i udowodnij, że w przedziale
                    $(a,b)$ leży co najmniej $k$ różnych liczb postaci *,
                    biorąc wielokrotności liczby otrzymanej powyżej.
            \end{enumerate}
        \end{problem}
    \item
        * \begin{problem}
            Uzasadnij, że dla dowolnej liczby $A$ istnieje takie $n$, że $2^n$
            rozpoczyna się od cyfr z liczby $A$ np. dla $A = 13$ mamy
            $2^{17} = 131072$, dla $A = 1811$ mamy $2^{1901} = \underbrace{1811430839172\ldots}_{573\hbox{ cyfry}}$,
            jak widać te liczby nie muszą być zbyt małe :P
 
            \emph{Wskazówka: rozważ $n\log_{10} 2 = \log_{10} 2^n$ i $\log_{10} A$, gdzie
            $\log_{10} x$ to taka liczba rzeczywista, że $10^{\log_{10} x} =
            x$ (żadnych strasznych własności logarytmów nie potrzeba znać).}
        \end{problem}
\end{enumerate}
 
\end{document}
</strong></a>