Skip to main content
Puzzling

Return to Answer

added 457 characters in body
Source Link
f''
f''
  • 33.9k
  • 4
  • 121
  • 165

  1. An obvious way to select the weights is to have them be powers of 2, from 1 to $2^{99}$. Every positive integer has a unique binary representation, so no two different sets of weights can be have the same total weight.

  2. There are $2^{100}$ possible sets of weights. If any two of them have the same weight, then they can be balanced (removing any weights that show up on both sides), so all of the sets must have different weights. To have the smallest possible total weight, the sets must weigh $0,1,2,...,2^{100}-1$. The binary construction has a total weight of $2^{100}-1$, so this is the minimum.

  • The set of powers of 2 is also the only way to achieve this total weight: To have a total weight of $2^{100}-1$, every integer from 0 to $2^{100}-1$ must correspond to some set of the weights. In particular, if we choose the weights from lowest to highest, we must always choose the smallest integer that is not a sum of any other set of weights, because otherwise there would be no set with that as its total weight. Then ant11's construction is forced.

  1. An obvious way to select the weights is to have them be powers of 2, from 1 to $2^{99}$. Every positive integer has a unique binary representation, so no two different sets of weights can be have the same total weight.

  2. There are $2^{100}$ possible sets of weights. If any two of them have the same weight, then they can be balanced (removing any weights that show up on both sides), so all of the sets must have different weights. To have the smallest possible total weight, the sets must weigh $0,1,2,...,2^{100}-1$. The binary construction has a total weight of $2^{100}-1$, so this is the minimum.

  1. An obvious way to select the weights is to have them be powers of 2, from 1 to $2^{99}$. Every positive integer has a unique binary representation, so no two different sets of weights can be have the same total weight.

  2. There are $2^{100}$ possible sets of weights. If any two of them have the same weight, then they can be balanced (removing any weights that show up on both sides), so all of the sets must have different weights. To have the smallest possible total weight, the sets must weigh $0,1,2,...,2^{100}-1$. The binary construction has a total weight of $2^{100}-1$, so this is the minimum.

  • The set of powers of 2 is also the only way to achieve this total weight: To have a total weight of $2^{100}-1$, every integer from 0 to $2^{100}-1$ must correspond to some set of the weights. In particular, if we choose the weights from lowest to highest, we must always choose the smallest integer that is not a sum of any other set of weights, because otherwise there would be no set with that as its total weight. Then ant11's construction is forced.
deleted 69 characters in body
Source Link
f''
f''
  • 33.9k
  • 4
  • 121
  • 165

  1. An obvious way to select the weights is to have them be powers of 2, from 1 to $2^{99}$. Every positive integer has a unique binary representation, so no two different sets of weights can be have the same total weight.

  2. There are $2^{100}$ possible sets of weights. If any two of them have the same weight, then they can be balanced (removing any weights that show up on both sides), so all of the sets must have different weights. To have the smallest possible total weight, the sets must weigh $0,1,2,...,2^{100}-1$. The binary construction has a total weight of $2^{100}-1$, so this is the minimum.

  3. Not sure yet. {2,4,6,7} shows that $2^{n-1}$ isn't a hard limit.

  1. An obvious way to select the weights is to have them be powers of 2, from 1 to $2^{99}$. Every positive integer has a unique binary representation, so no two different sets of weights can be have the same total weight.

  2. There are $2^{100}$ possible sets of weights. If any two of them have the same weight, then they can be balanced (removing any weights that show up on both sides), so all of the sets must have different weights. To have the smallest possible total weight, the sets must weigh $0,1,2,...,2^{100}-1$. The binary construction has a total weight of $2^{100}-1$, so this is the minimum.

  3. Not sure yet. {2,4,6,7} shows that $2^{n-1}$ isn't a hard limit.

  1. An obvious way to select the weights is to have them be powers of 2, from 1 to $2^{99}$. Every positive integer has a unique binary representation, so no two different sets of weights can be have the same total weight.

  2. There are $2^{100}$ possible sets of weights. If any two of them have the same weight, then they can be balanced (removing any weights that show up on both sides), so all of the sets must have different weights. To have the smallest possible total weight, the sets must weigh $0,1,2,...,2^{100}-1$. The binary construction has a total weight of $2^{100}-1$, so this is the minimum.

Source Link
f''
f''
  • 33.9k
  • 4
  • 121
  • 165

  1. An obvious way to select the weights is to have them be powers of 2, from 1 to $2^{99}$. Every positive integer has a unique binary representation, so no two different sets of weights can be have the same total weight.

  2. There are $2^{100}$ possible sets of weights. If any two of them have the same weight, then they can be balanced (removing any weights that show up on both sides), so all of the sets must have different weights. To have the smallest possible total weight, the sets must weigh $0,1,2,...,2^{100}-1$. The binary construction has a total weight of $2^{100}-1$, so this is the minimum.

  3. Not sure yet. {2,4,6,7} shows that $2^{n-1}$ isn't a hard limit.