¿Cuántos pares de subconjuntos se pueden formar?

Considere el siguiente problema:

Dejar S ( A ) representar la suma de los elementos de un conjunto A de tamaño norte . Lo llamaremos un conjunto de suma especial si para dos subconjuntos disjuntos no vacíos cualesquiera, B y C , las siguientes propiedades son verdaderas:

  1. S ( B ) ≠ S ( C ) ; es decir, las sumas de subconjuntos no pueden ser iguales.

  2. Si B contiene más elementos que C entonces S ( B ) > S ( C ) .

Para este problema supondremos que un conjunto dado contiene norte elementos estrictamente crecientes y ya cumple la segunda regla.

Sorprendentemente, fuera del 25 posibles pares de subconjuntos que se pueden obtener de un conjunto para el cual norte = 4 , solo 1 de estos pares deben probarse para la igualdad (primera regla). Del mismo modo, cuando norte = 7 , solo 70 fuera de 966 los pares de subconjuntos necesitan ser probados. Para norte = 12 , cuantos de los 261625 pares de subconjuntos que se pueden obtener necesitan ser probados para la igualdad?

mi pregunta es porque para norte = 4 hay 25 posibles pares de subconjuntos? Si mis cálculos son correctos, entonces el número debe ser igual 21 .

Mi lógica es la siguiente:

Nota: no soy matemático, por lo que no estoy seguro de si el término "longitud del conjunto" existe en matemáticas, así que solo para asegurarme, "longitud del conjunto" a continuación se refiere a la cantidad de elementos que contiene el conjunto (por ejemplo, longitud de { 2 , 3 , 4 } igualará 3 )

  1. El problema especifica que si las longitudes de dos subconjuntos no son iguales, el subconjunto con mayor longitud tendrá una suma mayor. Por lo tanto, cuando probamos la igualdad de conjuntos, solo consideramos pares de subconjuntos con la MISMA longitud.
  2. Los pares de subconjuntos con longitud 1 deben ignorarse, porque cada valor en el conjunto es único.
  3. Considere subconjuntos con longitud 2. En total hay Combinaciones (4,2) = 6 subconjuntos. Para 6 subconjuntos, hay Combinaciones (6,2) = 15 pares que se pueden formar.
  4. Considere subconjuntos con longitud 3. En total hay Combinaciones (4,3) = 4 subconjuntos. Para 4 subconjuntos, se pueden formar combinaciones (4,2) = 6 pares.
  5. Debido a que solo hay un subconjunto con longitud 4, no se pueden formar pares.
  6. Total = 15 + 6 = 21

¿Dónde cometí el error?

@EricTowers Para un conjunto arbitrario {x1,x2,x3,x4....,xn}, S(A) = x1+x2+x3+x4...+xn. Entonces si A = {4,6,8,10}, entonces S(A) = 4+6+8+10 = 28
A menudo usamos el término "cardinalidad" de un conjunto para indicar su tamaño.

Respuestas (2)

Cada elemento de o norte -conjunto de elementos A tiene tres posibilidades: Puede ser elemento de B , o de C , o de ninguno. Por lo tanto, contamos 3 norte formas de tener dos subconjuntos disjuntos B , C de A . Pero B debe ser no vacío; por lo tanto restamos el 2 norte casos donde B = ∅ y C es alguno de ellos 2 norte subconjuntos de A . De la misma manera restamos el 2 norte casos donde C = ∅ y B es cualquier subconjunto de A . Uy, restamos el caso B = C = ∅ dos veces, por lo tanto, debemos volver a agregarlo. Entonces contamos

(1) 3 norte − 2 norte − 2 norte + 1
formas de elegir subconjuntos no vacíos disjuntos B , C de A . Seguimos contando en exceso en la medida en que contamos pares ordenados de subconjuntos. como permuta B con C realmente no hace una diferencia, estamos interesados ​​en la mitad de ( 1 ) , es decir, en
(2) 3 norte + 1 2 − 2 norte
pares desordenados de subconjuntos disjuntos no vacíos de A . Para norte = 4 , ( 2 ) es igual 81 + 1 2 − dieciséis = 25 . Este es el 25 se refiere el enunciado del problema. Tenga en cuenta que esto todavía cuenta pares de diferentes tamaños (para los cuales solo necesitamos verificar la condición 2) y pares de conjuntos únicos (para los cuales la condición 1 es trivialmente cierta). De hecho, por A = { a , b , C , d } con a < b < C < d solo necesitamos verificar B = { a , d } , C = { b , C } si ya sabemos que la condición 2 se cumple. Esto se debe a que por ejemplo a + C < b + d sigue ya sin control explícito de a < b y C < d .

¿Conteo de inclusión-exclusión? ¡muy lindo! :)

Explícitamente, la lista de pares de subconjuntos son

{1},{2}
{1},{3}
{1},{4}
{2},{3}
{2},{4}
{3},{4}
{1,2},{3}
{1,2},{4}
{1,3},{2}
{1,3},{4}
{1,4},{2}
{1,4},{3}
{2,3},{1}
{2,3},{4}
{2,4},{1}
{2,4},{3}
{3,4},{1}
{3,4},{2}
{1,2},{3,4}
{1,3},{2,4}
{1,4},{2,3}
{1,2,3},{4}
{1,2,4},{3}
{1,3,4},{2}
{2,3,4},{1}

Tenga en cuenta que estamos contando pares con diferentes tamaños aquí, y que muchos de los candidatos que creó su método (como 12 de los "15" pares de subconjuntos de tamaño 2) no se cuentan porque no son disjuntos.

En cuanto a verificar la igualdad, necesitamos verificar la igualdad si: 1. los dos subconjuntos tienen la misma cardinalidad, y 2. no es cierto que el norte El elemento más grande en un subconjunto particular siempre es más grande que el norte El elemento más grande en el otro: si todos los ganadores están en un lado, el otro lado posiblemente no pueda cerrar la brecha. De los 90 pares de subconjuntos para conjuntos de tamaño 5, 15 tienen ambos subconjuntos del mismo tamaño y sus tamaños son mayores que 1, y solo 5 de ellos cumplen con el requisito de pedido que hace posible que resulten iguales: {1,4 },{2,3}; {1,5},{2,3}; {1,5},{2,4}; {1,5}, {3,4}; y {2,5}, {3,4}.

¿Cuántos pares de subconjuntos se pueden formar?
RespuestasAquíPolítica de privacidad1y, 1v