Una tienda tiene 200 botas de tamaño A, 200 botas de tamaño B y 200 botas de tamaño C. En estos 600 botas, 300 son de el pie izquierdo y 300 son de el pie derecho. Sabiendo que utilizable pares de botas tienen el mismo tamaño y son de diferentes pies, demostrar que es posible encontrar al menos 100 pares de utilizable botas.
Respuestas
¿Demasiados anuncios?
Si cualquier categoría de tamaño $A,B,C$ tiene la igualdad de los números de la izquierda y la derecha botas, no se requieren $100$ pares de utilizable botas y hemos terminado.
De lo contrario, cada tamaño tendrá una mayoría de un pie. Desde $101\times 3>300$, estos no pueden ser el mismo pie, así que sin pérdida de generalidad podemos suponer que hay dos pies de las mayorías y uno a la izquierda-pie de la mayoría. Ahora el número de la derecha botas en el derecho-pie de la mayoría de los tamaños es en la mayoría de las $300$, así que hay al menos $100$ a la izquierda botas en los dos tamaños, los cuales pueden ser adaptados a la derecha botas, dándonos $100$ utilizable pares como sea necesario.
David
Puntos
496
Para dar una idea del problema, aquí es una prueba por casos. Llamar a $a_L$ el número de tamaño de $A$ pie izquierdo botas, $b_R$ el número de tamaño de $B$ pie derecho, botas, etc.
Primero nos tenga en cuenta que el número de pares de tipo $A$ está dado por la $\min\{a_L,a_R\}$. Ahora, tenemos $a_L + a_R = 200$, por lo tanto $a_R = 200-a_L$. Podemos usar esto para decir el número de pares de tamaño $A$ está dado por $\min\{a_L,200-a_L\}$.
Ahora, llamando $p$ el número de pares vemos claramente que el
$p = \min\{a_L,200-a_L\} + \min\{b_L,200-b_L\} + \min\{c_L,200-c_L\}$.
Suponga que el zurdo de zapatos es la menor cantidad en todos estos términos, obtenemos $p = a_L + b_L + c_L$, pero sabemos que hay 300 zurdo zapatos, por lo tanto $p=300$. Suponga que el zurdo de zapatos es la menor cantidad en dos de los términos de $p$. Sin pérdida de generalidad, supongamos que esto es cierto para el tamaño de la $A$$B$. Entonces tenemos que
$p = a_L + b_L + 200 - c_L = 300 - c_L + 200 - c_L = 500 - 2c_L$,
pero $c_L \leq 200$ por lo tanto, $p\geq 100$. Suponga que el zurdo de zapatos es la menor cantidad en uno de los términos de $p$. Sin pérdida de generalidad, supongamos que esto es cierto para el tamaño de la $A$. Entonces tenemos
$p = a_L + 400 - (b_L + c_L) = a_L + 400 - (300 - a_L) = 100 + 2a_L \geq 100$.
Por último, suponga que el zurdo de zapatos es la menor cantidad en ninguno de los términos de $p$. Entonces
$p = 600 - a_L - b_L - c_L = 300$.
martinhans
Puntos
131
(Alternativas de solución)
Deje $\alpha, \beta,\gamma \in \mathbb Z\leq 100 $
Número de botas se tabulan como sigue:
$$\begin{array}&& \hline \bf\text{Left}&\bf\text{Right}&\bf\text{Total}&\bf\text{Usable Pairs}\\ \hline \bf\text{Size A}&100+\alpha &100-\alpha &200&100-\alpha\\ \bf\text{Size B}&100-\beta &100+\beta &200 &100-\beta\\ \bf\text{Size C}&100+\gamma &100-\gamma &200 &100-\gamma\\ \hline \bf\text{Total}&300 &300 &600&300-(\alpha+\beta+\gamma)\\ \hline \end{array}$$
Para el total de la Izquierda y la Derecha botas para la igualdad de $300$, $\alpha-\beta+\gamma=0 \Rightarrow \beta=\alpha+\gamma$.
Número de espacio de los pares está dada por $$\begin{align} N=300-(\alpha+\beta+\gamma)&=300-2\beta\\ N_{\text{max}}=N\big|_{\beta=0}&=300\\ N_{\text{min}}=N\big|_{\beta=100}&=100\\ \end{align} $$
(Solución Original a continuación)
Considere el caso extremo en el que
- todos los 200 tamaño de Una botas son a la Izquierda (L), y
- más de 200 de tamaño B botas son a la Derecha (R),
es decir, todos los inutilizable.
Esto deja a 100 R y 100 L botas. Estos deben ser de tamaño C.
Por lo tanto, hay 100 pares de utilizable botas.
Daniel Xiang
Puntos
15
Hay tres categorías de tamaño de Una de zapatos, tamaño B, zapatos, y el tamaño de C zapatos. Vamos a poner 600 botas en estas tres categorías. Desde 300 son los zapatos del pie izquierdo, por el pigeon-hole principio, al menos una categoría contendrá 100 botas. Ahora añadimos en el 300 a la derecha botas.
Aquí es el tipo de ingenuo manera en que yo pensaba acerca de este problema. La categoría que contiene al menos 100 botas tiene entre 100 y 200 izquierda botas - llamar a esta categoría $c_1$. Ahora hay alrededor de 100 casos.
Si $c_1$ contiene de 200 a la izquierda arranca, entonces los 100 restantes están contenidas en la segunda dos categorías que cuando llenamos con la derecha botas producirá 100 pares de zapatos ya que ninguna de estas categorías tienen menos de 100 puntos por el derecho de las botas.
Si $c_1$ contiene 199 izquierda botas, luego el resto de la 101 se encuentra en el segundo dos categorías, y obtenemos 1 trabajando par de $c_1$. Si todos 101 están contenidas en una de las dos categorías restantes, luego de que la categoría de rendimiento 99 adicionales pares de trabajo después de ser llenado con la derecha botas. Si ninguna de las dos categorías restantes contienen todos 101 izquierda botas, entonces obtenemos un adicional de 101 pares de trabajo, ya que ambas categorías tienen al menos 100 resto de spots para el derecho de las botas.
Si $c_1$ contiene 198 izquierda botas, volvemos a repetir el argumento anterior.
Este tipo de argumento va a trabajar para $c_1$ contiene de 200 a 100 a la izquierda botas.
Probablemente hay una forma más elegante de probar esto, pero me parece que este primer vistazo tipo de razonamiento más intuitiva y todavía razonablemente rigurosa.
