7
$\begingroup$

A puzzle from John Conway and Pizza Hut. (The competition has ended, so I think it's okay to post the puzzle here.)

Our school’s puzzle-club meets in one of the schoolrooms every Friday after school.

  • Last Friday, one of the members said, "I’ve hidden a list of positive integers in this envelope that add up to the number of this room."
  • A girl said, "That's obviously not enough information to determine the numbers on your list. If you told us the number of numbers in the envelope and their product, would that be enough to work them all out?"
  • He (after scribbling for some time): "No."
  • She (after scribbling for some more time): “well, at least I’ve worked out their product.”

What is the number of the school room we meet in?”

$\endgroup$
  • 2
    $\begingroup$ Can we assume that the numbers in the envelope are all positive integers? $\endgroup$ – user2390246 Apr 1 '16 at 9:57
  • $\begingroup$ I really don't understand this question...there're no limits on the quantity or type of numbers (natural, integer, real, etc), so the answer could be anything. If the number "0" is included anywhere in the list, then the product would be zero, then that accounts for the product not revealing the answer. $\endgroup$ – Liesmith Apr 1 '16 at 12:11
  • $\begingroup$ @user2390246 This isn't a problem from OP (it's a direct copy of all the text from the Pizza Hut website), so I don't think we'll get much in the way of clarification. $\endgroup$ – Lacklub Apr 1 '16 at 12:29
6
$\begingroup$

Answer:

The room number is $12$.


Argument:

Let $x_1,\ldots,x_n$ be the positive integer numbers on the list, let $S$ be the sum of these $n$ numbers, and let $P$ be the product of these $n$ numbers; note that $S$ is the room number.

Claim 1: $S\ge13$ is impossible.

Proof: Define $k:=S-13$ with $k\ge0$. Consider the following lists :

  • The numbers $6$, $6$, and $(k+1)$-times number $1$.
  • The numbers $2$, $2$, $9$ and $k$-times number $1$.

Both lists contain $k+3$ numbers with sum $S=k+13$ and product $P=36$. Hence for such a room number $S$, the girl would have $36$ as a possible candidate for the product $P$.

  • The numbers $3$, $4$, $4$ and $(k+2)$-times number $1$.
  • The numbers $2$, $2$, $2$, $6$ and $(k+1)$--times number $1$.

Both lists contain $k+5$ numbers with sum $S=k+13$ and product $P=48$. Hence for such a room number $S$, the girl would also have $48$ as a possible candidate for the product $P$. Since the girl is able to uniquely determine the product $P$ from knowing the room number and knowing the conversation, we cannot have two possible candidates $36$ and $48$ for the product. Hence $S\ge13$ indeed is impossible, and the claim is proved.

Claim 2: $S\le11$ is impossible.

Proof: Then for every choice of $n$ and $P$, there exists at most one list of $n$ positive integers $x_1,\ldots,x_n$ with sum $S$ and product $P$. I have verified this statement by a computer program: I have generated all lists with sum $\le11$, and it turns out that no two different such lists agree simultaneously in $n$ and in $P$ and in $S$. This collides with the statement "No" that the member makes after scribbling for some time.

Claim 3: $S=12$ is possible.

Proof: Consider the following lists:

  • The numbers $3$, $4$, $4$, $1$.
  • The numbers $2$, $2$, $2$, $6$.

Both lists contain four numbers with sum $S=12$ and product $P=48$. My computer program shows that for $S=12$, these are the only two lists that simultaneously agree in $n$ and in $P$.

$\endgroup$
  • $\begingroup$ Thanks. I found the same solution, but not a proof of uniqueness. $\endgroup$ – Colonel Panic Apr 1 '16 at 14:22
  • 1
    $\begingroup$ @Gamow why 6,8,8,2 and 4,4,4,12 are not okay? do I miss something? S would be 24, and product will be the same 768 $\endgroup$ – Oray Apr 1 '16 at 14:27
  • $\begingroup$ @Oray: Yes, your example is fine for the initial piece of the conversation. But S=24 does not go along with the last statement of the girl, as there also exist other pairs of lists and other products with the same sum S=24. In other words, the room number 24 does not allow the girl to uniquely determine the product. $\endgroup$ – Gamow Apr 1 '16 at 16:21
  • $\begingroup$ @Gamow you assume both people know the club room number at the start of the dialogue? I was confused about this, because the girl says "That's obviously not enough information to determine the number of the room." $\endgroup$ – Colonel Panic Apr 1 '16 at 23:35

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.