Koło matematyczne I LO w Białymstoku

 
Zadania PDF.
 
Rozwiązania 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}
\title{Zadania do samodzielnego rozwiązania spod hasła "Kombinować każdy może..."}
\date{}
\maketitle
\begin{enumerate}
\item Kombinatoryki jeszcze w tym roku nie było, najwyżej tyle co na obozie, ale do tych zadań nie potrzebna jest teoria (może oprócz najprostszej - Dirichleta, który był i prostych kolorowań, które były na obozie), bardziej tytułowa umiejętność kombinowania.
\item Wyznaczyć wszystkie liczby pierwsze $p$, takie, że $2p+1$ i $4p+1$ są również pierwsze.
\item Mamy prostokątną szachownicę $N\times M$, z wyciętym polem $(a,b)$ (lewy dolny róg ma współrzędne $(1,1)$, a lewy górny $(1,M)$). Udowodnić, że jeśli szachownicę tę (bez pola $(a,b)$) da się pokryć prostokątami $1\times 2$, stawianymi poziomo lub pionowo, to $2|a+b$.
\item Dane są liczby $a_1<a_2<\cdots<a_n$ i $b_1 > b_2 >\cdots > b_n$, wśród których każda z liczb $1,2,3,\cdots,2n$ występuje dokładnie raz. Udowodnić, że $|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|=n^2$. Wskazówka: przeanalizować dużo małych przypadków.
\item Te zadanka nie są zbyt proste, ani trudne, biorąc pod uwagę, że na rozwiązanie jest tydzień. W miarę możliwości poziom następnych serii (o ile będą), będzie wyrównywany do poziomu rozwiązujących.
\end{enumerate}
\end{document}
 

Źródło rozwiązań 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}
\title{Zadania do samodzielnego rozwiązania spod hasła "Kombinować każdy może..."}
\date{}
\maketitle
\begin{enumerate}
\item Kombinatoryki jeszcze w tym roku nie było, najwyżej tyle co na obozie, ale do tych zadań nie potrzebna jest teoria (może oprócz najprostszej - Dirichleta, który był i prostych kolorowań, które były na obozie), bardziej tytułowa umiejętność kombinowania.
\item Wyznaczyć wszystkie liczby pierwsze $p$, takie, że $2p+1$ i $4p+1$ są również pierwsze.\\
\textbf{Rozwiązanie}: Rozważmy reszty z dzielenia przez 3. Jeżeli $p\equiv 0 (\mod 3)$, to oczywiście $p=3$. Wtedy też $2p+1=7$ i $4p+1=13$ są pierwsze, więc mamy jedno rozwiązanie. Gdy $p\equiv 1 (\mod 3)$, to $3|2p+1$, więc, skoro jest to liczba pierwsza, to musi być $2p+1=3$, $p=1$ - sprzeczność. Jeżeli $p\equiv 2 (\mod 3)$, to $3|4p+1$, więc $4p+1=3$, czyli $p<1$, sprzeczność. Ostatecznie tylko liczba $3$ spełnia warunki zadania.\\
\textbf{Inny sposób}: $p=2$ nie spełnia warunków zadania - $4p+1$ nie jest pierwsza, dalej zakładamy, że $p\geq3$. Zauważmy, że jedna z liczb $4p,4p+1,2(2p+1)=4p+2$ musi być podzielna przez $3$, bo są to 3 kolejne liczby całkowite. To implikuje, że któraś z liczb $p, 2p+1, 4p+1$ musi być podzielna przez $3$, a skoro są one pierwsze, to któraś musi być równa $3$. Mamy $p\geq3$, stąd $2p+1>3,4p+1>3$, więc $p=3$. Liczba 3 spełnia warunki zadania.\\
\item Mamy prostokątną szachownicę $N\times M$, z wyciętym polem $(a,b)$ (lewy dolny róg ma współrzędne $(1,1)$, a lewy górny $(1,M)$). Udowodnić, że jeśli szachownicę tę (bez pola $(a,b)$) da się pokryć prostokątami $1\times 2$, stawianymi poziomo lub pionowo, to $2|a+b$.\\
\textbf{Rozwiązanie}: Zauważmy, że jeżeli szachownicę sa się pokryć prostokątami, to musi być $2|NM-1$, stąd $N,M$ - nieparzyste, $N=2n+1$, $M=2m+1$ ($n,m\in\mathbb{Z}$, $n,m\geq 0$). Pokolorujmy pola $(x,y)$ szachownicy, które spełniają warunek $2|x+y$ na czarno. Każdy prostokąt zajmuje jedno pole białe i jedno czarne, skoro da się pokryć prostokątami, to pól białych i czarnych jest tyle samo.\\
Zauważmy, że wszystkie rogi są czarne. Pól czarnych jest $n\cdot M+m+1$ (liczymy po 2 kolumny i ostatnia zostaje), a białych $n\cdot M+m$, czyli o jedno mniej. Stąd pole czarne musiało być na początku usunięte, aby pokrycie było możliwe.\\
Co ciekawe, odwrotne twierdzenie jest również prawdziwe: Da się pokazać (konstruując śmieszną spiralkę), że jeżeli tablica $N\times M$, gdzie $N,M$ - nieparzyste ma wycięte pole $(a,b)$, takie, że $2|a+b$, to da się ją pokryć prostokątami $1\times 2$ (stawianymi pionowo lub poziomo).\\
\item Dane są liczby $a_1<a_2<\cdots<a_n$ i $b_1 > b_2 >\cdots > b_n$, wśród których każda z liczb $1,2,3,\cdots,2n$ występuje dokładnie raz. Udowodnić, że $|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|=n^2$. Wskazówka: przeanalizować dużo małych przypadków.\\
\textbf{Rozwiązanie}: Zauważmy, że każda liczba większa niż $n$ jest w parze w wyrażeniu z zadania z liczbą niewiększą niż $n$. Faktycznie załóżmy, że w $(b_n)$ jest $k$ liczb większych od $n$, te liczby to oczywiście $b_1,b_2,\cdots,b_k$, bo $(b_n)$ jest posortowany. Wtedy oczywiście w $(a_n)$ jest $n-k$ liczb większych od $n$ i są to liczby $a_n,a_{n-1},\cdots,a_{k+1}$. Widać, że w żadnej parze nie ma 2 liczb większych od $n$.\\
Z powyższego rozumowania wnosimy, że w każdej parze jest 1 liczba większa od $n$ i jedna niewiększa od $n$. Ponieważ każda liczba większa od $n$ jest większa od każdej liczby niewiększej od $n$, to w $|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|$ liczby większe od $n$ są brane z plusem, a niewiększe z minusem (bo jeżeli $a>b$, to $|a-b|=a-b$), więc $|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|=2n+(2n-1)+\cdots+(n+1)-n-(n-1)-\cdots-1=(2n-n)+((2n-1) - (n-1))+\cdots+((n+1)-1)=n+n+\cdots+n=n\cdot n=n^2$.
\item Te zadanka nie są zbyt proste, ani trudne, biorąc pod uwagę, że na rozwiązanie jest tydzień. W miarę możliwości poziom następnych serii (o ile będą), będzie wyrównywany do poziomu rozwiązujących.
\end{enumerate}
\end{document}