Koło matematyczne I LO w Białymstoku

 
Zadania PDF.

Źródło zadań w texu.

 
%        File: zad.tex
%     Created: Sun Sep 11 07:00 PM 2011 C
% Last Change: Sun Sep 11 07:00 PM 2011 C
\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\textwidth 16cm
\textheight 24cm
\oddsidemargin 0cm
\topmargin 0pt
\headheight 0pt
\headsep 0pt
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{polski}
\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{obs}[thm]{Obserwacja}
\newtheorem{useless}[thm]{}
 
\newenvironment{sol}[1][Rozwiązanie. ]{
\noindent\textsc{#1}}
{\hfill\par}
 
\newcounter{problem}
\newenvironment{problem}[1][Zadanie]{
\stepcounter{problem}
\noindent{\textsc{\bfseries #1 \theproblem}}\\}
{\hfill\par}
 
\def\source#1{\\Źródło: #1}
\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}
 
\subimport{../}{style.sty}
%\include{style}
 
\def\headpicture{../micek-2cm.jpg}
\def\author{Joachim Jelisiejew}
\def\date{13 września 2011}
\begin{document}
\section{Trójkąt Pascala}
 
Mamy następujące
 
\begin{problem}
    Policzyć, ile jest $k$-elementowych podzbiorów zbioru $\left\{ 1, 2,
    \dots, n \right\}$?
\end{problem}
 
Pierwszy krok: oznaczmy mądrze problem $\ddot\smile$.
\begin{defn}
    Niech $\binom{n}{k}$ oznacza liczbę $k$-elementowych podzbiorów zbioru
    $\left\{ 1, 2, \dots, n \right\}$. Oznaczenie $\binom{n}{k}$ czytamy
    ``$n$ po $k$''.
\end{defn}
 
Drugi krok: jak możemy wybrać $k$-elementowy podzbiór?
\begin{obs}
    Wszystkie elementy lub $0$ elementów możemy wybrać na jeden sposób:
    \[
    \binom{n}{n} = \binom{n}{0} = 1
    \]
    dla każdego $n$.
\end{obs}
\begin{obs}
    \label{add}
    Zauważmy, że wybierając $k$-elementowy podzbiór możemy wybrać element
    ``$n$'' lub nie. Tak więc
    \[
    \binom{n}{k} = \hbox{liczba }k\hbox{-elementowych
    podzbiorów}\{1,\dots,n\}=
    \]
    \[\hbox{ liczba }k\hbox{-elementowych
    podzb.}\left\{ 1, 2,\dots, n \right\}\hbox{ zawierających }n\ \ +
    \]
    \[\hbox{
    liczba }k\hbox{-elementowych podzb.}\left\{ 1, 2,\dots, n \right\}\hbox{
    nie zawierających }n =
    \]
    \[
    \hbox{liczba }k-1\hbox{-elementowych podzb. }\left\{ 1, 2, \dots, n-1
    \right\} +
    \]
    \[
    \hbox{liczba }k\hbox{-elementowych podzb. }\left\{ 1, 2, \dots, n-1
    \right\} =
    \]
    \[
    \binom{n-1}{k-1} + \binom{n-1}{k}.
    \]
\end{obs}
 
Łącznie obserwacje te pozwalają obliczyć np.
\[
\binom{3}{2} = \binom{2}{2} + \binom{2}{1} = 1 + \binom{2}{1} = 1 +
\binom{1}{0} + \binom{1}{1} = 3.
\]
Zwykle $\binom{n}{k}$ przedstawia się w~postaci tzw. \textbf{trójkąta
Pascala}:
 
\includegraphics{pascal}
 
\begin{problem}
    Uzasadnij z~definicji, że $\binom{n}{k} = \binom{n}{n-k}$.
\end{problem}
 
\begin{problem}
    Udowodnij, że
    \[
    \binom{n}{k} = \frac{n!}{k!(n-k)!}.
    \]
    np. korzystając ze wzoru z~obserwacji \ref{add}.
\end{problem}
 
\begin{problem}
    Udowodnij, że jeśli liczba $p$ jest pierwsza, to
    $p\left|\binom{p}{k}\right.$ dla $k=1,2,\dots,p-1$.
\end{problem}
 
\subsection{Wzór dwumianowy Newtona}
 
Trzeci krok: jak jeszcze możemy wybrać $k$-elementowy podzbiór?
 
Możemy zdecydować, czy wybieramy element ``$1$'' czy nie, czy wybieramy
element ``$2$'' czy nie itd. Musimy tylko uważać, żeby łącznie wybrać $k$
elementów.
 
Przykładowo: podzbiory zbioru $\left\{ 1, 2 \right\}$ to $\left\{ 1, 2
\right\}, \left\{ 1 \right\}, \left\{ 2 \right\}, \left\{  \right\} =
\emptyset$.
 
Załóżmy, że $TAK$ oznacza, że wybieram, że element, $NIE$ oznacza, że nie
wybieram elementu. Wtedy podzbiór $\left\{ 2 \right\}$ to $TAK, NIE$, a~zbiór
$\left\{ 1, 2 \right\}$, $TAK, TAK$. Można pójść dalej i~zapisać wszystkie
podzbiory jako
\[
TAK, TAK; TAK, NIE; NIE, TAK; NIE, NIE\hbox{ lub,}
\]
\[\hbox{ z lekkim nadużyciem } (TAK,
NIE)(TAK, NIE) = (TAK, NIE)^2.
\]
Zbiory $k$-elementowe to te, w~których $TAK$ występuje dokładnie $k$-razy, nie
zważając na kolejność: $TAK, NIE$ i~$NIE, TAK$, czyli kolejność nie ma
znaczenia.
 
Można zapisać, że
\[
(TAK + NIE)^2 = TAK^2 + TAK\cdot NIE + NIE\cdot TAK + NIE^2 = TAK^2 +2\cdot
TAK\cdot NIE + NIE^2 = \]
\[\binom{2}{0}TAK^2 + \binom{2}{1}TAK\cdot NIE +
\binom{2}{2}NIE^2.
\]
Ogólnie, możemy to zapisać jako
\begin{thm}[Wzór dwumianowy Newtona]
    \[
    (a + b)^n = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b +
    \binom{n}{2}a^{n-2}b + \dots + \binom{n}{n}b^n.
    \]
    przykładowo $(a+b)^3 = \binom{3}{0}a^3 + \binom{3}{1}a^2b +
    \binom{3}{2}ab^2 + \binom{3}{3}b^3 = a^3 + 3a^2b + 3ab^2 + b^3$.
\end{thm}
Formalny dowód tego wzoru jest w~zasadzie powtórzeniem tego, co jest
powiedziane wyżej, ale będzie on jeszcze pokazany na kółkach.
 
\end{document}