Seemingly Trivial Problems
There are many problems, which seem to be trivial
at first sight, but nevertheless a very hard to
solve. Below a list of such seemingly trivial problems
is given, roughly going from hard to easy:
- Biggest object you can carry upstairs:
Given the dimensions of a building, which
is the biggest object that can be moved from the
entrance to each of the rooms? Or to any of the
- Driving around a field:
If you are driving a car, there is a smallest circle
you can make. Lets assume that you have a field
with a certain border, and that there is free space
to drive around it. What is the shortest
route to drive around this field? Or, which is the
route with the smallest included area?
- Balls inside a box:
Given a certain box, how many balls of a certain size
can be put in this box?
- The historicity of Jesus Christ:
To give a reliable, unbaised indication of the
historicity of Jesus Christ.
- Keeping your wallet light:
Which strategy should you follow to keep the weight
of the coins in your wallet at light as possible over
time? (Of course, without using a credit card or
other kind of plastic money all the time.)
- Shortest robe around a bundle of tubes:
What is the shortest line you can draw around a given
set of circles, when the the circles are not allowed
- Finding a good parking place in a one-way parking place:
A good parking place, is a place that is close to
where you need to be. In a one-way parking place you have
a risk of having to drive round another time when you
wait too long for picking a parking place while coming
closer to where you need to be. What is a good
algorithm if you can only look a few parking lots ahead?
- Finding shortest route on a half empty parking lot:
If you know where your car is, find the shortest route
at the end of the shopping day, when the parking lot is
about half empty. And what if you can only look a limited
- Solving clickomania puzzles:
Find the best solution for a
(proven to be NP-complete for sufficient colors and size.)
- Generate solvable clickomania puzzles:
Generate clickomania puzzles which can be played without leaving
any sqaures left.
- Perfect Tetris strategy:
Assume that you have always sufficient time, does there
exist a playing strategy, such that you can play indefinitely.
(The answer is no.)
- The cutting sticks problem:
finding a proof for the cutting stick problem.
- Symmetrical Langton Ant's:
Proving why certain Langton Ants produce patterns which
result in symmetrical states over and over again.
(Has been proven in 1995.)
- Squares inside rectangles:
Proving that there exist no rectangle which exactly can be
filled with squares from 1 to n, for some n.
- Julia set of the Califlower fractal.
- Domino puzzle with the highest number of solutions:
What is the domino puzzle (36 numbers placed in a square grid
to be tiled with domino stones) that has the highest number of differten solutions
- Counting Hamilton cycles in product graphs.
- Smallest circle enclosing a collection of points:
Given a collection of points, find the smallest circle enclosing
all of them. (Suggested by Razvan Tigaeru.)
- Covering grid points by a circle:
If you have a sheet with a square grid, what is the
maximum number of grid points that can be covered
with a circle of a certain radius, and where should
the center be put?
- Dividing numbers in two equal groups:
Given a set of natural numbers can it be divide into two
groups such that the two groups sum up to the same value.
If the total sum of the numbers is odd, this is obviously
not possible. (This seems rather simple for small sets of
numbers, but let's say how about a set of a million different
- Perform a vote:
The U.S.A. presidential elections of 2000 have proven that
this is far from trivial.
- Point in a triangle:
Decide if a given point lies inside a certain triangle or not,
using finite precision numbers. Especially for points very close
to the edges and the corners this is far from easy. (The problem
is in the rounding errors, and how to avoid them.)
- Cheapest way to order dinner at a fastfood restaurant:
At fast food restaurants you can order separate items or
meals, which are combinations of certain items, but usually
for a lower price than the items separately. If you have
to order many items, which is the cheapest combination of
meals and separate items? What if you also have a limitted
number of vouchers available? (This indeed is not such a
hard problem, but again, it does when numbers become larger.)