\documentclass[t,professionalfont]{beamer}

\usetheme{Marija}

\input{psfig-dvips}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{multimedia}
\usepackage{epsfig}

\def \d{{\rm d}}
\def \red{\color{red}}
\def \green{\color{green}}
\def \yellow{\color{yellow}}
\def \blue{\color{blue}}
\def \magenta{\color{\magenta}}
\def \darkblue{\color[rgb]{0.00,0.00,0.46}}


\def\dj{d\kern-0.4em\char"16\kern-0.1em}

\title[{\sc Institut za matematiku i informatiku, PMF Kragujevac}]{Bernuli, Ojler i pogre\v sno adresirana pisma }

%\title[Leonhard Euler]{Leonhard Euler: 300 years old}

\author[http://imi.pmf.kg.ac.rs]{Marija Stani\'c \\
\texttt{stanicm@kg.ac.rs}\\[3mm]}

\institute[IMI, PMF]{\large Institut za matematiku i informatiku\\ Prirodno-matemati\v cki fakultet\\ Univerzitet u Kragujevcu\\[3mm]}

\date{Decembar, 2008}

\begin{document}


\begin{frame}
  \titlepage
\end{frame}



\begin{frame}
 \frametitle{\vspace*{.5cm}

 {\em
\begin{tabular}{r}
``Predmet matematike je toliko te\v zak\\
da ne treba prepustiti slu\v caju\\
da se u\v cini zanimljivim."\\[2mm]
{\rm --{\sc Pjer Simon Laplas}}\\[1cm]

``\v Steta je \v sto nisam bolje\\
znao matematiku."\\[2mm]
{\rm --{\sc Albert Ajn\v stajn}}
\end{tabular}}}

\end{frame}


\section{Bazel XVIII vek}
\begin{frame}
%right
  \frametitle{\vspace{-1cm}\begin{center}  Bazel, \v Svajcarska - centar nauke \end{center}\vspace{-1cm}}

 Bazel, kao slobodan imperatorski grad jo\v s od 1263.\ godine, dugo je bio centar nauke.
  \pause

  \vspace*{.1cm}
    Pod upravom trgova\v ckog patricijata, nauka i umetnost su cvetali u Bazelu.
   \pause

  \vspace*{.1cm}
    Tom bazelskom patricijatu pripadala je i porodica Bernuli, koja se u XVII veku tu preselila iz Antverpena kada su taj grad osvojili \v Spanci.
   \pause

  \vspace*{.1cm}
   Od kraja XVII veka ta porodica je davala po nekog nau\v cnika u svakoj generaciji.
\end{frame}


\begin{frame}
%right
  \frametitle{\vspace{-1cm}\begin{center}  Dinastija Bernuli \end{center}\vspace{-1cm}}

 Osniva\v c dinastije bio je  Nikolas Bernuli.
  \pause

  \vspace*{.1cm}
    Njegovi sinovi  Jakob (1654-1705) i Johan (1667-1748) su bili  zna\v cajni matemati\v cari.
   \pause

    \vspace*{.1cm}
    I njihov bratanac Nikolas II (1687-1759) je bio  poznati matemati\v car.
   \pause

  \vspace*{.1cm}
    Johanovi sinovi  Nikolas III (1695-1726) i Daniel (1700-1782) su tako\dj e bili istaknuti matemati\v cari.

\end{frame}



\section{Nicolas II Bernoulli (1687-1759)}
\begin{frame}
%right
  \frametitle{\vspace{-1cm}\begin{center} Nikolas II Bernuli \end{center}\vspace{-1cm}}
  $\bullet$ ortogonalne trajektorije
  \pause

  \vspace*{.1cm}
   $\bullet$ diferencijalne jedna\v cine
  \pause

  \vspace*{.1cm}
  $\bullet$ integralni ra\v cun
  \pause

  \vspace*{.1cm}

  $\bullet$ verovatno\'ca
  \pause

  \vspace*{.5cm}

  Bio je urednik sabranih dela svoga strica Jakoba Bernulija, \v clan Kraljevskog nau\v cnog dru\v stva u Londonu i \v clan Bolonjske akademije.
\end{frame}





\section{Leonhard Euler (1707-1783)}
\begin{frame}
%right
  \frametitle{\vspace{-1cm}\begin{center} Leonard Ojler \end{center}\vspace{-1cm}}
  Ojler je svakako bio jedan od najzna\v cajnijih matemati\v cara svih vremena.
  \pause

  \vspace*{.1cm}
   Napisao je preko 900 nau\v cnih radova iz \pause
  algebre,
  \pause
  diferencijalnih jedna\v cina, \pause  stepenih redova, \pause specijalnih funkcija, \pause diferencijalne geometrije, \pause
  teorije brojeva, \pause racionalne mehanike, \pause varijacionog ra\v cuna, \pause muzike, \pause optike, \pause hidrodinamike \pause i astronomije.
  \pause

  \vspace*{.1cm}
Skoro polovinu svojih radova napisao je kao potpuno slep.
\pause

  \vspace*{.1cm}
Veliki broj matemati\v ckih termina nosi njegovo ime.

\pause

  \vspace*{.1cm}
Bio je \v clan Petersbur\v ske i Berlinske akademije nauka.

\end{frame}

\begin{frame}
%right
  \frametitle{\vspace{-1cm}\begin{center}  Ojlerov disk \end{center}\vspace{-1cm}}

  \pause
  \vspace*{.4cm}
  \centerline{
    \movie[height=4.8cm,width=4.8cm]{}{eulerdisk.avi}
  }
\end{frame}

\section{Pogre\v sno adresirana pisma}
\begin{frame}
%right
  \frametitle{\vspace{-1cm}\begin{center} Problem pogre\v sno adresiranih pisama \end{center}\vspace{-1cm}}

\textit{Napisano je $k$ pisama, po jedno svakoj od $k$ razli\v citih osoba, i adresirano je $k$ koverata sa njihovim adresama.
Na koliko razli\v citih na\v cina je mogu\'ce ubaciti ova pisma u koverte tako da svako pismo bude u pogre\v snoj koverti?}
\pause
\bigskip

Ovaj problem je prvi razmatrao Nikolas II Bernuli, a nezavisno od njega kasnije ga je re\v sio i Ojler.

\end{frame}

\begin{frame}
  \frametitle{\vspace{-1cm}}

  O\v cigledno je da se u slu\v caju $k=1$ pismo ne mo\v ze ubaciti u pogre\v san koverat i da se u slu\v caju $k=2$ ta dva pisma na samo jedan na\v cin mogu ubaciti u pogre\v sno adresirane koverte. \pause \bigskip

Ozna\v cimo sa $a_1, a_2, \ldots, a_k$ pisma (objekte), a sa $P_1,P_2,\ldots,P_k$ njihove pozicije (koverte u koje su stavljena).
\pause Ako je pismo $a_i$ stavljeno u koverat $P_j$ pisa\'cemo $a_i\natural P_j$, a ako nije pisa\'cemo $a_i\ddag P_j$. \pause

Neka je $M(k)$ tra\v zeni broj pogre\v snih rasporeda. \pause U nastavku \'cemo pod {\it rasporedom} podrazumevati ponovno raspore\dj ivanje objekata pod uslovima navedenim u zadatku, bez posebnog nagla\v savanja.
\pause
\bigskip

Posmatra\'cemo dva razli\v cita slu\v caja:\pause
\begin{itemize}
  \item $a_1\natural P_2$ i $a_2\natural P_1$, dok objekti $a_3,\ldots,a_k$ zauzimaju pozicije iz skupa $\{P_3,\ldots,P_k\}$, ali tako da  $a_i\ddag P_i$, $i=3,\ldots,k$;\pause
  \item $a_1\natural P_2$, ali $a_2\ddag P_1$.
\end{itemize}
\end{frame}

\begin{frame}
  \frametitle{\vspace{-1cm}}

U prvom slu\v caju objekti $a_3,\ldots,a_k$ su distribuirani na pozicijama $P_3,\ldots, P_k$, tako da   $a_i\ddag P_i$, $i=3,\ldots,k$,
pa je broj mogu\'cih rasporeda $M(k-2)$.\pause\smallskip

Drugi slu\v caj je ekvivalentan slede\'coj situaciji: objekti $a_2,a_3,\ldots,a_k$ su distribuirani na pozicijama $P_1,P_3,\ldots,P_k$, tako da $a_2\ddag P_1$, $a_3\ddag P_3$, \ldots, $a_k\ddag P_k$. Prema tome broj rasporeda u ovom slu\v caju je $M(k-1)$.\pause \medskip

Na osnovu ova dva slu\v caja zaklju\v cujemo da je broj rasporeda u kojima se pismo $a_1$ nalazi u kovertu $P_2$ jednak $M(k-2)+M(k-1)$. \pause  \smallskip

Sli\v cnu analizu mo\v zemo ponoviti pri odre\dj ivanju broja rasporeda u kojima je redom $a_1\natural P_3$, $a_1\natural P_4$, \ldots, $a_1\natural P_k$. \pause Ovaj broj je uvek isti: \[M(k-2)+M(k-1).\]

\end{frame}

\begin{frame}
  \frametitle{\vspace{-1cm}}

Ukupan broj svih dozvoljenih rasporeda je
\[M(k)=(k-1)\bigl(M(k-2)+M(k-1)\bigr).\]
\pause
Poslednja rekurentna relacija se mo\v ze napisati u obliku
\[M(k)-k M(k-1)=-\bigl(M(k-1)-(k-1)M(k-2)\bigr). \leqno{{\darkblue(\clubsuit)}}\]
\pause
Ako obele\v zimo $N_i=M(i)-i M(i-1)$, tada {\darkblue$(\clubsuit)$} postaje
\[N_i=-N_{i-1}.\]
\pause
Uzimaju\'ci redom $i=3,\ldots,k$, dobijamo
\[N_3=-N_2, \;\; N_4=-N_3, \;\; N_5=-N_4, \; \ldots,\; N_k=-N_{k-1},\]
\pause
pa je
\[N_k=-N_{k-1}=(-1)^2N_{k-2}=(-1)^3N_{k-3}=\cdots=(-1)^{k-2}N_2,\]
\end{frame}

\begin{frame}
  \frametitle{\vspace{-1cm}}

\noindent tj.
\[M(k)-kM(k-1)=(-1)^{k-2}\bigl(M(2)-M(1)\bigr).\]
\pause
Kako je $M(1)=0$, $M(2)=1$ i $(-1)^{k-2}=(-1)^k$, iz prethodne jednakosti dobijamo
\[ M(k)-kM(k-1)=(-1)^k.\]
\pause
Ako obe strane prethodne jednakosti podelimo sa $k!$ dobi\'cemo
\[\frac{M(k)}{k!}-\frac{M(k-1)}{(k-1)!}=\frac{(-1)^k}{k!}.\leqno{{\darkblue (\spadesuit)}}\]
\pause\medskip

Napi\v simo sada jednakost {\darkblue $(\spadesuit)$} za $k=2,3,\ldots,k$.
\end{frame}

\begin{frame}
  \frametitle{\vspace{-1cm}}

\begin{eqnarray*}
\frac{M(2)}{2!}-\frac{M(1)}{1!}&\!\!\!\!=&\!\!\!\!\frac{(-1)^2}{2!},\pause\\
\frac{M(3)}{3!}-\frac{M(2)}{2!}&\!\!\!\!=&\!\!\!\!\frac{(-1)^3}{3!},\pause\\
\frac{M(4)}{4!}-\frac{M(3)}{3!}&\!\!\!\!=&\!\!\!\!\frac{(-1)^4}{4!},\pause\\
&\!\!\! \vdots \pause\\
\frac{M(k)}{k!}-\frac{M(k-1)}{(k-1)!}&\!\!\!\!=&\!\!\!\!\frac{(-1)^k}{k!}.
\end{eqnarray*}
\pause
Sabiranjem ovih $k-1$ jednakosti ($M(1)=0$) dobijamo
\[\frac{M(k)}{k!}=\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+\frac{(-1)^4}{4!}+\cdots+\frac{(-1)^k}{k!},\]
\end{frame}

\begin{frame}
  \frametitle{\vspace{-1cm}}

pa, kona\v cno, dobijamo krajnji rezultat
\[M(k)=k!\left(\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+\frac{(-1)^4}{4!}+\cdots+\frac{(-1)^k}{k!}\right).\]
\pause

Na primer, prvih nekoliko vrednosti je:
\[M(3)=2, \;\; M(4)=9, \;\; M(5)=44, \;\; M(6)=265, \;\; M(7)=1854.\]
\end{frame}

\section{Nenapadaju\'ci topovi}
\begin{frame}
%right
  \frametitle{\vspace{-1cm}\begin{center} Problem nenapadaju\'cih topova \end{center}\vspace{-1cm}}

\textit{Neka je $Q_n$, $n\ge 2$, broj na\v cina na koji se $n$ topova mo\v ze postaviti na \v sahovsku tablu $n\times n$, tako da se topovi me\dj usobno ne napadaju i da se nijedan top ne nalazi na glavnoj dijagonali. Podrazumeva se da glavna dijagonala ide od donjeg levog ugaonog polja, do gornjeg desnog ugaonog polja. Odrediti $Q_n$ za proizvoljno $n$.}\pause\bigskip

Dva razli\v cita topa moraju se nalaziti u razli\v citim vrstama i razli\v citim kolonama \v sahovske table.
\pause Svako polje \v sahovske table mo\v ze se predstaviti ure\dj enim parom $(i,j)$, gde je $i$ broj vrste,
a $j$ broj kolone, pri \v cemu je $(1,1)$ donje levo ugaono polje, a $(n,n)$ gornje desno ugaono polje.
Nijedan top se ne sme na\'ci na pozicijama oblika $(i,i)$, $i=1,\ldots,n$.
\end{frame}

\begin{frame}
%right
  \frametitle{\vspace{-1cm}}
  \centerline{\epsfig{figure=top1.eps, height=4.5cm}} \pause
  \medskip

Postavljeni problem nenapadaju\'cih topova je ekvivalentan problemu pogre\v sno adresiranih pisama. \pause

Prema tome:
\[Q_n=n!\left(\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+\frac{(-1)^4}{4!}+\cdots+\frac{(-1)^n}{n!}\right).\]
\end{frame}

\section{}
\begin{frame}
 \frametitle{\vspace{-1cm}\begin{center} That's all folks! \end{center}\vspace{-1cm}}

 \vspace*{1cm}

 \begin{center}{\red{\bf\huge HVALA NA PA\v ZNJI \\[3mm]
 I STRPLJENJU!}}
 \end{center}
\end{frame}

\end{document}
