
matemáticas son hermoso y, a veces, matemáticas se convierte en aún más hermosa con la ayuda de un poco de informática. Mi prueba favorita de todos los tiempos combina los dos de tal manera.
objetivo: demostrar que la cardinalidad del conjunto de números racionales positivos es igual a la del conjunto de números naturales.
este es un viejo problema que se remonta al Cantor con muchas pruebas:
- la prueba tradicional utiliza un argumento diagonal: visión geométrica que establece el numerador y el denominador de un número racional a lo largo de x e y ejes de un avión. La prueba es intuitivo pero difíciles de formalizar.
- hay una prueba corta pero densa que utiliza una asignación de producto cartesiano y otro teorema. Personalmente, no encuentro simplicidad y belleza al referirse a las cosas complejas.
- hay una prueba generativa usando una amplitud-primera transversal de un árbol de clavo-Wilf (a.k.a, árbol de H debido a su forma). Ahora estamos recibiendo ayuda de la informática pero no de una manera que ayuda a la simplicidad.
podemos hacer mucho mejor.
pruebas:
dado un número racional p/q, escribo como el hexadecimal número pAq. QED
ejemplos:
- 0/1 → 0A1 (161 en decimal)
- ¾ → 3A4 (932 en decimal)
- 12/5 → 12A5 (4773 en decimal)
código (porque podemos):
def to_natural (p, q) "#{p} A #{q}" final
es trivial para ampliar la generación todos racionales , no sólo el positivo unos, todo el tiempo que requerimos p/q para estar en forma canónica:
def to_natural (p, q) "#{p < 0? ' A': ''} #{p.abs}A#{q} "end
para mí, esta prueba de CS y se siente mucho más simple y más accesible que cualquiera de las pruebas de matemáticas-y estándar. Es generativa, reducible a una línea de código y no requiere conocimientos de cualquier conceptos avanzados más allá de los sistemas de numeración que no son base 10, una extensión de base aritmética posicional 10 recta, intuitivo.
Nota: no necesitamos usar hexadecimal. La primera vez que escuché esta prueba se hizo en base 11 pero creo que usando un sistema inusual de la base no hace la prueba mejor.
Comments
0 comments
Twitter
RSS