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

\documentclass[a4paper,11pt]{article}
%
\usepackage{amsmath}
%
\usepackage[a4paper,textwidth=6in,textheight=9in,marginparsep=7pt,marginparwidth=0.6in]{geometry}
\usepackage{xltxtra}
\usepackage{xgreek}
\usepackage{color}
%
\defaultfontfeatures{Scale=MatchLowercase,Mapping=tex-text}
\setmainfont{Linux Libertine O}
\setmonofont[Scale=0.90,Ligatures=NoCommon]{Courier New}
%
%
\title{ΤΕΜ-201 Διακριτά Μαθηματικά--1ο Φυλλάδιο Ασκήσεων}
\author{Μιχάλης Πλεξουσάκης}
%
\begin{document}
\maketitle
%
%
\begin{enumerate}
%
%
\item \textbf{Άσκηση 1.47}. Θα δείξουμε, με επαγωγή, ότι
%
\begin{equation*}
n^3 = \sum_{i=1}^n \left( n(n-1) + 2i-1 \right).
\end{equation*}
%
Η σχέση αυτή ισχύει, προφανώς, για $n=1$. Έστω ότι ισχύει για τον φυσικό αριθμό $k\ge 1$. Τότε,
%
\begin{equation*}
\begin{aligned}
\sum_{i=1}^{k+1} \left( (k+1)k + 2i-1 \right) &= \sum_{i=1}^k \left( (k+1)k + 2i-1 \right) + (k+1)k + 2(k+1)-1\\
&= \sum_{i=1}^k \left( (k+1)k + {\color{red}k(k-1) - k(k-1)} + 2i-1 \right) + k^2 + 3k +1\\
&= \sum_{i=1}^k \left( k(k-1) + 2i-1 \right) + \sum_{i=1}^k \left( (k+1)k - k(k-1) \right)\\
&\quad + k^2 + 3k +1.
\end{aligned}
\end{equation*} 
%
Κάνοντας χρήση της επαγωγικής υπόθεσης έχουμε
%
\begin{equation*}
\begin{aligned}
\sum_{i=1}^{k+1} \left( (k+1)k + 2i-1 \right) &= k^3 + 2\sum_{i=1}^k k + k^2 + 3k +1\\
&= k^3 + 2k^2 + k^2 + 3k +1\\
& = (k+1)^3.
\end{aligned}
\end{equation*}
%
%
\item \textbf{'Ασκηση 1.54}.  Στο πρώτο ερώτημα της άσκησης μας ζητείται να βρούμε το πλήθος των ακεραίων στο διάστημα $[1, 300]$ που
δεν διαιρούνται από το 3, ούτε από το 5, ούτε από το 7.  Έστω $A_3$ το σύνολο των αριθμών στο διάστημα $[1, 300]$ που διαιρούνται με το
3, $A_5$ το σύνολο των αριθμών στο διάστημα $[1, 300]$ που διαιρούνται με το 5 και $A_7$ το σύνολο των αριθμών στο
διάστημα $[1, 300]$ που διαιρούνται με το 7. Η απάντηση στο ερώτημα της άσκησης είναι $300-|A_3\cup A_5\cup A_7|$, μια και
$A_3\cup A_5\cup A_7$ είναι το σύνολο των αριθμών στο διάστημα $[1, 300]$ που διαιρούνται με \textbf{τουλάχιστον έναν} εκ τών 3, 5, και 7.
Έχουμε λοιπόν,
%
\begin{gather*}
|A_3| = 100, \quad |A_5| = 60, \quad |A_7| = 42,\\
|A_3\cap A_5| = 20, \quad |A_3\cap A_7| = 14, \quad |A_5\cap A_7| = 8, \quad |A_3\cap A_5\cap A_7| = 2,
\end{gather*}
%
επομένως $|A_3\cup A_5\cup A_7| = 100 + 60 + 42 - 20 - 14 - 8 + 2 = 162$. Η απάντηση στο πρώτο ερώτημα  της άσκησης είναι $300-162=138$.

Στο δεύτερο ερώτημα της άσκησης μας ζητείται να βρούμε το πλήθος των αριθμών στο διάστημα $[1, 300]$ που διαιρούνται από το 3 αλλά όχι από
το 5 και το 7.  Είδαμε ότι 100 αριθμοί διαιρούνται με το 3. Απο αυτούς, $|A_3\cap A_5| = 20$ διαιρούνται και με το 5, $|A_3\cap A_7| = 14$ διαιρούνται
και με το 7 και $|A_3\cap A_5\cap A_7| = 2$ διαιρούνται και με το 5 και με το 7. Επομένως το πλήθος των αριθμών που διαιρούνται με το 3 αλλά όχι
με το 5 και το 7 είναι $100-20-14+2 = 68$.
%
%
\item \textbf{'Ασκηση 1.56}. Έστω $K$  το σύνολο των κεντρώων, $\Gamma$  το σύνολο των ανθρώπων που φορούν γυαλιά και $\Pi$ το σύνολο των
ανθρώπων που τους αρέσει το παγωτό. Από τα δεδομένα της άσκσης έχουμε
%
\begin{gather*}
|K| = 595,\quad |\Gamma| = 595, \quad |\Pi| = 550,\\
|K \cap \Gamma| = 395,\quad |K \cap \Pi| = 350,\quad |\Gamma \cap \Pi| = 400, \quad |K\cap \Gamma \cap \Pi | = 250    
\end{gather*}
%
 Στο πρώτο ερώτημα της άσκησης ζητείται να βρούμε πόσοι άνθρωποι που δεν είναι κεντρώοι δεν φορούν γυαλιά και δεν τους αρέσει το παγωτό. Το πλήθος
 τους είναι το συνολικό πλήθος των ανθρώπων, δηλαδή 1000, αν αφαιρέσουμε αυτούς που είτε είναι κεντρώοι, είτε φορούν γυαλιά, είτε τους αρέσει
 το παγωτό, δηλαδή  $1000 - |K\cup \Gamma \cup \Pi |$. Έχουμε
 %
 \begin{equation*}
 \begin{aligned}
 |K\cup \Gamma \cup \Pi | &= |K| + |\Gamma| + |\Pi| - |K \cap \Gamma| - |K \cap \Pi| -  |\Gamma \cap \Pi| + |K\cap \Gamma \cap \Pi |\\
 &= 595 + 595 + 550 - 395 - 350 - 400 + 250\\
 &= 845,
 \end{aligned}
 \end{equation*}
 άρα  $1000-845=155$ δεν είναι κεντρώοι, δεν φορούν γυαλιά και δεν τους αρέσει το παγωτό.
 
 Στο δεύτερο ερώτημα της άσκησης ζητείται να βρούμε πόσοι είναι κεντρώοι και δεν φορούν γυαλιά και δεν τους αρέσει το παγωτό. Από το συνόλο
 των κεντρώων, $|K \cap \Gamma| = 395$ φορούν γυαλιά, $|K \cap \Pi| = 350$ τους αρέσει το παγωτό και $|K\cap \Gamma \cap \Pi | = 250$ 
 φορούν γυαλιά και τους αρέσει το παγωτό. Επομένως το πλήθος των κεντρώων που δε φορούν γυαλιά και δεν τους αρέσει το παγωτό είναι
 $595-395-350+250 = 100$.
 %
 %
 \item \textbf{'Ασκηση 1.59}. Έστω $H$ σύνολο των φοιτητών που φορούν καπέλο, $S$ το σύνολο των φοιτητών που φορούν κασκόλ,
 $P$ το σύνολο των φοιτητών που φορούν πουλόβερ και $G$ το σύνολο των φοιτητών που φορούν γάντια.  Από τα δεδομένα της άσκησης έχουμε
 %
 \begin{gather*}
 |H| = 60,\quad |S| = 51,\quad |P| = 54,\\
 |H \cap S| = 30,\quad |H \cap P| = 26, \quad |S \cap P| = 21, \quad |H \cap S \cap P| = 12
 \end{gather*}
 %
 Ξέρουμε επίσης ότι όσοι δεν φορούν ούτε καπέλο ούτε κασκόλ φορούν γάντια.  Στο πρώτο ερώτημα της άσκησης μας ζητείται να βρούμε 
 τον αριθμό των φοιτητών που φορούν γάντια.  Ας υπολογίσουμε πρώτα τον αριθμό των φοιτητών που φορούν καπέλο ή κασκόλ. Ο
 αριθμός αυτός είναι $60+51-30= 81$. Επομένως $130-81 = 49$ φοιτητές δεν φορούν ούτε κασκόλ ούτε καπέλο. Αυτοί λοιπόν φορούν γάντια.
 
 Στο δεύτερο ερώτημα μας ζητείται να υπολογίσουμε πόσοι από τους φοιτητές που δεν φορούν πουλόβερ, φορούν καπέλο αλλά όχι κασκόλ,
 με άλλα λόγια τον αριθμό $|\overline{P} \cap H \cap \overline{S}|$. Όμως
 $|\overline{P} \cap H \cap \overline{S}| = |H \cap \overline{S}| - | H \cap \overline{S} \cap P|$ και $|H \cap \overline{S}| =
 |H| - |H \cap S| = 60 - 30 = 30$  ενώ $|H \cap P \cap \overline{S}| = |H \cap P | - |H \cap P \cap S| = 26-12 = 14$. Επομένως το πλήθος
 των φοιτητών που δεν φορούν πουλόβερ αλλά φορούν καπέλο και δεν φορούν κασκόλ είναι $30-14=16$.
 
 Στο τρίτο ερώτημα μας ζητείται να βρούμε τον αριθμό των φοιτητών που δεν φορούν ούτε καπέλο ούτε πουλόβερ ούτε κασκόλ. Ο αριθμός
 αυτός είναι προφανώς $130 - |Η \cup P \cup S|$. 
 Εύκολα βλέπει κανείς ότι $|H \cup S \cup P| = 100$, το οποίο σημαίνει ότι $130-100 = 30$ φοιτητές δεν φορούν ούτε καπέλο ούτε κασκόλ ούτε πουλόβερ.
\end{enumerate}
%
 %
\end{document}
