Pieces of paper without consecutivity condition

Question

TL;DR: like this puzzle but with an arbitrary number of papers and without the condition that the papers chosen must be consecutive.

You are given $n$ pieces of paper, and you write down $n$ distinct natural numbers, any numbers you like, one on each piece of paper. Then the pieces of paper will be mixed up and laid upside down on the table in a random order. You are allowed to ask the sum of the numbers on any selection of the papers (they may be consecutive papers or not), even a selection of just one piece of paper if you wish.

What is the minimum number of questions you need to ask to know every single number in order?

Answer 1

You can get at most

one bit of information per piece of paper: "in" or "out". That is, if you've labelled your numbers perfectly, the most you can know from each result is whether each number is in your selected group.

This is possible to achieve:

Label your slips as 1, 10, 100, 1000..., and so on. This lets you easily read off which slips are in your group just by the "1" digits in your result.

---

So now we've reduced the problem to the variant where

instead of being told the sum, you are told which slips are in the group.

Here's an optimal strategy:

First, check half of the slips. You've now sorted your initial numbers into "was in the first set" and "was not in the first set" categories.

Now, these are two separate problems just like the original: you know the numbers in each category, but not their order. So you can solve each of these as a separate problem! On the first turn, you pick half of each of the categories. (You can make your selections for both categories together. All the numbers are different, and you know which numbers are in which categories, so there's no "interference".)

Once you've done that, you now have four categories! These are once again problems just like the original, but smaller. So you can continue this process, picking half of each category each time. Once all of your categories are just a single slip, you're done!

This is optimal because:

Consider the largest category that you don't know the order of. In order to solve the problem, you must get that size down to 1. And for any strategy, each turn, the size of this largest category will be halved at best. (If you don't cut it in half, then one piece will be larger than half the original size.)

So this strategy is optimal, since it always cuts each category in half.

Answer 2

Without restriction of only checking consecutive papers

I agree that Deusovi's answer is optimal. It is a similar approach to playing a number guessing game where you are told "higher" or "lower" when making a guess. The strategy is to divide the problem in half each time. Since you know which group each number is in after checking the sum, you can check halves of all current groups simultaneously.

The general solution for $n$ would be:

$$\left\lceil log_2{(n)}\right\rceil$$

Visualization:

With condition of only checking consecutive papers

I believe this is the general equation for $n$:

$$\begin{cases} 0 & n = 1 \\ \left\lceil\frac{n}{2}\right\rceil & n > 1 \end{cases}$$

---

For one paper, you already know the number so no questions necessary. For 2 papers, 1 question is necessary to differentiate the two.

For $n > 2$:

Write powers of 2: $\{1,2,4,8,16, \dots\}$ and make decisions as done with $n=15$.

With $3$ papers, write $1, 2, 4$. First, check the sum of the first 2 papers. By the binary representations having every digit unique, you know the 2 numbers on these papers (but not the order). Check the last 2 to know which paper is in the middle one and by deduction, you now know the first paper and last paper. 2 questions necessary.

With $4$ papers, write $1, 2, 4, 8$. First, check the sum of the first 2 papers. You now know the 2 numbers on these papers but not the order. Check the 2nd and 3rd to know which paper is in the second (and by deduction also the first and third). Since there is only 1 paper left, you know it must be the only remaining number. 2 questions necessary.

With $5$ papers, write $1, 2, 4, 8, 16$. First, check the sum of the first 2 papers. You now know the 2 numbers on these papers but not the order. Check the 2nd, 3rd, and 4th to know which paper is in the second (and by deduction also the first). Check the last 2 to know the fourth paper (and by deduction the third and fifth). 3 questions necessary.

With $6$ papers, write $1, 2, 4, 8, 16, 32$. First, check the sum of the first 2 papers. You now know the 2 numbers on these papers but not the order. Check the 2nd, 3rd, and 4th to know which paper is in the second (and by deduction also the first). Check the 4th and 5th papers to know the internal order of those and deduce the third. Since only one paper has remained unchecked, you know all 6 papers. 3 questions necessary.

7 or 8 papers - 4 questions
9 or 10 papers - 5 questions
11 or 12 papers - 6 questions
13 or 14 papers - 7 questions
15 or 16 papers - 8 questions
17 or 18 papers - 9 questions $\dots$

Answer 3

As an example, say we have numbers 1, 2, 3. Then, we find the sum of the three numbers, which is six. Then, we take the numbers and lay them out in a row. Then, we ask the sum of two slips. Then, we ask for the sum of another two slips. The one with the greater sum has the biggest number in the group. The one with the smaller sum would have the smaller number in its group. Then, to know which one is the middle number, we take the value of both groups minus away six, and you get the middle number.

Take another example. This time, we have the numbers 1, 2, 3 and 4. We ask the sum of two numbers twice (with one including in both sums), and once again, the one with the greatest sum contains the greatest number and vice versa. This time, though, as long as one sum is greater than 6, you know that 4 is included in one of the sums. If so, you know that the number that was added together with 4 (the group with the greatest sum) is either 2 or 3. If the sum is 6, 2 was added with four. If the answer is seven, 3 was added with four. If the other sum is 6, then two was added with four, or three with four if the answer is seven. The number that was not included is the remaining number that wan't touched at all.

Thus, as @eyl327 stated:
Five/Six Numbers would take 3 questions,
Seven/Eight Numbers would take 4,
Nine/Ten Numbers would take 5.

And this would continue on and on