%% -*- mode: latex; coding: utf-8; -*-

%% Comando para compilar: lualatex ej04b.tex
%% Debes compilar el archivo dos veces para obtener las referencias

\documentclass[11pt,letterpaper]{article}


\usepackage{polyglossia}
\usepackage[margin=1in]{geometry}
\usepackage{algpseudocode}
\usepackage{mathtools,amsthm}
\newtheorem{theorem}{Teorema}
\newtheorem{corollary}[theorem]{Corolario}
\newtheorem{lemma}[theorem]{Lema}
\theoremstyle{definition}
\newtheorem{definition}{Definición}[section]
\usepackage{enumitem,amssymb}
\setlist[itemize]{noitemsep, topsep=0pt}
\setlist[enumerate]{noitemsep, topsep=0pt}
\setlist[description]{noitemsep, topsep=0pt}
\usepackage{tabularx,booktabs}
\usepackage{siunitx}
\usepackage{titling}
\predate{}\postdate{}
\preauthor{}\postauthor{}

\setdefaultlanguage{spanish}
\setlength{\droptitle}{-11.5ex}
\setlength{\parindent}{0pt}


\title{%
  Matemáticas discretas 2024--1 \\
  Ejemplo 4b: Redacción de demostraciones}
\date{}
\author{}


\begin{document}

\maketitle
\bigskip

En este documento se presentan ejemplos de redacción para las
demostraciones discutidas en clases.  Los métodos de demostración
utilizados son: prueba directa de implicación, prueba por
contraposición, prueba con cadenas de ``sii'', prueba por casos y
prueba por contradicción.

\begin{theorem}
  Si $0 \leq x \leq 2$, entonces $-x^3 + 4x + 1 > 0$.
\end{theorem}
\begin{proof}
  Supongamos que $0 \leq x \leq 2$.  Entonces $x$, $2-x$ y $2+x$ no
  son negativas.  Por lo tanto, el producto de estos términos tampoco
  es negativo.  Sumar $1$ a este producto resulta en un número
  positivo, entonces \[x(2-x)(2+x)+1 > 0.\] Multiplicando el lado
  izquierdo de la desigualdad se demuestra que \[-x^3+4x+1>0.\]
\end{proof}

\begin{theorem}
  Si $r$ es irracional, entonces $\sqrt{r}$ también es irracional.
\end{theorem}
\begin{proof}
  Demostramos la contrapositiva: si $\sqrt{r}$ es racional, entonces
  $r$ es racional.  Supongamos que $\sqrt{r}$ es racional.  Entonces
  existen enteros $a$ y $b\not=0$ tales que \[\sqrt{r}=\frac{a}{b}.\]
  Elevando al cuadrado en ambos lados de la igualdad resulta en
  que \[r=\frac{a^2}{b^2}.\] Ya que $a^2$ y $b^2$ son enteros, $r$ es
  racional.
\end{proof}

\begin{theorem}
  La desviación estándar de una secuencia de valores es cero, si y
  solo si, todos los valores son iguales a la media.
\end{theorem}
\begin{proof}
  Construimos una cadena de implicaciones ``sii'', comenzando con la
  afirmación que la desviación estándar es cero.  Sean $x_1,\dots,x_n$
  la secuencia de valores y $\mu$ su media, por definición de
  desviación estándar tenemos
  que, \[\sqrt{\frac{(x_1-\mu)^2+(x_2-\mu)^2+\dots+(x_n-\mu)^2}{n}}=0.\]
  Ya que cero es el único número cuya raíz cuadrada es cero, la
  anterior igualdad se cumple
  sii \[(x_1-\mu)^2+(x_2-\mu)^2+\dots+(x_n-\mu)^2=0.\] Los cuadrados
  de números reales nunca son negativos, entonces cada término del
  lado izquierdo de la ecuación anterior no es negativo.  Esto
  significa que la ecuación se cumple sii cada término $(x_i-\mu)^2$
  es cero.  Cada uno de estos términos es cero sii $x_i=\mu$, por lo
  tanto esto se cumple sii cada $x_i$ es igual a la media.
\end{proof}

\begin{theorem}
  Cada colección de seis personas incluye una clica de tres personas o
  un grupo de tres desconocidos.
\end{theorem}
\begin{proof}
  La demostración es por análisis de casos.  Sea $x$ una de las seis
  personas, todos los escenarios se contemplan con dos casos:
  \begin{enumerate}
  \item\label{casos:1} Entre las otras cinco personas además de $x$
    hay al menos tres que conocen a $x$.
  \item\label{casos:2} Entre las otras cinco personas además de $x$
    hay al menos tres que no conocen a $x$.
  \end{enumerate}
  \begin{description}
    \item[{Caso 1:}] Suponemos que al menos tres personas conocen a
      $x$ y consideramos dos subcasos:
      \begin{description}
      \item[{Caso 1.1:}] Ninguna pareja de esas tres personas se
        conoce.  Entonces estas tres personas conforman un grupo de
        tres desconocidos.
      \item[{Caso 1.2:}] Alguna pareja de esas tres personas se
        conoce.  Entonces esa pareja, junto con $x$, conforman una
        clica de tres personas.
      \end{description}
      Esto implica que el teorema se cumple en el caso~\ref{casos:1}.
    \item[{Caso 2:}] Suponemos que al menos tres personas no conocen a
      $x$ y también consideramos dos subcasos:
      \begin{description}
      \item[{Caso 2.1:}] Todas las parejas de estas tres personas se
        conoce.  Entonces estas tres personas conforman una clica de
        tres.
      \item[{Caso 2.2:}] Alguna pareja de esas tres personas no se
        conoce.  Entonces esa pareja, junto con $x$, conforman un
        grupo de tres desconocidos.
      \end{description}
      Esto implica que el teorema se cumple en el caso~\ref{casos:2}.
  \end{description}
  Ya que el teorema se cumple en los dos casos y estos contemplan
  todos los posibles escenarios, el teorema se cumple en general.
\end{proof}

El siguiente lema es utilizado en el teorema~\ref{teorema:contra}.

\begin{lemma}\label{lema:contra}
  Si $n^2$ es par, entonces $n$ es par.
\end{lemma}
\begin{proof}
  Demostramos la contrapositiva: si $n$ es impar, entonces $n^2$ es
  impar.  Supongamos que $n$ es impar.  Por lo tanto existe un entero
  $k$ tal que $n=2k+1$.  Elevando ambos lados de la igualdad al
  cuadrado tenemos que \[n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1.\] Ya que
  $2k^2+2k$ es un entero, $n^2$ es impar.
\end{proof}

\begin{theorem}\label{teorema:contra}
  $\sqrt{2}$ es irracional.
\end{theorem}
\begin{proof}
  Usamos demostración por contradicción.  Supongamos que la afirmación
  es falsa y $\sqrt{2}$ es racional.  Entonces existen enteros $a$ y
  $b\not=0$ tales que $\sqrt{2}=a/b$.  Suponemos sin pérdida de
  generalidad que esta es una fracción irreducible.  Elevando ambos
  lados de la igualdad al cuadrado resulta en
  que \[2=\frac{a^2}{b^2}.\] Al multiplicar ambos lados de la ecuación
  por $b^2$ tenemos que \[2b^2=a^2.\] Por el lema~\ref{lema:contra}
  tenemos que $a$ es par.  Por lo tanto $a^2$ es múltiplo de $4$ y
  $d^2$ es un múltiplo de $2$.  Por el lema~\ref{lema:contra} tenemos
  que $d$ también es múltiplo de $2$.  Con esto hemos concluido que
  tanto $a$ como $b$ tienen a $2$ como factor primo en común, lo que
  contradice el supuesto que $a/b$ es una fracción irreducible.  Por
  lo tanto, $\sqrt{2}$ debe ser irracional.
\end{proof}




\end{document}
