9846

Picking Up Coins in a Grid

In this puzzle, we have a rectangular board of cells, with some cells having a coin (the red disks in the plot). A robot is initially in the lower-left cell of the board. The task of the robot is to pick up as many coins as possible and carry them to the upper-right cell. However, at each step the robot can only move either one cell right or one cell up. Each time the robot visits a cell with a coin, it picks up that coin. The blue line shows an optimal tour, that is, a tour that allows the robot to pick up the maximum number of coins.
To solve the puzzle by yourself, hide the optimal path and the maximum number of coins that can be picked up.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

This is puzzle number 62 in [1]. As in the book, the optimal path is found here by using dynamic programming. Let the centers of the cells be at points , , . The robot starts at and ends at . Let be 1 if there is a coin at and 0 otherwise. Let be the largest number of coins the robot can pick up and bring to . The task is to maximize .
The robot can reach the point either from below—that is, from —or from the left, . The largest number of coins that can be brought to these points are and , respectively. Thus, the largest number of coins the robot can bring to is the maximum of these two numbers plus . So, , , , . In addition, , , , and , .
After we have coded these formulas, we simply ask for the value of and we know the maximum number of coins that can be picked up! Mathematica does all the recursive calculations for us. To get the optimal path, we also write down from where it is optimal to come to each . Note that often the optimal path is not unique.
For more about dynamic programming with Mathematica, see Section 23.5.2 in [2].
References
[1] A. Levitin and M. Levitin, Algorithmic Puzzles, New York: Oxford University Press, 2011.
[2] H. Ruskeepää, Mathematica Navigator: Mathematics, Statistics, and Graphics, 3rd ed., San Diego: Elsevier Academic Press, 2009.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+