|
Zadania PDF.
Źródło zadań w texu.
% File: zadanka.tex
% Created: Tue Feb 26 09:00 AM 2013 C
% Last Change: Tue Feb 26 09:00 AM 2013 C
\documentclass[10pt, a4paper]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[textwidth=16cm, textheight=25.5cm]{geometry}
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{polski}
\usepackage{graphicx}
\usepackage{enumitem}
\setenumerate{itemsep=2pt,topsep=2pt,parsep=0pt,partopsep=0pt}
\usepackage[cmyk,usenames,dvipsnames]{xcolor}
\definecolor{background-gray}{gray}{0.95}
\definecolor{border-gray}{gray}{0.65}
%\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}
\newtheorem{cor}[thm]{Wniosek}
\newtheorem{lem}[thm]{Lemat}
\newtheorem{defn}[thm]{Definicja}
\newtheorem{tozs}[thm]{Tożsamość}
\newtheorem{hyp}[thm]{Hipoteza}
\newtheorem{example}[thm]{Przykład}
\newtheorem{obs}[thm]{Obserwacja}
\newcommand{\HRule}{\rule{\linewidth}{0.2mm}}
\renewcommand{\section}[1]{
%\vspace*{-1.5cm}
\stepcounter{section}%
\begin{center}%
\begin{minipage}{2.5cm}
\includegraphics[origin=c,width=2.5cm]{\headpicture}
\end{minipage}\begin{minipage}{\sectionwidth}
\begin{center}
{\Huge \bfseries \center #1}
\vskip 1mm
\small \normalfont \sc
\author{}\\
\date{}
\end{center}
\end{minipage}
\end{center}
\HRule
}
\newenvironment{sol}[1][Rozwiązanie. ]{
\vskip 3mm
\noindent\emph{#1}
}
{
}
\newcounter{problem}
\newenvironment{problem}[1][]{
\stepcounter{problem}
\vskip 3mm
\noindent{\textsc{{\bfseries Zadanie \theproblem{}} #1}}\\}
{
}
\pagestyle{empty}
\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}
\def\sectionwidth{8cm}
\def\headpicture{../micek-2cm.jpg}
\def\author{kółko I~LO Białystok}
\def\date{26 lutego 2013}
\newcommand{\infobox}[1]{%
\noindent
\fcolorbox{border-gray}{background-gray}{#1}
}
\begin{document}
\section{Algorytm Euklidesa}
\begin{problem}
Jeżeli $a$ jest iloczynem potęg liczb pierwszych
$p_1^{a_1},\dots,p_k^{a_k}$, zaś $b$ jest iloczynem potęg tych samych liczb
pierwszych $p_1^{b_1},\dots,p_k^{b_k}$ to ile wynosi $NWD(a, b)$?
\end{problem}
\begin{problem}
Dla jakich liczb naturalnych $n$ ułamek
\[
\frac{3n + 4}{2n + 5}
\]
jest liczbą całkowitą?
\end{problem}
\paragraph{Rozszerzony algorytm Euklidesa} Dla danych $a, b$ całkowitych
dodatnich chcemy użyć algorytmu Euklidesa do znalezienia liczb $x, y$ całkowitych takich, że
\[x\cdot a + y\cdot b = NWD(a, b).\]
\def\result#1{\infobox{#1}}
\def\floor#1{\left\lfloor #1 \right\rfloor}
Przeanalizujmy ciąg równości:
\[1 = NWD(0, 1) = NWD(2 - 2\cdot 1, 1) = NWD(2, 1) = NWD(1, 2) = NWD(7
-3\cdot 2, 2) = NWD(7, 2),\]
\[
1 = 1\cdot \result{0} + 1\cdot \result{1} = 1\cdot \left(\result{2} - 2\cdot
\result{1}\right) + 1\cdot \result{1} = 1\cdot \result{2} - 1 \cdot
\result{1} = -1\cdot \result{1} + 1\cdot \result{2} =
\]
\[
-1\cdot \left( \result{7} - 3\cdot \result{2} \right) + 1\cdot \result{2}
= -1\cdot \result{7} + 4\cdot \result{2}.
\]
Poniżej podajemy pseudokod uogólnionego algorytmu:
\begin{enumerate}
\item Załóżmy $a\neq 0$.
Niech $x', y'$ będą wartościami zwróconymi przez
$NWD(b, a\mod b)$. Znaczy to, że
\[x'\cdot b + y'\cdot (a\mod b)
= NWD(a, b).\] Podstawiamy $a\mod b = a - k\cdot b$, czyli
\[
y'\cdot a + (x' - y'k)\cdot b = x'\cdot b + y'\cdot (a -
k\cdot b) = NWD(a, b),
\]
więc zwracamy $y', x' - y'k$. Możemy przy tym zauważyć, że $k=\floor{a/b}$.
\item Załóżmy $a = 0$. Wtedy zwracamy $1, 1$, bo $1\cdot 0 + 1\cdot b
= b = NWD(a, b)$.
\end{enumerate}
\begin{problem}
Niech $a, b, d$ będą całkowite.
Równanie $x\cdot a + y\cdot b = d$ ma rozwiązanie w~liczbach
całkowitych $x, y$ wtedy i~tylko wtedy, gdy $NWD(a, b)\big|d$.
\end{problem}
\begin{problem}[Chińskie twierdzenie o~resztach]
Załóżmy, że liczby całkowite dodatnie $a, b$ są względnie pierwsze.
Dla dowolnych reszt $r_1\mod a,\ \ r_2 \mod b$ istnieje liczba
całkowita $M$ taka, że
\[M \equiv r_1 \mod a\quad\mbox{oraz}\quad M\equiv r_2 \mod b.\]
\emph{Wskazówka: rozważ najpierw reszty $(1, 0)$ i~$(0, 1)$.}
\end{problem}
\begin{problem}[Konstruowanie odwrotności $\mod n$]
Dana są liczby względnie pierwsze $a, n$.
Pokaż, jak przy pomocy algorytmu Euklidesa znaleźć liczbę $b$ taką, że
$a\cdot b \equiv 1 \mod n$.
Zastosuj opisaną procedurę do znalezienia liczby $b$ takiej, że $8b
\equiv 1 \mod 61$. Spróbuj również znaleźć liczbę $b$ taką, że $8b
\equiv 1 \mod 41$.
\end{problem}
\begin{problem}
Dla których $x$ całkowitych liczba $x^3 + 3\cdot x^2 + 3\cdot
x$ jest podzielna przez $x^2 + 2x + 1$?
\end{problem}
\begin{problem}
Wyznaczyć wszystkie liczby $a\in \mathbb{R}$, dla
których wielomiany $f(x)=x^5 +ax^3+x^2+1$ i~${g(x)=x^4+ax^2+x+1}$
mają wspólny pierwiastek.
\end{problem}
\end{document}
|
