Si $A=\{n | n \in N, n\le 100\}$ ¿Qué número tiene más representaciones como la suma de los elementos de un subconjunto de $A$ ?

Question

Si $A= \{n | n \in N, n\le 100\} $ qué número tiene más representaciones como suma de los elementos de un subconjunto de $A$ ¿y por qué?
Mi opinión sería $\frac{100.101}{2}$ pero no estoy seguro de cómo se puede demostrar.

Answer 1

No se me ocurre una buena prueba. Pero un poco de Python muestra que tienes razón, el máximo único se consigue con $2525$ .

import collections
counts = collections.defaultdict(int)

# There is one way to express 0 as a sum of a subset of the empty set.
counts[0] = 1

for element in range(1, 101):
  # Add counts to itself right-shifted by element
  for target in range(len(counts) - 1, -1, -1):
    counts[target + element] += counts[target]

maximum = max(counts.values())
print maximum
print [x for x, count in counts.items() if count == maximum]

1731024005948725016633786324
[2525]