MatMod logo

All Posts

In this blog, I will add a new post all 3-5 days. Each post contains a complete (optimization) problem, many of them are puzzles. Each problem consists of a comprehensive description of the problem, a description of the modeling (translation from spoken language to mathematical language), a mathematical formulation, an implementation in the LPL modeling language, and a link to solve the problem directly through the Internet. A full document is also downloadable as a PDF.

I start with easy puzzle problems, but later on, more complicated problems will be presented. Enjoy!

The Witch Puzzle I (witches)

This puzzle is an interesting pastime. Print out the 3×3 puzzle squares shown in Figure 1 on a color printer. Cut out the nine squares to place the 9 pieces on the table. The puzzle is simple: Arrange the pieces into a 3×3 square in such a way that the pieces matches up so that each “puz” front is matched up with the corresponding “zle” horizontally and vertically with the next piece. Good luck! Depending on the puzzle and how they are arranged, it’s quite a challenge. Great for a rainy day if your “Stop the Rain” spell doesn’t work! This puzzle is known as the “witch puzzle” because the pieces of some commercial games contain bitmaps of colored witches.

Read more

Pack Umbrellas (umbrella)

A number n of “umbrellas” (⊤) (2-dimensional spanned “umbrellas”) is given. Their heights can be modified arbitrarily. The problem is to push these umbrellas together as closely as possible such that the total span is as minimal as possible. A small example with four umbrellas is given in Figure 1 with their widths 6, 8, 11, and 22. The idea of this model is from Ivo Blöchliger.

Read more

A Two Persons Game (gameh)

Two players play the following number game: Each chooses (secretly) a positive number. The numbers are then uncovered at the same time and compared. If the numbers are equal, neither of the players will get a payoff. If the numbers differ by one, then the player who has chosen the higher number obtains the sum of both, otherwise the player with the smaller number obtains the smaller of both. The play is repeated endlessly. Which number and how often should a player choose a number in each round? (The game has been described in [1].)

Read more

Golomb Ruler (golomb)

A Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is the length of the ruler. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. A Golomb ruler of a given order with minimal length is called a optimal Golomb ruler.

Read more

Wolf-Goat-Cabbage (alcuin)

“A man had to take a wolf, a goat and a bunch of cabbages across the river. The only boat he could find can only take the man and of them at a time. But he had been ordered to transfer all of these to the other side in good condition. How could this be done?”

Read more

Maximizing Vitality (cells)

This one-dimensional cellular automaton consists of n (here n = 20) cells arranged in a horizontal line with the leftmost being cell 0. Each cell i has two neighbors: a left one l(i) and a right one r(i). The left neighbor of cell 0 is cell n- 1, and the right neighbor of cell n- 1 is cell 0.

Read more

Earthlings (earthling)

August 2020. The spaceship landed. “Earth!” they shouted. They knew that earthlings are divided into three groups: those who always tell the truth, those who always lie, and those who do both, alternating between true and false statements, starting with either. “Let’s go!” said the captain. The aliens approached three earthlings, who each were from a different group, and asked, “Who won the last World Cup? Who came in second? Who came in third?” One of them responded, “Zaire first. Uruguay second. Spain third.” Another one said, “Zaire first. Spain second. Uruguay third.” The third one said, “Uruguay first. Spain second. Zaire third.” The aliens returned to their spaceship and flew back to where they came from. Do you know which response was the true ranking in the World Cup? (see [2] and [1]).

Read more