15
$\begingroup$

You are given $15$ pieces of paper, you are asked to write down any distinct integer numbers on them as you wish. Then these pieces of paper will be turned back, mixed and put on the table in a straight order. After that, you are allowed to ask the sum of numbers in the face down papers for as many papers next to each other as you want, but you cannot ask separate paper sums, they have to be consecutive papers. Though you may even ask a specific number in a piece of paper if you wish.

What is the minimum number of questions you need to ask to know every single number on the papers?

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ I think you should ask for 15 distinct numbers, otherwise I could write 42 on each paper and ask no questions. $\endgroup$
    – Daniel Mathias
    Mar 25, 2020 at 8:29
  • 1
    $\begingroup$ @DanielMathias you are right, I fixed that part. $\endgroup$
    – Oray
    Mar 25, 2020 at 8:30
  • 5
    $\begingroup$ ^ Upvote for @DanielMathias purely for the choice of 42 as the arbitrary number... $\endgroup$
    – Stiv
    Mar 25, 2020 at 12:17
  • $\begingroup$ Is there some particular reason the puzzle doesn't have 16 paper pieces? Rand's solution could solve that, too: with "n, o" as the final sum, 15 pieces get positively identified, so there'd only be one possibility for the 16th one. $\endgroup$
    – Bass
    Mar 25, 2020 at 20:56
  • $\begingroup$ @Bass no actually i knew that 16 pieces of paper would have the same answer. though i just want to make sure whether if 15/16 would be different answers or not. Someone could come up with better solution than mine. $\endgroup$
    – Oray
    Mar 25, 2020 at 21:17

3 Answers 3

Reset to default
11
$\begingroup$

By choosing appropriate numbers to write at the start, you can manage it with

eight questions.

Here's how.

Choice of numbers

The numbers you should write at the beginning are

the powers of 2: $1,2,4,8,16,32,...$

Let's label the numbers, in the new order as they're laid out face down, $a,b,c,d,e,f,g,h,i,j,k,l,m,n,o$.

Every time you ask a question about some subset of consecutive papers, you know

the exact (unordered) set of numbers on those papers. This is the maximum amount of information you can get from one question, since knowing the sum cannot tell you anything about the order.

Note that this condition (in the last spoilertag just above) is the important thing. There's nothing special about the particular set of numbers I mentioned: you could as easily use

e.g. powers of 10, which would make the required deductions quicker for those not used to binary representations.

Choice of questions

  1. With your first question, you choose

    $a,b$.

  2. With your second question, you choose

    $b,c,d$. Now you know exactly what $a$ and $b$ are, and you know the unordered set $\{c,d\}$.

  3. With your third question, you choose

    $d,e,f$. Now you know exactly what $c$ and $d$ are, and you know the unordered set $\{e,f\}$.

Keep going in this way, choosing

$f,g,h$ then $h,i,j$ then $j,k,l$ then $l,m,n$.

After that, you know

all numbers except $m$ and $n$, which you only know as an unordered pair. One more question is enough to know which is which among them.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Since we are (probably) getting the sums in decimal, I think I'd choose 12-19 and 23-29 instead, each multiplied by a unique power of 100; that'd be 12, 1300, 140000 and so on. As long as the possible sums are all unique, the actual numbers are arbitrary, and this way each constituent number is clearly visible in the sum, making partitioning a breeze. The effect is purely practical of course, and doesn't affect the solution. (Which seems curiously optimal, by the way: I don't think there's anything better, but this method would work with 16 pieces of paper too.) $\endgroup$
    – Bass
    Mar 25, 2020 at 13:44
  • 1
    $\begingroup$ @Bass 1, 10, 100... $\endgroup$
    – Daniel Mathias
    Mar 25, 2020 at 14:32
  • 1
    $\begingroup$ @DanielMathias sure, but can you tell 13 zeroes from 14 at a glance? $\endgroup$
    – Bass
    Mar 25, 2020 at 16:40
4
$\begingroup$

I can prove that

Eight questions

is minimal.

The difficulty comes in distinguishing each of the 14 pairs of neighboring slips of paper, as well as the first and last papers. There are 15 such pairs of slips of paper. If a question includes or excludes both slips, the response will be the same if those slips were swapped. In contrast, a question can only distinguish the ordering of two slips if it includes one but not the other. We can only recover the full ordering if we distinguish the ordering of each pair. But each question can only distinguish two pairs - corresponding to the two endpoints of the sequence queried. In particular, the first and last papers can only be distinguished if one of the endpoints is an end of the sequence.

Since we have 15 pairs to distinguish, and we can distinguish at most 2 per question,

We need at least 8 questions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ One can prove better than that: if there are 16 slips of paper, any set of questions which each involve at least two slips, and collectively involve all 16 endpoints excluding the one following the last one, will allow one to determine the ordering. In fact, if one is told which sum includes the leftmost slip, one wouldn't need to be told anything else about the questions! $\endgroup$
    – supercat
    Mar 25, 2020 at 22:33
0
$\begingroup$

Maybe I missed the point here but surely if you used values 1,2,4,8,16....32768 you could tell which two values were selected in any pair, so you'd have at most 2 possibilities for each piece of paper. By mutual exclusion and 'walking' your way along you could identify each value. This would take 14 goes at most.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I think you did miss the point, which is to find the minimum required number of questions. Yes, it can very easily be done in 14 goes, but we don't need that many. $\endgroup$
    – Rand al'Thor
    Mar 26, 2020 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.