4: Bijecciones y Pruebas Combinatorias

Última actualización
Guardar como PDF

Page ID: 114500

Joy Morris
University of Lethbridge

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Tal vez recuerde que en Matemáticas 2000 aprendió que dos conjuntos tienen la misma cardinalidad si hay una bijección entre ellos. (Una bijección es una función uno a uno, onto.) Esto nos lleva a otro método importante para contar un conjunto: se nos ocurre una biyección entre los elementos del conjunto desconocido, y los elementos de un conjunto que sí sabemos contar. Esta idea está muy estrechamente relacionada con el concepto de una prueba combinatoria, que exploraremos en la segunda mitad de este capítulo.

Aparte: Aunque no vamos a explorar los conceptos de\(P\) y en\(NP\) absoluto en este curso, aquellos de ustedes que han estudiado estas ideas en cursos de informática pueden estar interesados en aprender que la mayoría de las técnicas utilizadas para demostrar que un problema particular está en\(P\) o en\(NP\) están relacionados con las técnicas discutidas en este capítulo. Por lo general,\(X\) se demuestra que un problema está en\(NP\) (por ejemplo) comenzando con un problema en el\(Y\) que ya se sabe que está en\(NP\). Entonces el científico utiliza algunas ideas inteligentes para demostrar que el problema\(Y\) puede estar relacionado con el problema\(X\) de tal manera que si el problema\(X\) pudiera resolverse en tiempo polinomial, esa solución produciría una solución al problema\(Y\), aún en tiempo polinómico. De ahí el hecho de que\(Y\) está en\(NP\) fuerzas\(X\) para estar en\(NP\) también. Las mismas ideas a veces pueden relacionar el número de soluciones de problema\(X\) con el número de soluciones de problema\(Y\).

4.1: Conteo vía Bijecciones
Puede ser difícil averiguar cómo contar el número de resultados para un problema en particular. A veces será posible encontrar un problema diferente, y demostrar que los dos problemas tienen el mismo número de resultados. Si podemos averiguar cómo contar los resultados para el segundo problema, ¡entonces también hemos resuelto el primer problema! Esto puede parecer descaradamente obvio de manera intuitiva, pero esta técnica puede proporcionar soluciones simples a problemas que a primera vista parecen muy difíciles.
4.2: Pruebas combinatorias
Cuando miramos las bijecciones, estábamos usando esta idea para encontrar una manera más fácil de contar algo que parecía difícil. Pero si realmente podemos encontrar una fórmula que cuente correctamente la respuesta a nuestro problema de alguna manera difícil, y también podemos encontrar una fórmula diferente que cuente correctamente la respuesta al mismo problema mirándolo de una manera diferente, entonces sabemos que los valores de las dos fórmulas deben ser iguales, a pesar de sus diferentes apperances. Esta es la idea de la prueba combinatoria.
4.3: Resumen
Esta página contiene el resumen de los temas tratados en el Capítulo 4.