14
$\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?

$\endgroup$
  • 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 at 8:29
  • 1
    $\begingroup$ @DanielMathias you are right, I fixed that part. $\endgroup$ – Oray Mar 25 at 8:30
  • 5
    $\begingroup$ ^ Upvote for @DanielMathias purely for the choice of 42 as the arbitrary number... $\endgroup$ – Stiv Mar 25 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 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 at 21:17
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.

$\endgroup$
  • 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 at 13:44
  • 1
    $\begingroup$ @Bass 1, 10, 100... $\endgroup$ – Daniel Mathias Mar 25 at 14:32
  • 1
    $\begingroup$ @DanielMathias sure, but can you tell 13 zeroes from 14 at a glance? $\endgroup$ – Bass Mar 25 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.

$\endgroup$
  • $\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 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.

New contributor
ED209 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 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 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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