En algunas casillas de un tablero cuadriculado de $2018 \times 2018$ se colocaron fichas rojas y azules (no más de una ficha por casilla). Primero Pinocho retira del tablero todas las fichas rojas que tengan alguna ficha azul en su misma columna. A continuación retira del tablero todas las fichas azules que tengan alguna ficha roja en su misma fila.
Pinocho dice que luego de realizar este proceso quedaron en el tablero más de $1009^2$ fichas rojas y más de $1009^2$ fichas azules. Demostrar que a Pinocho le crecerá la nariz.
ACLARACIÓN: A Pinocho le crece la nariz cada vez que miente.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Es claro que por la forma de eliminar fichas no es posible que al final quede una fila o columna con al menos una ficha de cada color entonces en cada fila o columna quedan fichas del mismo color. Supongamos que Pinocho no miente. Es claro que podemos permutar las filas y columnas del tablero y cumplen las mismas condiciones. Entonces permutamos las filas tal que dejamos a todas las fichas rojas hacia la izquierda y todas las azules hacia la derecha y luego permutamos las columnas y dejamos a las fichas rojas arriba de todas las azules. Entonces tenemos que podemos dividir el tablero con 2 rectas de tablero (una horizontal y una vertical) tal que queden 4 rectángulos donde el que esta en la superior izquierda estan todos los rojos y en la inferior derecha todos los azules. Sea R y A la cantidad de fichas rojas y azules respectivamente y sean a,b y m,n los lados de los rectángulos en los cuales las fichas rojas y azules están dentro
respectivamente. Sea x=1009, entonces $a+b+n+m=2x+2x=4x$ (dado que a+m y b+n son los lados del tablero)
Ahora como Pinocho no miente entonces $x^2< R \leq ab$ y como $4ab\leq (a+b)^2$ entonces $4x^2<(a+b)^2$ entonces $2x<a+b$ análogamente llegamos que $2x<m+n$ sumando estas 2 cosas llegamos a una contradicción con lo anterior.
Por tanto Pinocho miente.
Llamamos:
$r$ a la cantidad de fichas rojas.
$a$ a la cantidad de fichas azules.
$C_r$ a la cantidad de columnas que tienen al menos una ficha roja.
$C_a$ a la cantidad de columnas que tienen al menos una ficha azul.
$F_r$ a la cantidad de filas que tienen al menos una ficha roja.
$F_a$ a la cantidad de filas que tienen al menos una ficha azul.
Luego de realizar el proceso no quedo ninguna fila ni ninguna columna con 2 fichas de diferente color, por lo tanto
$C_r+C_a\leq 2018$ (1)
$F_r+F_a\leq 2018$ (2)
Por palomar $\left \lceil \frac{r}{C_r} \right \rceil \leq F_r$ y $\left \lceil \frac{a}{C_a} \right \rceil \leq F_a$
Pasando terminos en (1) conseguimos $C_a\leq 2018-C_r$ (3)
Con (2) y (4) conseguimos $\left \lceil \frac{r}{C_r} \right \rceil + \left \lceil \frac{a}{2018-C_r} \right \rceil \leq F_r+F_a\leq 2018$ (5)
$\frac{r}{C_r}+\frac{a}{2018-C_r} \leq \left \lceil \frac{r}{C_r} \right \rceil + \left \lceil \frac{a}{2018-C_r} \right \rceil $ (6) donde la igualdad es valida cuando las dos divisiones dan soluciones enteras.
De (5) y (6) surge $\frac{r}{C_r}+\frac{a}{2018-C_r} \leq F_r+F_a\leq 2018$
Ahora vamos a buscar el menor valor posible para $\frac{r}{C_r}+\frac{a}{2018-C_r}$ para eso vamos a tomar el menor valor para $r$ y $a$ el cual es $1009^2+1=1018082$
Si queremos que $\frac{1018082\times 2018}{2018C_r-C_r^2}$ tenga el menor valor posible necesitamos que $2018C_r-C_r^2$ tenga el mayor valor posible. $2018C_r-C_r^2$ es una parábola descendente por lo que su mayor valor va a ser cuando $C_r=X_v$ donde $X_v$ es la coordenada $X$ del vertice.
$X_v=\frac{-b}{2a}=\frac{-2018}{2\times-1}=1009$
Por lo tanto $2018C_r-C_r^2$ tiene su mayor valor cuando $C_r=1009$, lo que significa que el menor valor de $\frac{r}{C_r}+\frac{a}{2018-C_r}$ es $\frac{1018082\times 2018}{2018\times 1009-1009^2}>2018$, lo que produce que
Luego de realizar las operaciones, llamamos $n$ a la cantidad de filas donde aparece al menos una ficha roja y llamamos $m$ a la cantidad de columnas donde aparece al menos una ficha azul. Notemos que la cantidad máxima de fichas rojas que pueden quedar es: $n*(2018-m)$, y la cantidad máxima de fichas azules es:
$m*(2018-n)$.
Supongamos que: $n*(2018-m)>$$1009^2$.
Despejando obtenemos que: $m<\frac{-1009^2}{n}+2018$
Pero también queremos que $m*(2018-n)>$ $1009^2$.
Reemplazamos $m$ y obtenemos:
$(2018-\frac{1009^2}{n})*(2018-n)>$$1009^2$
Despejando obtenemos la siguiente expresión:
$(n-1009)^2$$<0$
El cual es absurdo, dado que ningún cuadrado perfecto es negativo. Con esto justificamos que a pinocho le crecerá la nariz.
Lo primero que hacemos es notar que al final del proceso ninguna ficha roja comparte columna con alguna ficha azul, lo mismo ocurre en las filas. También vemos que es indistinta la posición de una columna de izquierda a derecha, lo mismo ocurre en las filas.
Sean $A_c,A_f$ la cantidad de columnas y filas, respectivamente, que contienen fichas azules luego del proceso. El mismo tipo de notación utilizaremos para las fichas rojas. Como no importa la posición de las columnas y las filas podemos acomodarlas convenientemente para que todas las fichas azules se encuentren contenidas dentro de un tablero rectangular de $A_c×A_f$ (no necesariamente lo cubren por completo pero son a lo sumo eso), de la misma manera trabajamos con las fichas rojas.
Por la primera observación que hicimos resulta que $A_c+R_c≤2018$ y $A_f+R_f≤2018$
Multiplicando ambas resulta en $A_c×A_f+R_c×R_f+A_c×R_f+A_f×R_c≤2018^2$
Pero Pinocho nos dice que $A_c×A_f>1009^2 y R_c×R_f>1009^2$
Reemplazando tenemos que $A_c×R_f+A_f×R_c<2×1009^2$
Sumando ambas de las desigualdades que nos da Pinocho resulta $A_c×A_f+R_c×R_f>2×1009^2$
Luego $A_c×R_f+A_f×R_c<A_c×A_f+R_c×R_f$
Factoreando: $0<(A_c−R_c)(A_f−R_f)$
Esto nos dice que ambos factores son positivos o negativos. En el primer caso resulta que $R_c$ y $R_f$ son ambos menores que $1009$ y por lo tanto Pinocho mintió. En el segundo pasa lo mismo con las fichas azules.
Conclusión: Pinocho es un mitómano