El principio del encasillamiento: ¿cómo resolver este tipo de cuestiones?

Question

Tenemos dos secuencias , $(a_i)_{i=1}^{2n}$ y $(b_i)_{i=1}^{2n}$ tal que $1\leq a_i, b_i\leq n$ por cada $i$ .

Demuestre que hay dos conjuntos de índices $I, J \subseteq \left \{ 1,2, ... 2n \right \}$ tal que $\sum_{i\in I}a_i=\sum_{j\in J}b_j$ .

Bueno, la pregunta no decía nada de que esos conjuntos estuvieran vacíos pero creo que no se refería a eso. No sé que hacer con preguntas como estas. Obviamente hay muchos más subconjuntos que sumas posibles ( $2^{2n}-1$ en comparación con $2n^2$ ) pero realmente no ayuda.

Estaré encantado de escuchar ideas, consejos o soluciones.

Answer 1

Estoy asumiendo que $a_i$ y $b_i$ denotan números enteros, aunque esto no se indica en el PO.

Definir $S_j = \sum_{i=1}^j a_i$ y $T_k = \sum_{i=1}^k b_i$ Así que $1 \leq S_j \leq 2n^2$ y $1 \leq T_k \leq 2n^2$ para $1 \leq j \leq 2n$ y $1 \leq k \leq 2n$ . Obsérvese que el $S_j$ son todos distintos, y también lo son los $T_k$ 's. Tenemos $|S_j - T_k| \leq 2n^2-1$ , por lo que hay $4n^2-1$ posibles valores de $S_j-T_k$ para $1 \leq j \leq 2n$ y $1 \leq k \leq 2n$ .

Considere la $4n^2$ pares $(S_j, T_k)$ para $1 \leq j \leq 2n$ y $1 \leq k \leq 2n$ . Como hay más pares que valores posibles de $S_j-T_k$ por el principio de encasillamiento debe haber al menos dos pares distintos, digamos $(S_j,T_k)$ y $(S_l, T_m)$ , que corresponden a la misma diferencia, es decir $$S_j- T_k = S_l - T_m$$ También podemos suponer, sin pérdida de generalidad, que $j > l$ . Entonces $$S_j - S_l = T_k - T_m$$ implica $$\sum_{i=l+1}^j a_i = \sum_{i=m+1}^k b_i$$