8
$\begingroup$

There is a pile of $n$ items. Every time you divide a pile into two piles, you get a score being the product of the number of items in the two piles. Show that the sum of your scores at the end is always $\binom{n}{2}$.

My question: What are some (preferably well-known) books/articles that discuss or at least mention this puzzle? Is there a name to the puzzle? I guess it's quite famous, and as I want to mention it in an article, I would like to cite it properly instead of just saying that it is "a famous puzzle". Searching Google for "pile product score" doesn't yield useful results.

Improve this question
$\endgroup$
2
  • 6
    $\begingroup$ Why have I never heard of this! By the way, if your score for breaking $n = a + (n-a)$ is not $a(n-a)$ but $a(n-a)(n-2)$, your total is again constant, $2{n\choose 3}$. Any total scoring function $f(n)$ with $f(1)=0$ gives such a game, but the associated scoring functions $f(n) - f(a) - f(n-a)$ don't seem to look so nice, usually. $\endgroup$
    – Allen Knutson
    Commented Jan 10, 2015 at 23:04
  • $\begingroup$ The puzzle allows a continuous variant (by exhaustion) that may be interesting for pedagogical purposes. "Start with a segment on length $L$. Every time you cut an interval into two intervals, you get a score equal to the product of their lengths. Show that the total score can approach, but never reach, the value $L^2/2$." $\endgroup$
    – Pietro Majer
    Commented Aug 18, 2021 at 7:18

3 Answers 3

Reset to default
6
$\begingroup$

This entry on Cut the Knot gives a proof and the reference to the book Exploring Mathematics with Your Computer by A. Engel. I am not sure if the puzzle was invented by Engel, but hopefully the book will have an earlier reference if that's not the case (unfortunately I do not have access to the book at the moment).

Improve this answer
$\endgroup$
5
$\begingroup$

(Long comment) I’d rephrase the puzzle this way. There is a Go board with some stones disposed on a full isosceles right-angled triangle. You remove a maximal rectangle from the configuration, then again from what is left, and so on. Show that when you have taken all the stones from the board, there is no stone left on it.

Improve this answer
$\endgroup$
5
  • $\begingroup$ A somehow trivialising description $\endgroup$
    – Pietro Majer
    Commented Aug 17, 2021 at 14:24
  • 1
    $\begingroup$ "rectangular triangle" meaning right-angled triangle, I presume. $\endgroup$
    – Gerry Myerson
    Commented Aug 17, 2021 at 23:47
  • 1
    $\begingroup$ Thankyou Gerry :) $\endgroup$
    – Pietro Majer
    Commented Aug 18, 2021 at 0:39
  • $\begingroup$ "When you have taken all the stones from the board, there is no stone left on it" sounds like a tautology to me. $\endgroup$
    – Richard Stanley
    Commented Aug 18, 2021 at 20:00
  • $\begingroup$ Yes, the final tautology was a kind of joke to suggest that in the above picture the explanation is completely obvious indeed. $\endgroup$
    – Pietro Majer
    Commented Aug 19, 2021 at 5:20
2
$\begingroup$

A name that has been published for this puzzle is pile splitting. Bill Marion wrote about it as an example of strong induction in a discrete mathematics pedagogy collection I edited. He presented three other versions, given below, and referenced a James Tanton article with many more. Also, he mentioned that the puzzle is included in Rosen's textbook.

  • Bill Marion, Pile Splitting Problem: Introducing Strong Induction, in Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules, and Articles, MAA Notes #74, ed. Hopkins, Mathematical Association of America, 2009, 7-10.
  • James Tanton, A Dozen Questions About: Pile Splitting, Math Horizons 12 (2004) 28-31.

Here are the other versions from Bill's article. Write $n = r+s$ for the split (and require $r, s \ne 0$). See also Allen Knutson's comment.

  • Take the sum of all scores $rs(r+s)$.
  • Take the product of all scores $\frac{1}{r} + \frac{1}{s}$.
  • Take the product of all scores $\binom{r+s}{r}$.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .