número de formas de particionar $S=\{1,2,\dots,2020\}$ de modo que dado $a\in A, b\in B: \ a + b $ nunca es múltiplo de 20 y 1024

Question

Hallar el número de maneras de dividir $S=\{1,2,\dots,2020\}$ en dos conjuntos disjuntos A y B con $A \cup B = S$ de modo que si elige un elemento $a \in A$ y $b \in B:\ a + b$ nunca es múltiplo de 20. A o B puede ser el conjunto vacío, y el orden de A y B no importa. En otras palabras, el par de conjuntos (A, B) es indistinguible del par de conjuntos (B, A).

mi primera aproximación fue tratar de resolver para un caso más simple como $S=\{1,2,\dots,20\}$ . Anoté $20=(19+1)=(18+2)=(17+3)= \dots =(9+11)$ , lo interesante de estos pares es que observen que los elementos de cada par deben estar estrictamente en el mismo conjunto de lo contrario se sumarían para dar un múltiplo de 20, los restantes eran 20 y 10 de los cuales 10 podrían colocarse en cualquiera de los dos grupos y el elemento 20 también podría ir en cualquiera de los dos conjuntos excepto en el caso en que consideremos conjuntos nulos. En mi opinión, en el caso más sencillo, si dejaba fuera los conjuntos nulos y el problema con 10 y 20, el número total de conjuntos necesarios era 9C1+9C2+9C3+ . . . + 9C8

Answer 1

En primer lugar, supongamos que tenemos una partición aceptable y que $x \equiv y \pmod{20}$ . Si $x$ y $y$ están en lados diferentes de la partición, entonces al menos uno de ellos debe estar en el mismo lado que $20-x$ . Esto contradice nuestra suposición de que la partición es aceptable. Por lo tanto, todos los elementos de la misma clase de equivalencia $\pmod {20}$ deben ir dentro del mismo lado de la partición.

Eso significa que el caso más sencillo que ya ha analizado nos da la solución. Hay nueve pares de clases de equivalencia que suman $20$ . Cada uno debe ir en el mismo lado de la partición. Además, la clase de equivalencia de $10$ y la clase de equivalencia de $20$ puede ir en cualquier lado de la partición.

Designemos arbitrariamente el lado de la partición que contiene la clase de equivalencia de $20$ como $A$ . Entonces usted tiene $2$ opciones para cada uno de los $10$ "pares" de clases de equivalencia (donde tratamos la clase de equivalencia de $10$ como pareja). Cada "par" puede entrar en $A$ o en $B$ . Por lo tanto, el número total de particiones aceptables es $2^{10}=1024$ .