%!TEX TS-program = xelatex
%!TEX encoding = UTF-8 Unicode

\documentclass[11pt,a4paper]{article}
\usepackage[margin=1in]{geometry}

% ========================================================================================
% Packages
% ========================================================================================

\usepackage{xcolor}
\usepackage{hyperref}

\hypersetup{
    colorlinks = true, % Colors links instead of ugly boxes
    urlcolor   = blue, % Color for external hyperlinks
    linkcolor  = blue, % Color of internal links
    citecolor  = red   % Color of citations
}

\usepackage{graphicx}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{mathtools}
\usepackage{booktabs}
\usepackage{fancyvrb}

% ========================================================================================
% Fonts and hyphenation. Change the fonts to suit your needs.
% ========================================================================================

\usepackage{libertine}

\usepackage{polyglossia}
\setmainlanguage[variant=mono,numerals=arabic]{greek}
\setotherlanguage[variant=usmax]{english}

% Mark any english text for proper hyphenation

\newcommand{\en}[1]{\textlang{english}{#1}}

% Convenience

\newcommand{\R}[1]{\mathbb{R}^{#1}}

% ========================================================================================
% Article data
% ========================================================================================

\title{\vspace{-2em}MEM291 Σχεδίαση και Ανάλυση Αλγορίθμων\\
1ο φυλλάδιο ασκήσεων}
\author{Μιχάλης Πλεξουσάκης\\ Τμήμα Μαθηματικών \& Εφαρμοσμένων Μαθηματικών}
\date{}

% ========================================================================================
% Begin document
% ========================================================================================

\begin{document}

% ========================================================================================
% Title page
% ========================================================================================

\maketitle

% ========================================================================================
% Main body
% ========================================================================================

\begin{enumerate}
%
\item Αποδείξτε με επαγωγή ότι
%
\begin{equation} \label{eq:ind}
1 + \dfrac{1}{4} + \dfrac{1}{9} + \cdots + \dfrac{1}{n^2} < 2 - \dfrac{1}{n},
\end{equation}
%
για κάθε $n > 1$.
\begin{proof}
Η σχέση \eqref{eq:ind} ισχύει για $n = 2$ γιατί
%
\begin{equation*}
    1 + \dfrac{1}{4} = \dfrac{5}{4} < 2 - \dfrac{1}{2} = \dfrac{3}{2}.
\end{equation*}
%
Έστω τώρα ότι η \eqref{eq:ind} ισχύει για κάποιο $n \ge 2$. Tότε, από την επαγωγική υπόθεση έχουμe
%
\begin{align*}
1 + \dfrac{1}{4} + \dfrac{1}{9} + \cdots + \dfrac{1}{n^2}  + \dfrac{1}{(n+1)^2} &< 2 - \dfrac{1}{n} + \dfrac{1}{(n+1)^2}\\
    &< 2 - \dfrac{1}{n} + \dfrac{1}{n(n+1)}\\
    &= 2 - \dfrac{1}{n+1},
\end{align*}
%
το οποίο ολοκληρώνει την επαγωγική απόδειξη.
\end{proof}
%
\item Δείξτε ότι μεταξύ 95 φοιτητών/φοιτητριών σε μια τάξη, η πιθανότητα δύο από αυτούς να έχουν γενέθλια την ίδια μέρα
είναι μεγαλύτερη από $0.99999$.
%
\begin{proof}
Θα υποθέσουμε ότι η πιθανότητα ένας τυχαία επιλεγμένος φοιτητής/φοιτήτρια να έχει γενέθλια μια συγκεκριμένη μέρα είναι
$1/d$, όπου $d = 365$. Υποθέτουμε επίσης ότι η τάξη αποτελείται από $n = 95$ τυχαία και ανεξάρτητα επιλεγμένους
φοιτητές/φοιτήτριες.

Με αυτές τις υποθέσεις υπάρχουν $d^n$ ακολουθίες γενεθλίων, όλες το ίδιο πιθανές, και ακριβώς
\begin{equation*}
    d (d - 1) \cdots (d - (n - 1))
\end{equation*}
ακολουθίες γενεθλίων σε διαφορετικές ημερομηνίες. Συνεπώς, η πιθανότητα να έχουν όλοι διαφορετικές ημερομηνίες γενεθλίων
είναι
%
\begin{align}\label{eq:bday1}
    \dfrac{ d (d - 1) \cdots (d - (n - 1)) }{d^n} &= \dfrac{d}{d} \cdot \dfrac{d-1}{d} \cdots \dfrac{d - (n-1)}{d}\nonumber\\
    &= \left(1 - \dfrac{0}{d}\right) \cdot \left(1 - \dfrac{1}{d}\right) \cdots
    \left(1 - \dfrac{n-1}{d}\right).
\end{align}
%
Χρησιμοποιώντας τώρα το γεγονός ότι $1 + x \le e^x$ για κάθε $x\in\mathbb{R}$, έχουμε
%
\begin{equation}\label{eq:bday2}
\left(1 - \dfrac{0}{d}\right) \cdot \left(1 - \dfrac{1}{d}\right) \cdot
    \left(1 - \dfrac{n-1}{d}\right) \le
    e^0 \cdot e^{-1/d} \cdot e^{-(n-1)/d} = e^{-n(n-1)/2d}.
\end{equation}
%
Οι σχέσεις \eqref{eq:bday1} και \eqref{eq:bday2} δείχνουν ότι η πιθανότητα όλοι οι φοιτητές/φοιτήτριες να έχουν γενέθλια
σε διαφορετικές μέρες είναι
%
\begin{equation*}
    \dfrac{ d (d - 1) \cdots (d - (n - 1)) }{d^n} \le e^{-n(n-1)/2d} \approx 0.0000048\,6776 < 0.000005 = \dfrac{1}{200\,000}.
\end{equation*}
%
Επομένως, η πιθανότητα να υπάρχει ζεύγος φοιτητών/φοιτητριών με την ίδια ημερομηνία γενεθλίων είναι μεγαλύτερη από
$1 - 0.000005 = 0.999995 > 0.99999$. 
\end{proof}
%
\end{enumerate}
%
\end{document}

% ========================================================================================
% Done!
% ========================================================================================

\end{document}
