# 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 rooms?

• 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.

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 to overlap.

• 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 distance away?

• Solving clickomania puzzles:
Find the best solution for a clickomania puzzle. (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 different 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 numbers.)

• Perform a vote:
The U.S.A. presidential elections of 2000 have proven that this is far from trivial. Final report.

• 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.)

Home | Puzzles