martes, 10 de enero de 2012

Problema del Día: Objetos de tres tipos

Hola a todos. Espero que estén empezando el año nuevo bien y que les haya gustado la dinámica de la competencia de invierno. Este es el primer problema del blog de combi. Recuerden que comentar en estos problemas cuenta como parte de su calificación.

Se tienen $2n$ objetos de tipo $A$, $2n$ de tipo $B$ y $2n$ de tipo $C$. Se quieren repartir entre dos personas (de modo que a cada quien le toquen $3n$). Muestra que esto se puede hacer de $3n^2+3n+1$ formas.

14 comentarios:

Marco dijo...

Sean X,Y las personas. Veremos de cuántas maneras podemos darle 3n objetos a X, y como los objetos que van para Y quedan ya determinados, ésta será la respuesta.
Supongamos que escogemos n o más objetos del tipo A, y sea k un entero entre n y 2n (inclusive) que representa la cantidad de objetos que hace falta escoger. Entonces tenemos que escoger k objetos de entre los tipos B y C, lo cual claramente se puede hacer de k+1 formas, a saber, (k,0),(k-1,1),...,(0,k), dónde (a,b) representa escoger a objetos tipo A y b objetos tipo B. Entonces en este caso tenemos (n+1)+(n+2)+...+(2n+1) = (n+1)(3n+2)/2 formas... (esto evaluando k en cada valor de n a 2n... notemos que esto fue posible gracias a que los conjuntos de objetos tipo B y C contenían suficientes objetos)
Ahora, si escogemos una cantidad menor o igual a n-1 de tipo A, sea k un entero entre 1 y n (inclusive), de manera que tenemos que escoger 2n + k objetos de entre los tipos B y C (de los que, recordemos, podemos tomar a lo más 2n objetos de alguno de ellos).
Tomando (2n,k),(2n-1,k+1),...,(n+1+k,n-1),(n+k,n),...,(n+1,n+k-1),(n,n+k) notemos que la cantidad de parejas desde (2n,k) hasta(n+k+1,n-1) debe ser multiplicada por 2, para contar también los casos (k,2n),...(n-1,n+k+1). Pero la cantidad de parejas desde (n+k,n) hasta (n,n+k) no porque, haciendo una biyección entre (a,b) y (b,a) a la primer pareja de esta lista le corresponde la última, a la segunda la penúltima, etc. (en caso de que k sea par ((2n+k)/2,(2n+k)/2) se corresponde a sí misma y no hay necesidad de volver a contar.
Entonces tenemos 2(n-k)+ k+1 = 2n-k+1. Evaluando en k desde n hasta 1 tenemos (n+1)+...+(2n) = n(3n+1)/2.
Entonces la cantidad que buscamos es [(n+1)(3n+2) + n(3n+1)]/2 = 3n^2 + 3n + 1

Marco dijo...

me equivoqué al decir como interpretar (a,b).. debería ser a objetos del tipo B y b objetos del tipo C :p

José A. dijo...

Pues por Inducción el caso base es muy simple.
Supongamos que en el caso N, se cumple que el número de formas de partirlo es 3N^2+3N+1
Entonces nosotros queremos que para el caso N+1 sea 3(N+1)^2+3(N+1)+1.
Primero, digamos que lo que vamos a contar el número de cosas A,B,C que tiene la persona 1, porque sabiendo qué tendrá la persona primera sabemos que lo que resta será de la segunda.
Entonces si yo tengo una tercia de números que funcionen (para el caso N) digamos (A;B;C) sabemos que la tercia (A+1;B+1;C+1) sirve para el caso N+1. Si tenemos una división (A,B,C) con A,B,C>0 entonces si le resto 1 a cada uno, va a ser una configuración única válida para el caso N, a menos que alguno de los números A,B,C sean 2n+2, en cuyo caso menos uno sería 2N+1 y como el caso N solamente puede tener en cada clase a lo más 2n.
Ahora, sabemos entonces que hay una biyección entre el número de soluciones del caso N+1 tal que cada clase tiene al menos un objeto y menos de 2n+2 y el número de configuraciones del caso N.
Ahora solamente nos falta contar los casos en donde uno de las clases tiene 0 (no puede haber 2 con cero por definición del problema), y el número de formas de que uno tenga 2n+2 y los demás los n+1 restantes.
CASO 1
Si hay un 0, digamos en la clase C, tenemos las tercias de la forma (A;B;0) A+B=3N+3 y A,B<2n+3
Por lo tanto el valor de A puede variar desde N+1 a 2N+2 lo que nos da un total de n+2 casos favorables. Análogamente con cero en clase A y cero en clase B hay en total 3n+6 casos favorables aquí.
CASO 2:
Supongamos que la tercia es (2n+2,B,C) sabemos que B+C=n+1 y que B,C>0 (porque si uno fuera cero, se hubiera contado en el caso anterior). Entonces el valor de B puede variar desde 1 hasta N, lo que nos da un total de N casos favorables. Análogamente con el 2N+2 en clase B y clase C tenemos un total de 3N casos.

Entonces el total de casos favorables del mismo fenómeno en N+1 es:
3N^2+3N+1+(3N+6)+(3N)=
3(N^2+2N+1)+3N+4=
3(N+1)^2+3(N+1)+1
Como esa era la fórmula a la que queríamos llegar, entonces podemos dar por terminada la demostración.

José A. dijo...

Soy José Ángel de Baja California por cierto

Anónimo dijo...

Primero se me ocurrió fijarme en el coeficiente de $x^{3n}$ en $(1+x+x^{2}+\dots+x^{2n})^{3}$ (pues el exponente representa la cantidad de objetos que tiene la primer persona de cada tipo y con esto se determina lo que el otro tiene), pero me dí cuenta que es más fácil ver que para cualquier potencia de $x$ entre $n$ y $3n$ en $(1+x+x^{2}+\dots+x^{2n})^{2}$ existe exactamente un término en $(1+x+x^{2}+\dots+x^{2n})$ que nos da la suma de $3n$ para el exponente, así que sumaremos la cantidad de términos que se encuentran con exponente entre $n$ y $3n$, para esto, sé que la suma de todos los coeficientes debe ser $(2n+1)^{2}$ pues la expresión $(1+x+x^{2}+\dots+x^{2n})$ tiene suma $2n+1$ de coeficientes, así que contaré los que están entre $0$ y $n-1$ y en un caso análogo, los de $3n+1$ a $4n$ y los restaré al total.

Sea $(1+x+x^{2}+\dots+x^{2n})=X$, entonces, veamos que sumar menos de $n$ con los exponentes es lo mismo que encontrar los casos con los que podemos sumar $0,1,\dots,n-1$, así que veamos cómo encontrar este número:
Para empezar, si de la primera caja, digamos, $A$ tomamos al $x^{n-i}$, entonces hay $i$ valores distintos que podemos sacar de $B$ para que se cumpla la condición: $1,x,x^{2},\dots,x^{i-1}$, así que como contaremos para todos los $n-i$, con $i\in\{1,2,\dots,n\}$, podemos ver que la suma es lo mismo que sumar todos estos $i$'s, en otras palabras $\sum_{i=1}^{n}{i}=\frac{n(n+1)}{2}$ y dado que el resultado para los exponentes entre $3n+1$ y $4n$ es análogo (simplemente dividimos todo entre $x^{4n}$ y hacemos lo mismo para exponentes negativos con valores absolutos entre $0$ y $n-1$), entonces el total es de $n(n+1)$.

Por tanto, la cantidad de formas es $(2n+1)^{2}-n(n+1)=4n^{2}+4n+1-(n^2-n)=3n^{2}+3n+1$ como queríamos.

Juan dijo...

Si para la primera persona escogemos k objetos A, entonces dividimos en casos. (nota: utilizo que ya que escojo los A's y los B's que tendrá la primera persona, el resto está determinado).
CASO I .0 menor o igual a k menor o igual a n
Aqui nuestro deber es escoger 3n-k objetos de los 4n B's y C's que tenemos. Pero de cada uno debo escoger al menos n-k (si escojo menos, del otro tipo escogería 2n+1 o más, imposible). Así, puedo escoger desde n-k hasta 2n B's para la persona 1, y como esta persona debe recibir exactamente 3 objetos, el numero de c's para la persona quedaría determinado. Así, si la persona tiene k objetos A, hay (2n)-(n-k)+1 =n+k+1 maneras de escoger el resto de los objetos. Sumando con todos los k, en este caso hay:
(n+1)n + (0+1+2+...+n)+(n+1)1 = (n+1)(n+(n/2)+1) = (n+1)(3n+2)/2 maneras.
CASO II: n menor a k menor o igual a 2n.
Si escojo b objetos B, b<3n-k+1 (pues no puedo escojer un número negativo de C's). Obviamente b=0 también se vale (simplemente escojo 3n-k C's, y como k>n esto se vale, pues 3n-k<2n). Así, hay 3n-k+1 valores para b, por lo que en este caso hay (sumando por todos los k),
n(3n) - ((n+1)+(n+2)+...+2n) + n(1) = 3n^2+n-(1+2+...+2n)+(1+...+n) = 3n^2 + n - n(2n+1) + n(n+1)/2 = n(3n+1-2n-1 + (n+1)/2) = n(2n+(n+1))/2 = n(3n+1)/2 maneras.
Así, la totalidad de maneras es:
((n+1)(3n+2) + n(3n+1))/2 = (6n^2 + 6n + 2)/2 =
3n^2+3n+1 maneras, la respuesta deseada. Q.E.D.

Adán dijo...

Procederemos usando separadores. Sean $Z_{1}$ y $Z_{2}$ las $2$ personas a las que se les darán los $3n$ objetos. Basta contar cuantas maneras hay para darle los objetos a $Z_{1}$, pues el resto de los objetos los tendrá $Z_{2}$.

Ahora, como $Z_{1}$ tendrá $3n$ objetos, y los clasificaremos en $3$ tipos, usaremos $2$ separadores, y el total de maneras de repartirle los objetos a $Z_{1}$ será $\binom{3n+2}{3n}=\frac{\left(3n+2\right)\left(3n+1\right)}{2}=\frac{9n^{2}+9n+2}{2}$.

Ahora, aquí estamos contemplando casos en donde algún tipo de objeto aparece más de $2n$ veces, lo cual no es posible. No podemos tener simultáneamente $2$ o más objetos repitiéndose más de $2n$ veces, pues tendríamos más de $4n$ objetos, y solo tenemos $3n$. Entonces, si hay algún tipo de objeto con más de $2n$ objetos, solo ese tipo tiene más de $2n$.

Entonces, si un tipo de objeto se repite $2n+k$ veces, con $1\leq k \leq n$, tendremos que la suma de los otros $2$ tipos de objetos es $n-k$. Esta suma puede ser obtenida de $n-k+1$ maneras, pues cada tipo de objeto aparece una cantidad no negativa de veces. Entonces para cada $k$ arriba, hay $n-k+1$ casos donde contamos $2n+k$ objetos de un solo tipo. Como $k=1, 2,\ldots$ tenemos que la cantidad de casos que queremos eliminar es $1+2+\ldots+n=\frac{n^{2}+n}{2}$. Pero estos casos son para un tipo de objeto en específico que se repitió, y son $3$ tipos distintos de objetos, por lo que el total de casos que vamos a eliminar es $3\cdot \frac{n^{2}+n}{2}=\frac{3n^{2}+3n}{2}$.

Entonces, el total de maneras de darle los objetos a $Z_{1}$ es $\frac{9n^{2}-3n^{2}+9n-3n+2}{2}=\frac{6n^{2}+6n+2}{2}=3n^{2}+3n+1$, y este es el total de formas de repartir los $6n$ objetos, que es lo que queríamos demostrar.

Miguel Ángel- Mike dijo...

Como en total hay 6n objetos y queremos repartirlos de manera equitativa (osea 3n objetos cada uno), al repartirle los objetos a la persona "1" entonces el resto ira para la persona "2" por lo tanto basta con ver las posibles formas de repartirle 3n objetos de entre los 6n que hay a la persona "1" (simplemente por elegir a alguien). Tenemos que si le repartimos los 2n objetos del tipo A, entonces podemos repatir desde 0 a n objetos del tipo B y por lo tanto el numero de objetos que falten por repartir podemos tomarlos del tipo C. Si tomamos 2n-1 objetos del tipo A, podemos tomar desde 0 a n+1 objetos del tipo B y por lo tanto lo que falte lo tomamos del tipo C. Y si tomamos 2n-2 objetos del tipo A, podemos tomar desde 0 a n+2 objetos del tipo B y el resto de C, y asi sucesivamente, pero como si tomamos X objetos del grupo A solamente podemos tomar desde 0 hasta (3n-X)objetos del grupo B, pero como solamente tenemos 2n objetos el grupo B, siguiendo la sucesión solo podemos llegar hasta cuando tomamos n objetos del grupo A. Cuando tomamos n-Y objetos del grupo A, solamente podemos tomar desde Y hasta 2n objetos del grupo B ya que la suma delos objetos de los grupos B y C debe ser 2n+Y y solamente tenemos 2n objetos del grupo C. Como Y< ó = n ya que no podemos tomar un número negativo de ojetos, entonces nuestro numero de formas de repartir nuestros objetos cuando el numero de objetos del tipo A es menor a n es igual a la sumatoria desde n+1 hasta 2n, que es igual a (2n)(2n+1)/2-(n)(n+1)/2= (3n^2 + n)/2. Como segun a como está formada la sucesión que se planteó al principio aplicable desde cuando el número de objetos dl tipo A va desde n hasta 2n es igual al sumatoria desde n+1 hasta 2n+1, que es igual a (2n+1)(2n+2)/2 - (n)(n+1)/2= (3n^2 + 5n +2)/2, por lo tanto, al sumr ambas sumatorias, tenemos que el número de formas de repartirle 3n objetos a la persona "1" es (3n^2 + n)/2 + (3n^2 + 5n + 2)/2 = 3n^2 + 3n + 1 lo cual es igual a el número de formas de repartirle 3n objetos a cada pesona de entre los 6n objetos que tenemos, tal y como queriamos probar.

Unknown dijo...

Yo conté todas las maneras de darle 3n a alguno de los dos sin la restircción de que halla 2n a lo mucho de cada uno, las maneras de hacer esto son 3n+2 en 2 (con separadores).

Solo falta descartar los casos en los que hay más de 2n de algún tipo (no puede ser que halla más de dos con mas de 2n porque tendríamos más de los 3n necesarios).

Si de algún tipo obtuviéramos un excedente de k objetos, de los demás solo tendríamos que pedirles n-k objetos.

Podemos elegir desde 0 hasta n-k de un tipo y del otro ya quedaría determinado, así que hay n-k+1 opciones, y k puede ir desde 1 hasta n, por lo que la suma de estás opciones (la cantidad de casos que eliminaremos) será de 1+2+...+n= n(n+1)/2= (n^2+n)/2.

Le vamos a quitar esto a la cantidad que teníamos una vez por cada objeto que se exceda, por lo tanto lo restaremos 3 veces (una por A, otra por B y otra por C).
Como la cantidad obtenida originalmente equivalía a (9n^2+9n+2)/2, la nueva cantidad será 3n^2+3n+1, que era lo que buscábamos demostrar :D pues si ya le dimos a uno esta cantidad al otro le dan lo otro :)

Enrique dijo...

Sean $P$ y $Q$ ambas personas. Primero, vemos que el número de maneras de repartir los objetos es igual al número de maneras de darle objetos a $P$, pues para cada manera de hacer esto, $Q$ está forzado a tomar los objetos que no tomó $P$. Sea $S$ el conjunto de ternas ordenadas de enteros no negativos $(a,b,c)$ tales que $a+b+c=3n$, y sea $G$ el subconjunto de $S$ tal que $(a,b,c)\in S \Leftrightarrow a,b,c\leq 2n$. Es evidente que $|G|$ es el número de maneras de repartir los objetos, pues para cada terna $(a,b,c)\in G$ podemos asociar $a$, $b$ y $c$ con el número de objetos tipo $A$,$B$,$C$, respectivamente, que recibe $P$. Además, para cada forma de darle objetos a $P$ hay una sola terna $(a,b,c)$ que cumple que $a$,$b$ y $c$ son el número de objetos tipo $A$, $B$ y $C$ que recibe $P$, y $(a,b,c)\in G$ pues $a+b+c=3n$ y $a,b,c\leq 2n$. Vemos que $|G|=|S|-|X|$, donde $X$ el conjunto de ternas ordenadas de enteros no negativos $(x,y,z)$ tales que $x+y+z=3n$, siendo $x$,$y$ o $z$ mayor o igual a $2n+1$.
Por separadores, como tenemos 2 separadores para repartir $3n$ objetos en 3 partes, $|S|=\binom{3n+2}{2}$. Por otro lado, para cada terna $(x,y,z)\in X$, sea $m$ el elemento de la terna que cumple que $m\geq 2n+1$. Como $3n-m\leq 3n-(2n+1)=n-1$, sólo hay un $m$ por terna. Ahora, hay $3$ maneras de elegir $m$. Además, para todo $m$ existen $3n-m+1$ maneras de escoger los otros dos elementos de la terna, pues dichos elementos deben sumar $3n-m$, por lo que las opciones son $(0,3n-m),(1,3n-m-1),(2,3n-m-2),...,(3n-m,0)$. Como $m$ puede ser cualquier entero de $2n+1$ a $3n$, $3n-m+1$ es cualquier entero de $0$ a $n$, por lo que $|X|=3(n+(n-1)+(n-2)+...+1+0)=\frac{3n(n-1)}{2}=3\binom{n}{2}$. Es fácil verificar que $|G|=|S|-|X|=\binom{3n+2}{2}-3\binom{n}{2}=3n^{2}+3n+1$.
$\blacksquare$

alberto dijo...

Queremos ver cuantas terminas (a,b,c) hay tal que $a+b+c=3n$ y $a,b,c \leq 2n$. Donde a, b y c son los objetos del tipo A, B y C respectivamente que le damos a la primer persona.
Primero vemos cuantas hay sin considerar la segunda restriccion, que por separadores es $\binom{3n+2}{2}$, y ahora hay que quitarle cuando alguno de los tres es mayor a 2n.
spdg $a>2n \iff 3n=a+b+c > 2n +b+c \iff n>b+c$
Entonces queremos encontrar cuando b y c suman menos de n, que pueden sumar {0,1,2,...,n-1}, que por separadores se puede de $\binom{1}{1}+\binom{2}{1}+ \dots +\binom{n}{1}$. Como puede ser a, b o c el que sea mayor, multiplicamos por 3 y tenemos todos los casos cuando alguno es mayor a 2n. Entonces el resultado que queremos es:

$\binom{3n+2}{2}-3[\binom{1}{1}+\binom{2}{1}+ \dots +\binom{n}{1}]$
$= \frac{(3n+2)(3n+1)}{2} -3[1+2+ \dots +n]$
$=\frac{(3n+2)(3n+1)}{2}-\frac{3n(n+1)}{2}$
$=\frac{(9n^2+9n+2-3n^2-3n}{2}$
$=\frac{(6n^2+6n+2}{2}=3n^2+3n+1$
que es lo que queremos

alberto dijo...

La parte de latex que no sale completa dice:

$a>2n \iff 3n=a+b+c>2n+b+c$
$\iff n>b+c$

JulioC dijo...

solucion: ver que basta asignarle a una persona una tercia x,y,z (donde x son las del primer tipo, y las del primer tipo,etc) tal que x+y+z=3n y x,y,z<=2n; automaticamente la otra tercia esta definida, entonces veo conseparadores que si le quitamos la condicion x,y,z<=2n hay 3n + 2 en 2 soluciones, y si una de estas soluciones no sirve es porque alguno (es claro que solamente puede ser uno) es mayor que 2n y pues si suponemos que es x, entonces por separadores si x= 2n + i entonces hay n+1-i en uno que es n+1-i y pues la suma de estas posibilidas con i de 1 a n es 1+2+...+n = (n(n+1))/2; ahora multiplicamos ese numero por tres pues puede ser cualquiera de x,y,z. Y al hacer la resta 3n + 2 en 2 soluciones - 3(n(n+1))/2, nos da el numero q buscamos: 3n^2+3n+1

Unknown dijo...

Digamos que la primer persona obtuvo $0\leq k\leq n$ de $A$, asi que puede tener $3n-k\geq 2n$ entre $B$ y $C$ juntos. Entonces hay $n+1+k$ opciones. Para $n\leq k\leq 2n$, se tiene que entre $B$ y $C$ hay $3n-k \leq 2n$, entonces hay $3n+1-k$ opciones. Entonces hay en total $(n+1)+(n+2)+\cdots (2n+1)+2n+(2n-1)+\cdots +(n+1)=((n+1)+2n))+((n+2)+(2n-1))+\cdots ((2n)+(n+1))+2n+1=n(3n+1)+2n+1=3n^{2}+3n+1$

Publicar un comentario