Difficult word problem, looks like statistics/combinatorics. Having trouble making progress

Question

"A trader has discovered a source of 1000 unique types of stamps which she can buy in bulk and then sell to a network of 100 merchants through an intermediary. No matter what type of stamp, she pays $1 for each stamp. Each day, she can sell up to 100 bags of stamps (each bag containing one or more different stamps, with no limit on how many stamps can be in each bag), and she is paid the next day. Unfortunately, the intermediary hides the prices of the individual stamps, and only tells the trader the per-bag price. In order to consistently turn a profit at a reasonable margin, it would be helpful to know which of the 1000 types of stamps are the most valuable, so she could sell bags with only the most valuable stamps. Given 7 days to evaluate 1000 types of stamps using 100 bags/day max, how does she figure out which types of stamps are the most valuable?"

So, just need to find the most valuable stamp of the 1000 stamps.

I'm having trouble doing better than brute force. i.e. 700 bags with one stamp each. I've considered a couple approaches, but each one seems to be equal to brute force. I don't have much stats/combinatorics experience. I need to figure out how to eventually learn about the price of y stamps using only x bags, where x<y.

I can find the average stamp price, but since there's no assumed distribution of prices, I'm not sure how finding the average price would be useful. Finding the median price isn't possible. I could investigate the price variance, but it could only be an approximation. What seems to really throw me off is the fact that the prices aren't distributed in any particular way, which makes me concerned about the accuracy of approximations. To top it off, I'm not sure if the problem is solvable, or if an approximation is the best possible outcome.

Ideas I've tried:

selling bags of some number of stamps and checking the average price of the group, but again I can't seem to make use of the average price, given that there's no price to compare it too other than the cost of $1.

When I think about selling bags with some number of stamps in them, the unknown variance gives me a hard time making use of the resulting prices.

If anyone knows what kind of problem this is, or some statistical principle/theorem is at play, please let me know and I'll study it. I've had no luck with google, and my bachelors was in applied math with no stats experience whatsoever

Answer 1

Here's an idea. It only works assuming that stamps are integer-priced and that there are super-astronomical numbers of stamps in existence and at least one bag which is bigger than the universe. If the prices are not integer-valued, the problem is impossible per Ross Millikan's answer.

First, sell a bag containing one of each kind of stamp, and get $M$ dollars in return. Then $M$ is an upper bound on the price of any stamp.

Let $k$ be the length of the decimal representation of the number $M+1$, so that $M<10^{k+1}$. Now create a new bag containing the following stamps. Let $i=1,\dots,1000$ enumerate the types of stamps, and for each type $i$, put $10^{(i-1)\cdot(k+1)}$ stamps into the bag.

Now, if $p_i$ is the price for stamp type $i$, then the price of that bag of stamps will be $$p_1 + p_2 \cdot 10^{k+1} + p_3 \cdot 10^{2(k+1)} + \dotsm + p_{1000} \cdot 10^{1000(k+1)}.$$ This is a very long number, but it is made up of 1000 sequences of length $k+1$ from which the prices $p_i$ can be read off in order.

Answer 2

You can get the values of any $700$ packages you want. That will not give you the values of $1000$ stamps because you have fewer equations than unknowns. If you know the values of the stamps are integral, you might be able to do something with multiples, but you certainly can't guarantee it.

I would make $500$ pairs of stamps and sell those the first five days, then take the $200$ most valuable pairs and sell one stamp of each the last two days. We will get the value of the $400$ stamps that made up the most valuable pairs. We will miss the most valuable stamp if it is paired with a very cheap stamp while there are lots of pairs with both stamps of middling value.