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[OT4]{fontenc}
 
\usepackage[utf8]{inputenc}
 
% ----------------------------------------------------------------
 
\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{Kółko 24.11 - indukcja$^{-1}$}
 
\date{}
 
\maketitle
 
\paragraph{\textbf{Teoria}}
 
\begin{enumerate}
 
%\item Zasada indukcji matematycznej i rozszerzona zasada indukcji matematycznej ($T(1),T(2),...,T(n)\Rightarrow T(n+1)$).
 
\item Zasada nieskończonego schodzenia (bez formalnej definicji, bo to się może przyśnić).
 
\end{enumerate}
 
\paragraph{\textbf{Zadanka :) }}
 
\begin{enumerate}
 
%  \item Klasyczny dowód nierówności pomiędzy średnią arytmetyczną i geometryczną $\frac{a_1+...+a_n}{n}\geq \sqrt[n]{a_1a_2...a_n}$, przez "`indukcję"' $T(n+1)\Rightarrow T(n)$ i $T(n)\Rightarrow T(2n)$.
 
  \item Udowodnić, że $\sqrt{2}$ nie jest wymierne.
 
  \item Znaleźć wszystkie rozwiązania równania $8x^4+4y^4+2z^4=t^4$ w liczbach całkowitych nieujemnych.
 
  \item Znaleźć wszystkie rozwiązania równania $x^2+y^2+z^2+u^2=2xyzu$ w liczbach $\mathbb{N}_+$.
 
  \item Udowodnić, że $7$ nie sa się przedstawić w postaci sumy 3 kwadratów liczb wymiernych dodatnich.
 
  \item Udowodnij, że liczba postaci $4^n(8k-1)$, gdzie $k,n\in\mathbb{N}_+$ nie jest kwadratem innej liczby naturalnej i nie może być przedstawiona jako suma 1, 2 lub 3 kwadratów liczb naturalnych dodatnich.
 
  \item Ciąg $a_1,...,a_n$ ($a_i\in\mathbb{N}_+$) przetwarzamy na ciąg postaci $\frac{a_1+a_2}{2},\frac{a_2+a_3}{2},...,\frac{a_{n-1}+a_n}{2},\frac{a_n+a_1}{2}$, ten ciąg przetwarzamy analogicznie itd. Udowodnij, że po pewnej liczbie takich operacji albo otrzymany ciąg będzie stały, albo będzie on zawierać wyrazy niecałkowite.
 
  \item Niech $a_1,...,a_{2^n}$ będzie ciągiem liczb naturalnych. Udowodnij, że jeśli utworzymy z niego nowy ciąg $l_1,l_2,\cdots,l_{2^n}$ według reguły $l_k=|a_{k+1}-a_{k}|$ (umawiamy się, że $a_{2^n+1}=a_1$), a niego następny ciąg itd., to w końcu dojdziemy do ciągu złożonego z samych zer. Czy dla ciągu $(a_n)$ jest to nadal prawdziwe, gdy $n$ nie jest potęgą 2?
 
\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[OT4]{fontenc}
 
\usepackage[utf8]{inputenc}
 
% ----------------------------------------------------------------
 
\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{Kółko 24.11 - indukcja$^{-1}$}
 
\date{}
 
\maketitle
 
\paragraph{\textbf{Zadanka}}
 
\begin{enumerate}
 
  \item Udowodnić, że $\sqrt{2}$ nie jest wymierne.\\
 
    Załóżmy, że $\sqrt{2}$ jest wymierne. Jakoże jest ono większe od 0, to można je przedstawić w postaci $\frac{p}{q}$, to gdzie $p, q\in Z_+$. Mamy wtedy $\sqrt{2}=\frac{p}{q}$, a po podniesieniu do kwadratu i pomnżeniu przez $q^2$ dostajemy $2q^2=p^2$. Załóżmy, że $p_0,q_0$ jest parą o najmniejszej sumie spełniającą to równanie. Jest $2|p_0^2$, a stąd $2|p_0$. Niech $p_1=p_0/2$. Wtedy jest $2q_0^2=4p_1^2$, więc $4|2q_0^2$ i $2|q_0^2$. Tym samym $2|q_0$ i $q_0=q_1/2$, gdzie $q_1$ - całkowite. Mamy więc $2q_1^2=p_1^2$, co przeczy wyborowi $p_0,q_0$ jako pary o najmniejszej sumie (bo $p_0+q_0 > p_1 + q_1$).
 
  \item Znaleźć wszystkie rozwiązania równania $8x^4+4y^4+2z^4=t^4$ w liczbach całkowitych nieujemnych.\\
 
  Weźmy dowolne rozwiązanie tego równania w liczbach $x,y,z,t$. Mamy dla takich liczb $8x^4+4y^4+2z^4=t^4$, a stąd $2|t$ i $t/2=t_1$, $t_1\in Z$. Podstawiając dostajemy $8x^4+4y^4+2z^4=16t_1^4$, a po podzieleniu przez $2$, $4x^4+2y^4+z^4=8t_1^4$, z czego wynika, że $2|z$ i $z/2=z_1$, $z_1\in Z$. Po kolejnym podstawieniu i podzieleniu dostajemy $2x^4+y^4+8z_1^4=4t_1^4$, a więc $2|y$ i $y/2=y_1$, gdzie $y_1\in Z$. Powtarzając te operacje dostajemy $2|x$ i $x/2=x_1$, $x_1\in Z$. Podstawiając to dostajemy $8x_1^4 + 4y_1^4 + 2z_1^4 = t_1^4$.\\
 
  Otrzymaliśmy to samo równanie, więc podane operacje możemy powturzyć $n$ razy dla dowolnego $n$, stwierdzając, że $2^n|x$ i $2^n|y$ i $2^n|z$ i $2^n|t$ dla dowolnego $n$. Jedyną liczbą całkowitą podzielną przez dowolną potęgę $2$ jest 0. Tym samym jedynym rozwiązaniem w liczbach całkowitych nieujemnych może być $(0,0,0,0)$. Te liczby faktycznie spełniają równanie.
 
  \item Znaleźć wszystkie rozwiązania równania $x^2+y^2+z^2+t^2=2xyzt$ w liczbach $\mathbb{N}_+$.\\
 
  Zauważmy, że dla $x,y,z,t$ spełniających to równanie musi być $2|x^2+y^2+z^2+t^2$. $x^2$ daje resztę $1$ z dzielenia przez 2, gdy $x$ jest nieparzyste, a $0$, gdy $x$ parzyste. Stąd widzimy, że wśród liczb $x,y,z,t$ musi być parzysta ilość nieparzystych. Rozważmy 3 przypadki:
 
  \begin{enumerate}
 
  \item 4 liczby $x,y,z,t$ są nieparzyste. Jeżeli $x$ jest nieparzyste, to $x^2\equiv 1 (\mod 8)$ (sprawdź), więc $x^2+y^2+z^2+t^2\equiv 4 (\mod 8)$. Ale mamy $2\not|xyzt$, więc $4\not|2xyzt$. Sprzeczność.
 
  \item 2 liczby z $x,y,z,t$ są nieparzyste. Wtedy mamy $x^2+y^2+z^2+t^2\equiv 2 (\mod 4)$, więc $4\not|x^2+y^2+z^2+t^2$, a $4|xyzt$, więc sprzeczność.
 
  \item Wszystkie liczby $x,y,z,t$ są parzyste. Weźmy $x/2=x_1,y/2=y_1,z/2=z_1,t/2=t_1$. Dostajemy $4x_1^2+4y_1^2+4z_1^2+4t_1^2=2\cdot16x_1y_1z_1t_1$, czyli $x_1^2+y_1^2+z_1^2+t_1^2=8xyzt$. Dalej biorąc $\mod 8$ dostajemy łatwo, że $x_1,y_1,z_1,t_1$ są parzyste, więc możemy podstawić $x_2=x_1/2$ itd. Musi więć znowu być $2^n|x,y,z,t$ dla dowolnego $n\in Z_+$, więc $x=y=z=t=0$. Ale te liczby nie są naturalne dodatnie, więc ostatecznie nie ma rozwiązań.
 
  \end{enumerate}
 
  \item Udowodnić, że $7$ nie sa się przedstawić w postaci sumy 3 kwadratów liczb wymiernych dodatnich.
 
  Mamy $x^2\equiv 1 (\mod 8)$ lub $x^2\equiv 4(\mod 8)$, lub $x^2\equiv 0(\mod 8)$.\\
 
  Jeżeli $7=(\frac{p_1}{q_1})^2+(\frac{p_2}{q_2})^2+(\frac{p_3}{q_3})^2$, gdzie $p_i,q_i\in Z_+$, to wymnażając stronami $7(q_1q_2q_3)^2=(p_1q_2q_3)^2+(q_1p_2q_3)^2+(p_1p_2q_3)^2$. Jeżeli wykażemy, że równanie $7d^2=a^2+b^2+c^2$ w całkowitych nie ma rozwiązań, to wykażemy również tezę. Rozpatrzmy to równanie $(\mod 8)$. $a^2+b^2+c^2$ daje reszty $0,1,2,3,4,5,6$ (sprawdź), zaś wyrażenie $7d^2$ daje reszty $0,7,4$. Widzimy, że reszty $\mod 8$ są równe tylko jeśli $a^2+b^2+c^2$ przystaje do $0$ lub $4$ $(\mod 7)$, a wtedy liczby $(a,b,c,d)$ są parzyste (sprawdź) i podobnie jak w poprzednich zadaniach wnioskujemy, że $2^n|a,b,c,d$ dla dowolnego $n$. 
 
  \item Udowodnij, że liczba postaci $4^n(8k-1)$, gdzie $k,n\in\mathbb{N}_+$ nie jest kwadratem innej liczby naturalnej i nie może być przedstawiona jako suma 1, 2 lub 3 kwadratów liczb naturalnych dodatnich.\\
 
  Mamy udowodnić, że $4^n(8k-1)=a^2+b^2+c^2$, gdzie $a,b,c\in N_+\cup\{0\}$ nie ma rozwiązań. Faktycznie jeżeli $n=0$, to patrząc $\mod 8$ otrzymujemy speczność bo $a^2+b^2+c^2 (\mod 8)\in\{0,1,2,3,4,5,6\}$. Jeżeli zaś $n>0$, to patrząc $\mod 4$ dowiadujemy się, że $2|a,b,c$ i możemy podstawić $a_1=a/2$ i $b_1=b/2$, $c_1=c/2$ i podzielić przez 4, a dzielić przez 4 możemy skończoną ilość razy.
 
%  \item Ciąg $a_1,...,a_n$ ($a_i\in\mathbb{N}_+$) przetwarzamy na ciąg postaci $\frac{a_1+a_2}{2},\frac{a_2+a_3}{2},...,\frac{a_{n-1}+a_n}{2},\frac{a_n+a_1}{2}$, ten ciąg przetwarzamy analogicznie itd. Udowodnij, że po pewnej liczbie takich operacji albo otrzymany ciąg będzie stały, albo będzie on zawierać wyrazy niecałkowite.\\
 
%  Popatrzmy na ciąg $\frac{a_1+a_2}{2},\frac{a_2+a_3}{2},...,\frac{a_{n-1}+a_n}{2},\frac{a_n+a_1}{2}$. Jeżeli ma on wyrazy całkowite, to znaczy, że $a_1\equiv a_2\equiv\cdots\equiv a_n (\mod 2)$. Zauważmy, że jeżeli zapiszemy liczby $a_i$ w systemie binarnym, to jeśli po przetworzeniu $n$ razy otrzymamy wciąż ciąg całkowity, to znaczy, że na $n$ pierwszych miejscach w zapisie binarnym liczby $a_1,\cdots,a_n$ są identyczne (sprawdź przez indukcję). Jeżeli więc po każdej ilości przetworzeń ciąg wciąż będzie całkowity, znaczy, że początkowo wszystkie $a_1,\cdots,a_n$ były równe, więc ciąg początkowy był stały (jak i każdy kolejny).
 
%  \item Niech $a_1,...,a_{2^n}$ będzie ciągiem liczb naturalnych. Udowodnij, że jeśli utworzymy z niego nowy ciąg $l_1,l_2,\cdots,l_{2^n}$ według reguły $l_k=|a_{k+1}-a_{k}|$ (umawiamy się, że $a_{2^n+1}=a_1$), a niego następny ciąg itd., to w końcu dojdziemy do ciągu złożonego z samych zer. Czy dla ciągu $(a_n)$ jest to nadal prawdziwe, gdy $n$ nie jest potęgą 2?\\
 
%  Może to jeszcze ktoś rozwali więc poczekam z ogłaszaniem rozwiązania.
 
\end{enumerate}
 
\end{document}