Una máquina expendedora vende pasaje para viajar a $200$ ciudades distintas. Un día vendió $3800$ pasajes.
a) Determinar si siempre es verdadero que hay por lo menos $6$ ciudades para las que se vendieron el mismo número de pasajes.
b) Determinar si siempre es verdadero que hay por lo menos $7$ ciudades para las que se vendieron el mismo número de pasajes.
caso a)
Primero observamos, que si logramos distribuir los 3800 pasajes en grupos de 5 o menos destinos, diremos que no siempre es posible (a), y en caso de que esta distribución resulte imposible, diremos que siempre es verdadero.
Al distribuir los 200 destinos en grupos de 5, nos quedan 40 grupos. G1, G2, G3, ... G39, G40
Les daremos a estos grupos la menor cantidad de viajes posibles.
Los 5 destinos de G1 tendran o viajes.
Los 5 destinos de G2 tendran 1 viajes.
Los 5 destinos de G3 tendran 2 viajes.
Los 5 destinos de G4 tendran 3 viajes.
.
.
.
Los 5 destinos de G40 tendran 39 viajes.
Para calcular la cantidad de pasajes totales, distribuidos de esta manera aremos el triangular de 39 por 5 (ya que hay 5 destinos por cada cantidad de viajes).
((39 x 40):2)5
Esto no dará 3900 pasajes por lo cual siempre se dará que haya 6 ciudades para las que se vendieron la misma cantidad de pasajes. Debido a que organizando los grupos lo mas grandes posibles, con la menor cantidad de pasajes, nos sobraran 100 pasajes. Que seria lo mínimo que podemos hacer que sobre sin que se repitan 6 destinos con la misma cantidad de pasajes.
Caso b)
Plantearemos lo mismo que en el punto a pero con grupos de 6.
Distribuiremos los grupos igual que en el punto anterior pero, con hasta 6 destinos con la misma cantidad de pasajes. Por lo cual nos quedan 33 grupos de 6 destinos y dos destinos que nos sobran (33 x 6 +2 = 200).
A los grupos les daremos la menor cantidad de pasajes posibles (para no pasarnos).
Los 6 destinos de G1 tendran o viajes.
Los 6 destinos de G2 tendran 1 viajes.
Los 6 destinos de G3 tendran 2 viajes.
.
.
.
Los 6 destinos de G33 tendrán 32 viajes.
Para calcular la cantidad de viajes aremos el triangular de 32 por 6 ( ((32 x 33): 2) 6= 3168 )
Por lo cual nos sobran 632 destinos, que los podemos distribuir fácilmente en dos destinos de 316 viajes, o de cualquier otra manera que no use números del 0 al 32 porque los usamos previamente en los 33 grupos, y así se repetirían mas de 6 veces
Tenemos un ejemplo en el que no se cumple por lo cual diremos que b) es falso.
Como dato curioso, el problema puede generalizarse (con un método similar) a: Hay $n$ ciudades y se venden $k$ pasajes, entonces, la cantidad de ciudades con la misma cantidad de pasajes es, al menos,
$$\left\lceil\frac{\frac{(n-r-1)(n-r)}{2}+r(n-r)}{k}\right\rceil$$
donde $r$ es el resto de dividir $n$ por $k$
Veamos que por Principio del Palomar (https://omaforos.com.ar/viewtopic.php?t=1273) el caso menos favorable seria que para las primeras $5$ ciudades se vendan $0$ pasajes, para la segundas $5$ se venda $1$ pasaje y así siguiendo análogamente hasta las ultimas $5$ ciudades se vendan $39$ pasajes. Luego en total se vendieron $5.\sum_{i=0}^{39}i= 5.\frac{39.40}{2} = 3900$. Como $3900>3800$ hay alguna cuidad para la que se vendió un pasaje menos del que le asignamos, luego siempre es verdadero que haya $6$ con el mismo numero de pasajes.
No siempre es verdadero análogamente al caso anterior, podemos afirmar que para las primeras $6$ se vendieron $0$ pasajes, para las segundas $6$ se vendió $1$ pasaje, ..., para los trigésimo terceros $6$ se vendieron $32$ pasajes y para las ultimas $2$ se vendieron $\frac{3800-6\sum_{i=0}^{32}i}{2}=\frac{3800-6.\frac{32.33}{2}}{2}=\frac{3800-3168}{2}=316$ pasajes, dado este ejemplo justifico que no siempre es verdadero