¿Cómo utilizar el principio de encasillamiento generalizado para estar seguro de que al menos uno de los enteros elegidos es par?

Question

Q. ¿Cuántos enteros de $0$ a través de $60$ debe elegir para para estar seguro de obtener al menos uno que sea impar? al menos uno que sea par? uno que sea par?

Aquí está mi solución verbal "sin utilizar" el principio de encasillamiento.

A. La lista de enteros $0,1,2...,60$ tiene $31$ números enteros pares $30$ Enteros Impares. Así que para estar seguros de que al menos uno de los enteros elegidos es impar, debemos elegir $32$ enteros. Esto se debe a que puede ocurrir que primero $31$ enteros que elegimos resultan ser pares. Por un argumento similar, encontramos que si elegimos $31$ enteros de la lista, entonces estamos seguros de que al menos uno de ellos es par.

Ahora quiero escribir esta solución en términos de una función, palomas y casilleros.

Desgraciadamente, la lista de enteros dada contiene un total de $61$ enteros que es impar. Por lo tanto, no puedo aceptar que los casilleros sean $\{0,1\}, \{2,3\}, \{4,5\},...,\{58,59\},\{60\}.$ El problema es que el último elemento es un conjunto único. He intentado utilizar estos casilleros de la siguiente manera:

Dejemos que $X$ denotan el conjunto de palomas que se recogen y $Y=\{A_1=\{0,1\},A_2= \{2,3\},A_3= \{4,5\},...,A_{30}=\{58,59\},A_{31}=\{60\}\}$ denotan el conjunto de casilleros. Sea $f : X \to Y$ sea una función tal que $f(x)=A_i$ siempre que $x \in A_i.$

Para estar seguro de que al menos un entero es impar : Supongamos que hemos elegido $n$ número de palomas. Entonces hemos terminado cuando encontramos el menor valor de $n$ tal que $\lceil \frac n{31} \rceil \ge 2$ (Por el principio de encasillamiento generalizado). Obsérvese que $n=32$ encaja en el proyecto de ley. También $A_{31}$ no es el casillero que contiene al menos $2$ palomas desde el conjunto $\{60\}$ sólo tiene un elemento. Por lo tanto, uno de los otros casilleros debe funcionar y estamos seguros de haber encontrado al menos un entero impar.

Sin embargo, este argumento falla cuando queremos estar seguros de que al menos un entero es par.

¿Cómo debo pensar aquí sobre las palomas y los casilleros?

EDITAR: ¿Debo considerar diferentes casillas para el caso de escoger al menos un entero par? En concreto, sólo cambiaría $A_{30}=\{58,59\}$ a $A_{30}=\{58,59,60\}$ y descartar $A_{31}$ para este caso. Entonces el menor valor de $n$ tal que $\lceil \frac n{30} \rceil \ge 2$ es $n=31.$ Aquí incluso si $A_{30}$ resulta ser el casillero con al menos $2$ palomas estamos seguros de que una de las palomas está obligada a ser par ya que este palomar sólo tiene un número impar a saber $59$ en él.

Answer 1

En realidad, tu razonamiento inicial es un ejemplo perfecto de "razonamiento por encasillamiento": hay como máximo 31 agujeros "pares" para que entren las palomas, así que con 32 palomas seguro que obtienes un número impar.

¡Eso es!

Tu segundo método es mucho más complicado de lo que tiene que ser. Sí, puedes hacer que funcione haciendo los agujeros $\{ 0,1 \}$ , $\{2,3 \}$ etc., pero también utilizando $\{0,3 \}$ , $\{ 1,2 \}$ etc. De hecho, para conseguir tantos agujeros como números pares, se podría incluso utilizar $\{ 0,37,39 \}$ , $\{2, 13 \}$ , $\{ 4 \}$ , $\{ 6, 19,23,29,59 \}$ etc. En otras palabras, añadir los números Impares a los números pares, cuando lo único que cuenta es cuántos números pares hay, es completamente superfluo.

Ahora: Entiendo que has intentado configurarlo de forma que puedas intentar responder tanto a la pregunta sobre el impar como a la de los números pares a la vez... lo que parecía funcionar bien... hasta que llegaste a la $60$ por sí mismo' ... y ahora te metes en problemas: Usando $\{ 60 \}$ como agujero significa que puede contener exactamente una paloma "par", pero ahora no puede contener ninguna paloma "impar", por lo que no se puede utilizar para hacer el razonamiento relativo a los números Impares, y utilizando $\{ 58,59,60 \}$ significa que dos palomas "pares" pueden entrar en ese agujero, por lo que ahora no se puede utilizar para razonar sobre los números pares.

Así que realmente lo mejor es responder a la pregunta sobre los números pares por separado de la pregunta sobre los números Impares: con $31$ números pares que necesitas elegir $32$ palomas para conseguir una paloma impar, y con $30$ Números de impar que necesita $31$ palomas para conseguir una paloma uniforme.

Answer 2

Intentaré responder a la pregunta en el sentido en que usted la plantea.

Como ya se ha señalado, su primer argumento es en realidad lo que mucha gente (yo incluido) ya consideraría un argumento por el principio de encasillamiento. El segundo argumento añade mucha más estructura, a saber, la partición del conjunto $\{0,\ldots,60\}$ en $31$ subconjuntos (para demostrar que se puede elegir $31$ enteros pares pero no $32$ ) o $30$ subconjuntos (para demostrar que se puede elegir $30$ Impares enteros pero no $31$ ).

La estructura extra añade información a cualquier selección particular de números que no es realmente relevante para lo que se quiere demostrar; es decir, si ya se ha elegido $31$ enteros pares, la partición le indica no sólo que el $32$ n número se asignará a un casillero ya ocupado; una vez que elija realmente un $32$ número de la partición, la partición le dice específicamente que El número impar ya está en el casillero donde se intenta poner el nuevo número.

No veo nada particularmente equivocada con esto; Estoy seguro de que hay un montón de pruebas en las que construimos alguna estructura que hace un poco más que la cosa a demostrar, porque es una manera conveniente de obtener al menos lo que necesitábamos. Y usted puede tener buenas razones para querer una partición (por ejemplo, si el principio ha sido definido en términos de particiones).

Yo diría que la partición para " $32$ Los números deben incluir un número impar" tiene sólo algunas propiedades esenciales:

1. Consiste exactamente en $31$ subconjuntos.
2. Cada subconjunto contiene exactamente un número par.

Todo lo demás es arbitrario, así que puedes organizarlo como quieras. Una partición perfectamente buena es tener $30$ subconjuntos únicos que contienen un número par cada uno, y todo lo demás en el último subconjunto:

$$\{0\},\{2\},\{4\},\ldots,\{58\},\{60, 1,3,5,\ldots,59\}.$$

Así que ahora tenemos la información extra (innecesaria, pero inofensiva) de que si seleccionamos dos números para el mismo casillero, ambos están en el casillero que se asignó al número $60.$ Y esos números de doble ocupación son o bien dos números Impares (¡así que has elegido al menos uno!) o $60$ y un número impar.

Como no hay problema en poner $31$ números en un subconjunto de esta partición, estaría igualmente dispuesto a poner tres números en uno de los $30$ subconjuntos, a saber $A_{30}=\{58,59,60\}$ cuando se hace una partición para una prueba de que al menos un número debe ser par si se elige $31$ números.