Éste es un problema para el que resulta fácil dar una respuesta informal y verdaderamente difícil dar una solución precisa. Es sorprendente el hecho de que paradojas de este tipo fueron una dificultad importante para establecer las bases rigurosas de la teoría de conjuntos.

    Podéis encontrar una explicación de la paradoja en la página de William T. Gowers en esta página, en inglés, en un estilo claro que no requiere conocimientos técnicos pero tal vez sí una cierta familiaridad con argumentos matemáticos usuales. Conseguir una explicación así en Internet para un problema de esta página es un lujo, ya que la comprensión de Gowers de las matemáticas es, en mi opinión, excepcional. Si alguien que lea esto está dispuesto a traducir la respuesta o parte de ella al español y me lo envía podremos incluirla aquí. En la página del mismo autor, hay varios ensayos cortos y observaciones informales sobre temas varios, la mayoría de los cuales no requieren conocimientos avanzados y probablemente gusten a quien haya venido hasta aquí buscando la sección de juegos matemáticos.

    Dicho esto, intentemos nuestra propia explicación del problema. En mi opinión, una buena respuesta a la paradoja es que la frase 'el número natural más pequeño que no puede describirse exactamente con quince palabras o menos' no sirve como descripción de ningún número. ¿Por qué no?. Como dice Vicente Lirola,

    Bueno, es que ¿qué número es 'el número natural más pequeño que no puede describirse exactamente con quince palabras o menos'?, esa frase no describe ningún número en concreto. Si le dices eso a alguien, no va a tener ni idea de cuál es el número del que está hablando, así que realmente, no vale como frase descriptora.

    La descripción no vale porque no tengo forma de saber a qué número se refiere.

    El problema con el razonamiento que se hace en la paradoja es, como en tantas otras, que el lenguaje usual es impreciso y contiene algunas trampas lógicas y posibilidades de construir frases sin sentido. En la frase anterior, el significado de la palabra 'describir' no está claro en absoluto. Si quisiéramos hacer riguroso el razonamiento tendríamos que empezar por especificar exactamente nuestro lenguaje y decidir qué frases describen qué números, de forma que no quede ambigüedad posible. Podríamos ser permisivos en esto, incluso inventar nuevas palabras, usar el idioma que queramos y la construcción que más nos guste, siempre que demos una forma de, dada una frase, decidir a qué número corresponde. Entonces podríamos, sin duda, encontrar el número más pequeño que no podemos describir con menos de quince palabras, donde 'describir' tiene el significado que acabamos de expresar precisamente. Pero entonces la frase 'el número natural más pequeño que no puede describirse exactamente con quince palabras o menos' no tiene por qué ser una descripción válida en el sentido anterior. Esta frase no tenía por qué estar incluida en nuestra definición precisa del principio y simplemente no corresponde a ningún número. De hecho, si la hubiésemos incluido, automáticamente no tendría el significado que le damos en el lenguaje usual y no describiría al número que esperamos.

    Otra forma de decirlo, en un correo de Mario Tomelin, es la siguiente:

    Creo que la falla del argumento está en la frase que identifica al número natural mas pequeño que puede describirse con quince palabras o menos, porque para encontrar ese número partimos del supuesto de que ya hemos agotado todas las combinaciones de quince palabras de todas las que componen el idioma español.

    Rodrigo Martín Martín observa que:

    Se trata de una variante de la paradoja de Richards que data de 1905. El culpable de esta paradoja (y de muchas otras como la paradoja de Grelling, que utiliza adjetivos en lugar de números, o la famosa paradoja de Russell) es el fenómeno de la autorreferencia, ya que estamos definiendo un objeto en términos de una clase que contiene como elemento al objeto que se está definiendo.

    ¿Dónde estaba aquí la autorreferencia? El término 'descripción' sólo tiene un significado preciso cuando sabemos lo que significa describir algo; pero entonces la frase clave de la paradoja es una nueva descripción, de forma que la palabra 'descripción' se está refiriendo también a la frase en sí.

    Otras paradojas de este tipo son también muy conocidas. La paradoja de Russell, por ejemplo, provocó la modificación de los axiomas de la teoría de conjuntos. La teoría de conjuntos que no la tiene en cuenta, curiosamente, se llama hoy en día 'teoría de conjuntos ingenua', o 'naive set theory' en inglés. Russell señaló que esta teoría permitía una paradoja si uno consideraba 'el conjunto de todos los conjuntos que no se contienen a sí mismos'. Este conjunto no puede estar dentro de sí mismo, porque entonces su definición dice lo contrario; pero si no es miembro de sí mismo, entonces debe serlo por definición, lo cual produce un absurdo.

    En la página mencionada antes hay otra versión que resulta más cómica: todos los números tienen que ser interesantes, porque si no fuese así el primer número que no fuese interesante sería, precisamente por eso, de lo más interesante. Otra forma famosa de enunciar la paradoja consiste en preguntar 'En mi pueblo el barbero afeita a todos los hombres que no se afeitan ellos mismos. ¿Quién afeita al barbero?'. Podéis notar la clara analogía entre la paradoja de Russell y la del barbero. Otra forma de confundir al lenguaje es tomar una hoja de papel y escribir en un lado: 'la frase escrita en la otra cara de esta hoja es verdadera'. Y en la cara de atrás: 'la frase escrita en la otra cara de esta hoja es falsa'. ¿Son entonces falsas estas frases? ¿son acaso verdaderas?.