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}: \\}
\def\deg{^{\circ}}
\title{Warsztaty - kombinatoryka}
\date{}
\maketitle
\paragraph{Teoria}
\begin{enumerate}
\item Udowodnić, że ilość wyboru $n$-elementowego ciągu ze zbioru $(1,2,\cdots,n)$ (każdy element wybrany najwyżej raz) to $n!$.
\item Udowodnić, że ilość wyboru $k$-elementowego ciągu ze zbioru $(1,2,\cdots,n)$ (każdy element wybrany najwyżej raz) to $\frac{n!}{(n-k)!}$.
\item Udowodnić, że ilość wyboru $k$-elementowego ciągu ze zbioru $(1,2,\cdots,n)$ (każdy element wybrany najwyżej raz) to $\frac{n!}{k!(n-k)!}$.
\item \textbf{Symbol Newtona} Niech $n,k$ będą całkowite nieujemne. Wtedy definiujemy symbol Newtona:
$$\binom{n}{k}:=\frac{n!}{k!(n-k)!} \hbox{ jeżeli } n\geq k$$
$$\binom{n}{k}:=0 \hbox{ jeżeli } n<k$$
Własności
$$\binom{n}{k}=\binom{n}{n-k} \hbox{ i } \binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$$
\item Do $k$ rozróżnialnych pojemników wrzucamy $n$ nierozróżnialnych piłeczek. Udowodnić, że możemy to zrobić na
$$\binom{n+k-1}{k-1}$$
sposobów
\end{enumerate}
\paragraph{Zadania}
\begin{enumerate}
\item Udowodnić, że
$$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n$$
 
\item Udowodnić, że
$$\binom{n}{0}2^n+\binom{n}{1}2^{n-1}+\cdots+\binom{n}{n}2^0=3^n$$
 
\item Udowodnić, że dla $n>0$
$$\binom{n}{0}(-1)^n+\binom{n}{1}(-1)^{n-1}+\cdots+\binom{n}{n}(-1)^0=0$$
$$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots=2^{n-1}$$
w ostatniej sumie sumujemy dopóki dolny indeks jest niewiększy od górnego.
 
\item (nieomawiane) Udowodnić, że
$$\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2 = \binom{2n}{n}$$
 
\item Udowodnić, że liczba pokryć prostokąta $2\times n$ prostokątami $1\times 2$ i $2\times 1$ jest równa $F_{n+1}$ gdzie ciąg $(F_n)$ jest dany wzorem 
$$F_1 = F_2 = 1,\ \ F_{n+1} = F_n + F_{n-1}$$
 
\item W turnieju piłkarskim uczestniczy $n$ zespołów. Każdy z każdym rozgrywa jeden mecz. Rozgrywki odbywają się w $k$ miastach. Udowodnić, że pewne 3 zespoły rozegrają wszystkie mecze między sobą w jednym mieście, dla
\begin{enumerate}
\item $n=6,k=2$
\item (nieomawiane) $n=18,k=3$
\end{enumerate}
\footnotesize{źródło: www.ptm.pb.bialystok.pl}
\normalsize
 
\item Z pola E1 do pola E8 szachownicy król może dojść w siedmiu ruchach. Na ile sposobów może to zrobić?
\footnotesize{źródło: www.ptm.pb.bialystok.pl}
\normalsize
 
\item Udowodnić, że jeżeli mamy $101$ liczb całkowitych, to wśród nich są dwie, których różnica jest podzielna przez 100.
 
\item Udowodnić, że jeżeli wybierzemy $n+1$ różnych liczb ze zbioru $\{1,2,\cdots,2n\}$ to wśród nich są dwie
\begin{enumerate}
\item których suma jest równa $2n+1$
\item które są względnie pierwsze.
\end{enumerate}
 
\item Niech $a_1,a_2,\cdots, a_n$ będą liczbami całkowitymi. Udowodnij, że istnieją takie $1\leq k \leq l \leq n$, że $a_k+a_{k+1}+\cdots+a_l$ jest podzielne przez $n$.
\end{enumerate}
\end{document}