|
Zadania PDF.
Źródło zadań w texu.
% File: zad.tex
% Created: Mon Oct 17 10:00 PM 2011 C
% Last Change: Mon Oct 17 10:00 PM 2011 C
\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\textwidth 16cm
\textheight 26cm
\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{useless}[thm]{}
\newenvironment{sol}[1][Rozwiązanie. ]{
\noindent\emph{#1}
}
{\hfill\par}
\newcounter{problem}
\newenvironment{problem}[1][Zadanie]{
\stepcounter{problem}
\vskip 2mm
\noindent{\textsc{\bfseries #1 \theproblem}}\\}
{\hfill\par}
\def\source#1{\\Źródło: #1}
\def\abs #1{\left\vert #1\right\vert}
\renewcommand{\thethm}{}
\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{18 października 2011}
\begin{document}
\setlength{\topmargin}{-0.5in}
\section{Dwumian Newtona}
Przypominam, że
\[
\binom{n}{k} = \begin{cases}\frac{n\cdot (n-1)\cdot \dots \cdot (n-k+1)}{k\cdot (k-1)\cdot
\dots \cdot 1} & k > 0\\
1 & k =0.\end{cases}
\]
Definicja ma sens dla dowolnego $k\in \mathbb{Z}_{\geq 0}, n\in \mathbb{R}$ (!).
Jeżeli $0 \leq k \leq n$ oraz $n, k$ są całkowite to $\binom{n}{k} =
\frac{n!}{(n-k)!k!}$, pamiętajmy, że $0! = 1$.
\def\floor#1{\left\lfloor #1 \right\rfloor}
\begin{problem}
Dla liczby rzeczywistej $x$ definiujemy \emph{podłogę z~$x$} jako
największą liczbę całkowitą nie większą niż $x$, w~szczególności
z~definicji wynika, że $\floor{x} \leq x,\ \floor{x}\in \mathbb{Z}$ i~$\floor{x} = x \iff
x\in \mathbb{Z}$.
\begin{enumerate}
\item Udowodnij, że $x\leq y$ implikuje $\floor{x} \leq \floor{y}$.
\item Udowodnij, że dla liczb naturalnych $k, l$ zachodzi
$
\floor{\frac{k}{l}} = \frac{k}{l} \iff l\big|k.
$
\item Uzasadnij, że $\floor{x} + \floor{y} \leq \floor{x + y}$ dla
wszystkich $x,y\in \mathbb{R}$ (\emph{wskazówka: $\floor{a + b} =
\floor{a} + \floor{b}$, o~ile $a,b\in \mathbb{Z}$}).
\item Niech $p$ będzie liczbą pierwszą, niech $\alpha$ będzie
największą potęgą $p$, która dzieli $n!$ ($n$ silnia). Udowodnij,
że
\[
\alpha = \sum_{i=1}^{\infty} \floor{\frac{n}{p^i}}
\]
przy czym suma po prawej jest skończona.
\item Oblicz, w~zależności od $p, n, k$, ile razy liczba pierwsza $p$
dzieli $\binom{n}{k}$.
\item
Udowodnij, że jeżeli $p$ jest pierwsza, a~$l \geq 0$ całkowite, to
$
p\big|\binom{p^l}{k}
$
dla każdego całkowitego $k: 0 < k < p^l$.
\item Uzasadnij, że jeśli $l \geq 0$ jest całkowite, a~$p$ pierwsze, to
$(1+x)^{p^l} \equiv 1 + x^{p^l} \mod p$, to znaczy, że wielomian
$(1+x)^{p^l} - 1 - x^{p^l}$ ma współczynniki podzielne przez $p$.
Wywnioskuj z~tego przez indukcję, że $a^{p^k} \equiv a \mod p$ dla
każdego $a$ całkowitego.
Dowiedź tego samego stosując małe twierdzenie Fermata.
\item
Uzasadnij, że jeżeli $p$ jest pierwsze a~$k > 0$ całkowite, to
$p\big|\binom{pk}{k}$.
\end{enumerate}
\end{problem}
\vskip -5mm
\emph{Interpretacje kombinatoryczne.}
\begin{problem}
Udowodnij, że liczba najkrótszych dróg kratowych łączących $(0, 0)$ z~$(x,
y)$, gdzie $x,y\in \mathbb{N}$, wynosi $\binom{x+y}{y}$.
\end{problem}
\begin{problem}
Wykaż, że sposobów umieszczenia $n$ ulotek (nierozróżnialnych) w~$k$
skrytkach na listy jest $\binom{n+k-1}{k-1}$.
\end{problem}
\begin{problem}
Pokaż, że ilość nieujemnych rozwiązań całkowitych równania $x_1 + x_2 +
\dots + x_k = n$ w~zmiennych $x_1,\dots,x_k$ to $\binom{n+k-1}{k-1}$. Ile
jest takich rozwiązań w~liczbach całkowitych?
\end{problem}
\begin{problem}
Uzasadnij, że liczba funkcji ściśle rosnących $\left\{ 1, 2, \dots, n
\right\} \to \left\{ 1, 2, \dots, k \right\}$ jest równa $\binom{n}{k}$.
\end{problem}
\begin{thm}[Twierdzenie Lucasa]
Niech $p$ będzie pierwsza a~$a \geq b$ całkowite. Zapiszmy $a, b$
w~systemie pozycyjnym o~podstawie $p$ jako
\[a = \left(\overline{a_na_{n-1}\dots a_0}\right)_p,\quad b = \left(\overline{b_nb_{n-1}\dots
b_0}\right)_p\] ewentualnie uzupełniając z~przodu zerami, by długości zapisu były
równe. Wtedy
\[
\binom{a}{b} \equiv \binom{a_n}{b_n}\cdot \binom{a_{n-1}}{b_{n-1}}\cdot
\dots \cdot \binom{a_0}{b_0} \mod p.
\]
\end{thm}
\end{document}
|
