Muéstrame algunos problemas de encasillamiento

Question

Me estoy preparando para un examen de combinatoria. Una parte del mismo se centrará en el principio de encasillamiento. Por lo tanto, necesito algunos problemas difíciles o muy difíciles en el tema para resolver. Os agradecería que me enviarais enlaces \books\or sólo un problema de soledad.

Answer 1

---

Dividiré mi respuesta en dos partes: recursos de Internet y recursos de este mismo sitio.

---

Algunos recursos en Internet

Este breve documento contiene un montón de problemas relacionados con el principio de encasillamiento, tanto fáciles como difíciles, y tanto con solución como sin ella.

Esta página web contiene también una serie de problemas de encasillamiento, desde los básicos hasta los muy complejos, con todas las soluciones.

Echa un vistazo también a estas divertidas aplicaciones del principio de encasillamiento

---

Algunos problemas de este sitio

En este sitio se pueden encontrar muchos problemas interesantes que se resuelven con el principio del encasillamiento.

Números

101 enteros positivos colocados en un círculo

Se colocan en un círculo 101 enteros positivos cuya suma es 300. Demostrar que es posible elegir algunos números consecutivos de estos números cuya suma es igual a 200.

Escoge 100 números del 1 al 200 (uno menos que el 16) - ¡prueba que uno es divisible por otro!

Demuestra que si se eligen 100 números de entre los 200 primeros números naturales y se incluye un número menor que 16, entonces uno de ellos es divisible por otro.

De 52 enteros cualesquiera, se pueden encontrar dos cuya diferencia de cuadrados sea divisible por 100

Demuestra que para 52 enteros cualesquiera siempre se pueden encontrar dos tales que la diferencia de sus cuadrados sea divisible por 100.

Dados n números, demuestra que la diferencia de al menos un par de estos números es divisible por n-1

Suponga que tiene una lista de n números, n2. Sea A el conjunto de diferencias de pares de estos n números. Demuestra o refuta que al menos un elemento de A debe ser divisible por n1.

Una característica interesante de cualquier $1000$ diferentes números elegidos entre $\{1, 2, \dots,1997\}$

Suponga que elige 1000 números diferentes del grupo {1,2, ,1997}. Demuestra que dentro de los 1000 números elegidos, hay una pareja cuya suma es 1998.

Personas y objetos

Matemáticas discretas - Muestras aleatorias de helado

Supongamos que hay 5 tipos diferentes de helado que te gustan. ¿Cuántas muestras aleatorias de helado debe comer para garantizar que ha tomado al menos 7 muestras de un tipo?

Una pregunta relacionada con el principio de encasillamiento

En una habitación hay 10 personas, y ninguna de ellas tiene más de 60 años, y cada una tiene al menos 1 año de edad. Demuestra que siempre se pueden encontrar dos grupos de personas (sin ninguna persona en común) tales que la suma de las edades es la misma en ambos grupos.

combinatoria: El principio del encasillamiento

Supongamos que en cada grupo de 9 personas hay 3 de la misma altura. Demuestra que en un grupo de 25 personas hay 7 de la misma altura.

Pregunta sobre el principio de encasillamiento

Hay una fila de 35 sillas. Encuentra el número mínimo de sillas que deben estar ocupadas para que haya un conjunto consecutivo de 4 o más sillas ocupadas.

Otra pregunta del principio de encasillamiento

Un curso tiene siete temas optativos, y los estudiantes deben completar exactamente tres de ellos para aprobar el curso. Si 200 estudiantes aprobaron el curso, demuestre que al menos 6 de ellos deben haber completado los mismos temas optativos entre sí.

Geometría

Principio de encasillamiento para un triángulo

Consideremos un triángulo equilátero de área total 1. Supongamos que se eligen 7 puntos en su interior. Demuestre que unos 3 puntos forman un triángulo de área $\leq\frac 14$ .

Disposición de $100$ puntos en el interior $13\times18$ rectángulo

Demuestra que no puedes disponer 100 puntos dentro de un rectángulo de 13×18 de forma que la distancia entre dos puntos cualesquiera sea al menos 2.

Pregunta sobre el principio de la paloma: Nueve puntos en un diamante

Se da un diamante (un paralelogramo de lados iguales) cuyos lados miden 2 cm. Los ángulos agudos tienen 60 grados. Si hay nueve puntos dentro del diamante, demostrar que debe haber dos de ellos para que la distancia entre ellos es a lo sumo 1 cm.

Principio de encasillamiento y un decágono

Las cifras ${0,1,2,.....9}$ se asignan aleatoriamente a los vértices ${x_0,x_1,...x_9}$ de un decágono. Demuestra que hay 3 vértices consecutivos cuya suma es al menos 14.

Pregunta sobre el principio de los polígonos y los casilleros

Se eligen siete vértices en cada uno de los dos congruentes regulares de 16 gonos. Demostrar que estos polígonos pueden colocarse uno encima de otro de forma que al menos cuatro vértices elegidos de un polígono coincidan con alguno de los vértices elegidos del otro.

El menor número de puntos del plano que garantiza la existencia de un ángulo pequeño

¿Cuál es el menor número n, que en cualquier disposición de n puntos en el plano, hay tres de ellos haciendo un ángulo de a lo sumo 18?

Answer 2

Hay muchos problemas de este tipo (¡con soluciones!) en el Archivos Math.SE . Puede probar con otras palabras clave en el cuadro de búsqueda de la parte superior derecha de la página para buscar más problemas.

Answer 3

El famoso Pruebas del libro contiene un capítulo sobre El encasillamiento y la doble contabilidad . En él se pueden encontrar varias aplicaciones simpáticas del principio de encasillamiento.

Answer 4

Este apareció en una búsqueda rutinaria en Google de la frase "pidgeonhole principle exercise" y parece ser problemas de entrenamiento para el equipo de la olimpiada de Nueva Zelanda. Contiene numerosos problemas y tiene algunas soluciones en la parte posterior.

Answer 5

SI $\alpha>0$ es irracional, entonces las partes fraccionarias de $n\alpha$ forma un subconjunto denso de $[0,1]$ .

Dado un número entero positivo $n>0$ , los números de Fibonacci módulo $n$ es periódica.

Estos son muy famosos de la teoría de números. Hay pruebas de ellas utilizando el principio de encasillamiento.