Learn by Doing Puzzle 5: Matchsticks and Numbers

The Task

You have a set of matchsticks. One day, you decide that you want to create numbers out of them! You can create the digits 0 to 9 like so:

 _       _   _       _       _   _   _
| |  |   _|  _| |_| |_   |_   | |_| |_|
|_|  |  |_   _|   |  _|  |_|  | |_|   |
                

Using all of your matchsticks, write an algorithm that calculates the largest number and smallest number that you can make.

Start by solving this for low number of matchsticks (from 2 up to 25), then build up to 10000 matchsticks. Remember, none can be left over, and you cannot make any other symbol than the 10 digits above.

Once you've done that, you ponder... what's the smallest number you can make without leading zeroes for a given number of matchsticks?

During the solution session, values will be provided for 10, 25, 100, 1000 and 10,000 matchsticks, though your algorithms should be able to handle an arbitrary number of matchsticks.

Example: 10 Matchsticks

You must use all of your matchsticks for any solution you arrive at. If you have 10 matchsticks, and must use them all, you could build the numbers (not an exhaustive list):

• 40 (4 and 6 matchsticks)
• 56 (5 and 5 matchsticks)
• 101 (2, 6 and 2 matchsticks)

However, you cannot create the number 81, because that requires 9 matchsticks (7 and 1) with one left over. You can't create 0 on its own either, because four matchsticks remain.

Check your solutions

Once you've come up with a solution, you can check your solutions below. Enter:

• which calculation type you are checking;
• how many matchsticks you are simulating; and,
• the digits you've created with your leading zeroes.

The calculator below will tell you whether you are correct or not, but it will not give you the answer if you are wrong.