¿Cuál es el número mínimo de pares ordenados de números no negativos que debe elegirse para que haya dos pares (a,b) y (c,d) en el conjunto elegido conjunto elegido tal que a = c mod 3 y b = d mod 5.
Esto se preguntó en GATE 2005. Aquí no han mencionado ninguna restricción en los pares ordenados. No tengo ni idea de cómo enfocar este problema. Cualquier ayuda será muy apreciada.
Respuestas
¿Demasiados anuncios?
Oli
Puntos
89
Demostramos que $16$ pares son suficientes, pero $15$ pares no tiene por qué serlo.
Si tenemos $16$ o más pares, hay al menos $6$ pares cuyas primeras entradas son congruentes entre sí módulo $3$ . Esto se debe a que la primera entrada de cualquier par es congruente con una de $0$ , $1$ o $2$ modulo $3$ . Si hubiera $\le 5$ de cada tipo, entonces el número de pares sería $\le (3)(5)=15$ .
Y como hay al menos $6$ tales pares, $2$ de ellos al menos tienen sus segundas entradas congruentes módulo $5$ .
Para demostrar que $15$ no son suficientes, considere los pares $(0,0)$ , $(0,1)$ , $(0,2)$ , $(0,3)$ , $(0,4)$ y $(1,0)$ , $(1,1)$ , $(1,2)$ , $(1,3)$ , $(1,4)$ y $(2,0)$ , $(2,1)$ , $(2,2)$ , $(2,3)$ , $(2,4)$ .
David HAust
Puntos
2696
Esto es una aplicación del principio de encasillamiento. Cada par $(x,y)$ representa un par de clases de congruencia en $\def\Z{\Bbb Z}\Z/3\Z \times\Z/5\Z$ y la pregunta es cuántos pares deben elegirse para garantizar que un mismo par de clases de congruencia se alcance dos veces. Hay $\#(\Z/3\Z \times\Z/5\Z)=3\times5=15$ diferentes de tales pares de clases de congruencia, y el principio de encasillamiento dice que de cualquier manera $16$ pares $(x,y)$ se eligen, dos de ellos están obligados a ocupar el mismo par de clases de congruencia. Y por otro lado con sólo $15$ pares $(x,y)$ Es evidente que se podría ocupar cada uno de los $15$ pares de clases de congruencia exactamente una vez.
