|
Zadania PDF.
Źródło zadań w texu.
% File: niezm_krak.tex
% Created: Sun Nov 11 09:00 PM 2012 C
% Last Change: Sun Nov 11 09:00 PM 2012 C
\documentclass[10pt, a4paper]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[textwidth=16cm, textheight=27cm]{geometry}
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{polski}
\usepackage{graphicx}
\usepackage{enumitem}
\setenumerate{itemsep=2pt,topsep=2pt,parsep=0pt,partopsep=0pt}
\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}
\newtheorem{cor}[thm]{Wniosek}
\newtheorem{lem}[thm]{Lemat}
\newtheorem{defn}[thm]{Definicja}
\newtheorem{tozs}[thm]{Tożsamość}
\newtheorem{hyp}[thm]{Hipoteza}
\newcommand{\HRule}{\rule{\linewidth}{0.2mm}}
\renewcommand{\section}[1]{
%\vspace*{-1.5cm}
\stepcounter{section}%
\begin{center}%
\begin{minipage}{2.5cm}
\includegraphics[origin=c,width=2.5cm]{\headpicture}
\end{minipage}\begin{minipage}{\sectionwidth}
\begin{center}
{\Huge \bfseries \center #1}
\vskip 1mm
\small \normalfont \sc
\author{}\\
\date{}
\end{center}
\end{minipage}
\end{center}
\HRule
}
\newenvironment{sol}[1][Rozwiązanie. ]{
\vskip 3mm
\noindent\emph{#1}
}
{
}
\newcounter{problem}
\newenvironment{problem}[1][]{
\stepcounter{problem}
\vskip 3mm
\noindent{\textsc{{\bfseries Zadanie \theproblem{}} #1}}\\}
{
}
\pagestyle{empty}
\def\abs #1{\left\vert #1\right\vert}
\renewcommand{\angle}{\sphericalangle}
\renewcommand{\vec}[1]{\overrightarrow{#1}}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\dots}{\ldots}
\def\sectionwidth{6cm}
\def\headpicture{../micek-2cm.jpg}
\def\author{kółko I~LO Białystok}
\def\date{13 listopada 2012}
\begin{document}
\section{Niezmienniki}
Ukochaną sytuacją OMów jest ``mamy sytuację $A$ wykonujemy jakieś ruchy
zmieniające ją, czy możemy dojść do sytuacji $B$''. Zwykle nie da się
sprawdzić (mniej lub bardziej inteligentnie) wszystkich możliwości, trzeba
więc wybrać \emph{niezmiennik} lub \emph{półniezmiennik}~--- cechę sytuacji,
która nie zmienia się lub zmienia się w~dobry dla nas sposób.
Istnieje kanon niezmienników~--- sposoby często pojawiające się w~zadaniach.
Poniższe zadania wprowadzają wiele z~nich.
\emph{Wiele z~poniższych zadań pochodzi z~warsztatów V LO w~Krakowie.
Dziękuję!}
\setcounter{problem}{-2}
\begin{problem}[ulubione prof.~Kordosa]
Mamy puchar z~wodą, puchar z~winem oraz pusty (mniejszy) pucharek.
Zaczerpnięto pełen pucharek wody i~przelano ją do wina, następnie
zaczerpnięto również pucharek otrzymanej mieszaniny i~przelano ją do wody. Czy więcej jest
wody w~pucharze z~winem, czy wina w~pucharze z~wodą?
\end{problem}
\begin{sol}
W~obu pucharach łączna objętość płynu jest taka sama na początku i~na
końcu operacji. Wobec tego tyle wody ubyło z~pucharka z~wody, ile wina
przybyło. Czyli wody w~winie jest tyle samo ile wina w~wodzie.
\end{sol}
\begin{problem}
Mamy daną liczbę $2009!$. Obliczamy sumę jej cyfr, sumę cyfr liczby tak
otrzymanej itd. Uzasadnij, że po skończenie wielu ruchach uzyskamy liczbę
jednocyfrową. Jaka to będzie liczba?
\end{problem}
\begin{sol}
Oznaczmy przez $S(x)$ sumę cyfr $x$.
Jeżeli mamy liczbę dwu lub więcej cyfrową w~postaci $M = a_n\cdot 10^n + \dots
+ a_1 \cdot 10 + a_0$ to $S(M) = a_n + \dots + a_1 + a_0$.
Skoro $a_i\cdot 10^i \geq a_i$ oraz $10^na_n > a_n$ (ważne: ostra nierówność bo
$a_n> 0$ i~$n > 0$) to
\[S(M) = a_n + \dots + a_0 < a_n\cdot 10^n + \dots + a_1\cdot 10 + a_0 = M\]
więc branie sumy cyfr zmniejsza liczbę, o~ile nie jest ona jednocyfrowa.
Jeżeli startujemy z~$X$ to po każdej operacji otrzymujemy liczbę dodatnią.
Gdyby liczby otrzymywane w~$X+1$ kolejnych krokach były dwu lub więc
cyfrowe, to w~każdym z~nich zmniejszalibyśmy otrzymaną liczbę, więc po $X$
krokach otrzymalibyśmy liczbę nie większą niż $X - (X+1) = -1$. Ale suma
liczb liczby dodatniej nie może być ujemna. Sprzeczność!
Wobec tego po skończenie wielu krokach otrzymamy liczbę jednocyfrową
dodatnią.
\emph{W~tym wypadku półniezmiennikiem była po prostu wartość liczby
otrzymywanej w~kolejnych krokach i~fakt, że zmniejszała się ona.}
Reszta z~dzielenia liczby przez $9$ nie zmienia się (to cecha podzielności
przez $9$) a~$2009!$ jest podzielna, więc otrzymamy $9$.
\end{sol}
\subsection{Niegeometryczne}
\begin{problem}[Nowogród 2012]
Na tablicy zapisano liczbę uzyskaną przez podniesienie
liczby siedem do potęgi $2012^{2012}$. W~jednym kroku ścieramy pierwszą (od
lewej) cyfrę $C$ liczby zapisanej na tablicy, otrzymując liczbę $b$, ścieramy
również liczbę $b$ i~zapisujemy na tablicy $b + C$.
Po pewnej liczbie kroków otrzymaliśmy liczbę dziesięciocyfrową. Wykaż, że dwie
jej cyfry są jednakowe. \emph{Używamy systemu dziesiętnego.}
\end{problem}
\begin{problem}
Dana jest tablicy $2011 \times 2011$ wypełniona na początku liczbami $-1$.
W~każdym ruchu $2012$ liczb przez $-1$. Uzasadnij, że nie możemy otrzymać
planszy wypełnionej jedynkami.
\end{problem}
\subsection{Geometryczne}
Tutaj jest mało standardowych. Znane to \textbf{pole}, \textbf{obwód},
\textbf{środek ciężkości}, \textbf{wyróżnienie części} i~\textbf{pozostałe ;)}.
\begin{problem}
Na tarczy zegara w~miejsce liczb wkręcono żarówki. Żarówka na godzinie
$12$ jest zapalona, pozostałe są zgaszone. Możemy wybierać dowolne 6
kolejnych żarówek i~jednocześnie zmieniać stan wszystkich tych żarówek.
Czy możemy w~ten sposób doprowadzić do tego, by świeciła tylko jedna
żarówka na godzinie $11$?
\end{problem}
\begin{problem}
Fredek gra w~samotnika. Plansza do gry ma kształt $n$--kąta foremnego. Na
każdym wierzchołku tego $n$--kąta stoi kieliszek, niektóre kieliszki są
napełnione. Jedno posunięcie polega na tym, że Fredek wypija zawartość
dowolnie wybranego kieliszka oraz zawartość tych sąsiednich kieliszków,
które były napełnione i~jednocześnie napełnia te sąsiednie kieliszki,
które były puste. Jeśli po pewnym posunięciu wszystkie kieliszki są puste,
to Fredek idzie się napić. Uzasadnij, że jeśli $n$ jest podzielne przez
$3$ i~na początku jedynie jeden kieliszek jest napełniony, to Fredek nie pójdzie się napić.
\end{problem}
\begin{problem}[matma.ilo.pl]
Wokół okrągłego stołu siedzi $2012$ ufoli. Początkowo jeden z ufoli ma
$2012$ czarnych dziur. W jednym ruchu każdy ufol, który posiada co najmniej
dwie czarne dziury, może wziąć dwie ze swoich czarnych dziur i podarować po
jednej czarnej dziurze każdemu ufolowi siedzącemu obok. Powiedz ufolom,
czy może dojść do sytuacji, gdy po pewnej liczbie ruchów każdy ufol ma po
jednej czarnej dziurze.
\end{problem}
\begin{problem}[LVII OM, etap 2, mniej więcej]
Trójkąt równoboczny o~boku długości $2012$ jest złożony z~płytek
w~kształcie trójkącików równobocznych o~boku długości $1$, mających jedną
stronę pokolorowaną na karolinowo a~drugą na szymonowo. Trójkącik można
odwrócić, jeżeli sąsiaduje z~co najmniej dwoma trójkącikami mającymi
widoczną stronę w~innym kolorze. Uzasadnij, że nie istnieje ustawienie
startując od którego możemy odwracać trójkąciki bez końca.
\end{problem}
\begin{problem}[Epidemia]
Uczniowie piszą olimpiadę ustawieni w~kwadrat $2012 \times 2012$. Jeżeli
dwóch uczniów sąsiadujących z~$A$ (z~boku/przodu/tyłu, nie po przekątnej) jest
zniechęconych, zniechęca się także uczeń $A$.
Uzasadnij, że jeśli na końcu cała sala jest zniechęcona, to na początku
zniechęconych musiało być co najmniej $n$ uczniów.
\end{problem}
\begin{problem}
Dana jest szachownica $2010 \times 2010$. Na każdym polu leży kamień.
Dwa kamienie leżą na pewnym~wierszu/kolumnie/przekątnej tak, że oddziela
je jedno pole możemy je przełożyć na to pole. Uzasadnij, że kamieni nie da
się zgromadzić w~jednym punkcie.
\end{problem}
\end{document}
|
