I am making a puzzle based on a Project Euler problem. Here is the puzzle at present:
What path in the triangle below, starting from the top number with each step moving to one adjacent number in the next row, gives the greatest possible sum?
35
12 80
88 79 96
73 56 20 55
The intended solution to this problem is to, in the second-last row, draw an arrow from the greater of the two to the bottom. Then replace the number with the sum of those numbers, as follows:
35
12 80
161 135 151
↗ ↗ ↖
73 56 20 55
When this process is repeated until the top row, it will give the best path. In this case, 35 to 80 to 96 to 55 is the best path.
I feel that this puzzle is too easy, however. There are only so many paths and it's very easy to see which ones couldn't possibly be best. It's definitely possible to solve this without finding the "correct" solution. The obvious solution is to add more rows, but adding too many would require a lot of arithmetic. Already 6 additions must be performed to solve the puzzle, and puzzles get boring if there are too many additions. Five rows would require 10 additions and six rows would require 15.
Should I keep the puzzle at four rows, or increase its size? Is there general advice as to how large a puzzle should be?
Answer
Determining an "appropriate size" for a puzzle is all about determining what constraints you consider "appropriate", and then finding a puzzle that fits those constraints.
In your case, you are given a pyramid with $n$ levels, designed in such a way that the dynamic programming approach to the problem requires $\binom{n}{2}$ additions, but there are $2^n$ possible paths in total.
You can make a table of values for this:
$$\begin{matrix} n & \binom{n}{2} & 2^n\\ 4 & 6 & 16 \\ 5 & 10 & 32 \\ 6 & 15 & 64 \\ 7 & 21 & 128 \\ \end{matrix}$$
I personally feel that doing about 10 or 15 additions shouldn't be a problem, so you could get away with a six-row pyramid. However, you seem to feel that this is too much.
Sometimes, the bounds you provide mean that there are no appropriate sizes for the puzzle because they don't require you to see the trick behind it. It just means that that type of puzzle is probably off-limits to your audience.
No comments:
Post a Comment