Koło matematyczne I LO w Białymstoku

 
Zadania PDF.

Źródło zadań w texu.

 
\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{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]{}
\begin{document}
\def\rozw{\\ \textbf{Rozwiązanie}: \\}
\title{Kółko 12.3 - niezmienniki i półniezmienniki}
\date{}
\maketitle
\paragraph{Teoria}
\begin{enumerate}
\item W zadaniach kombinatorycznych często spotykamy się z zadaniem typu: mamy dany obiekt $A$, wykonujemy na nim jakieś operacje, czy możemy dojść do innego, również danego obiektu $B$. Jeżeli odpowiedzią jest tak, to musimy po prostu, co jest zwykle dość trudne, pokazać, jakie przekształcenia wykonać. Jeżeli odpowiedzią jest nie, albo nam się tak wydaje :P, to sensowne jest zdefiniowanie pewnej własności obiektów $A,B$, która nie zmienia się przy przekształceniu, lub zmienia się, ale w określony sposób i zmiany tej własności są takie, że nigdy wychodząc od wartości w $A$ nie osiągnie się wartości takiej jak w $B$. Własność tę nazywamy \emph{niezmiennikiem} (gdy się nie zmienia), lub \emph{półniezmiennikiem}, gdy zmienia się, ale w określony sposób.
\item Czasami opłaca się opisać w pełni symulację procesu, ale zwykle jest to zbyt trudne i za bardzo pożera czas, zwłaszcza na 2 etapach.
\end{enumerate}
\paragraph{Zadania}
\begin{enumerate}
\item Dana jest tablica $3\times 5$ wypełniona na początku $-1$. W każdym ruchu zmieniamy znak dokładnie 2 liczb. Czy może się okazać, że otrzymalismy tablicę zapełnioną jedynkami?
 
\item (1. zadanko jubileuszowe) Wokół okrągłego stołu siedzi $13$ ufoli. Początkowo jeden z ufoli ma $13$ czarnych dziur. W jednym ruchu każdy ufol, który posiada co najmniej 2 czarne dziury, może wziąć 2 ze swoich czarnych dziur i podarować po jednej czarnej dziurze każdemu ufolowi siedziącemu obok. Powiedz ufolom, czy może dojść do sytuacji, gdy po pewnej liczbie ruchów każdy ufol ma po jednej czarnej dziurze.
 
\item (2. zadanko jubileuszowe) Udowodnij, że jeżeli posadzimy wśród ufoli Martę i damy jej $13+1$ czarnych dziur, nie zdoła ona rozdzielić tak czarnych dziur, żeby każdy ufol miał po jednej i jedna została Marcie, stosując algorytm opisany w powyższym zadaniu, gdzie Martę traktujemy jako ufola.
 
\item (epidemia) Na planszy rozmiaru $n\times n$ panujemy epidemia. Pole zaraża się, jeżeli co najmniej 2 sąsiadów (mających z polem wspólny bok) pola jest zarażonych. Ile co najmniej pól musiało być zarażonych na początku, jeżeli na końcu zarażone są wszystkie pola?
 
\item W terrarium jest $13$ żółtych, $15$ zielonych i $17$ czerwonych kameleonów. Gdy 2 kameleony różnych spotkają się, to oba zmieniają kolor na ten trzeci. Czy może się okazać, że po pewnych czasie wszystkie kameleony będą tego samego koloru?
 
\item Z $n^2$ płytek w kształcie trójkątów równobocznych ułożono trójkąt równoboczny o boku $n$. Każda płytka jest z jednej strony śliwkowa, a z drugiej pomarańczowa. Możemy odwracać płytki następująco: wybieramy płytkę $P$, mającą boki wspólne z co najmniej dwiema płytkami, których widoczne strony mają kolor inny niż widoczna strona płytki $P$ i odwracamy $P$ na drugą stronę. Rozstrzygnąć czy istnieje taka początkowa konfiguracja widocznych stron, że jeśli damy te płytki endrju do zabawy, to będzie on przekładać płytki nieskończenie (w i rezultacie spóźni się na kółko)?
 
\item W Białymstoku i okolicach mieszka $23$ uczestników olimpiady informatycznej. Każdy z nich lubi grać w dotę z niektórymi innymi (jeżeli $A$ lubi grać z $B$, to $B$ lub grać z $A$), oczywiście niektórzy np. Ola mogą nie lubić grać w Dotę z nikim. Jako, że drugi etap już minął, postanowili oni uczcić ten fakt nastepująco: w każdym kolejnym tygodniu kolejno jeden z nich zaprasza wszystkich, z którymi lubi grać w Dotę na wielki turniej Doty, który trwa cały tydzień. Po tym turnieju, jeżeli gospodarz lokalu ma inny system operacyjny niż większość (ostra) jego gości, to zmienia on swój system operacyjny na ten, który ma większość gości (wszyscy uzywają tylko systemu XP lub Vista). Udowodnić, że po pewnym czasie nigdy już żaden system operacyjny nie będzie zmieniany.
 
\item Na szachownicy o wymiarze $2001 \times 2003$ rozmieszczone są pionki, po jednym w każdym polu. Czy można tak przestawić pionki, by:
\begin{itemize}
\item na każdym polu stał nadal 1 pionek,
\item każdy pionek stał, po zmianie, na polu stykającym się bokiem z polem, na którym stał przed zmianą?
\end{itemize}
 
\item \footnotesize{Źródło części zadań: staszic}
 
\end{enumerate}
\end{document}