Questions tagged [optimization]

A mathematical puzzle where you have to optimize a certain objective function (maximize profit, minimize cost).

Filter by
Sorted by
Tagged with
57
votes
10answers
43k views

A camel transporting bananas

A somewhat well-known puzzle is described as such: You have a pile of 3,000 bananas. You wish to transport them to a place 1,000 miles away on the back of a camel; however, the camel can only carry ...
53
votes
8answers
5k views

Find a straight tunnel

There is a circular area with radius 1 km. And there is a tunnel, which is just under the surface, but invisible - unless you dig. It is known that the tunnel goes under the area (at least touches it ...
47
votes
6answers
4k views

Eight coins for the fair king

You are responsible for creating new types of coins for the court. King respects the forgetful: he wants you to create 8 coins of different value, no more. King respects the feeble: he wants that any ...
42
votes
17answers
8k views

A blanket for my baby snake

Mama snake wants to knit a blanket for little baby snake. She is not a dissipater and wants to make the blanket of a minimal size (area). But her baby snake is quite a lively baby and it always ...
40
votes
7answers
5k views

Amnesiac in a ring shaped palace

Related: Turn off all lights in a ring-shaped palace Your boss has trapped you inside a ring-shaped palace, and all you know about the palace is that there are some number* of identical rooms, each ...
35
votes
11answers
4k views

Sudoku net that is always solvable

A sudoku net is a 9x9 grid where every cell is either (blank) or has a cross (block). A random solved sudoku is chosen. The net is placed on top of the sudoku (in any of the 4 ways). We can only see ...
31
votes
6answers
5k views

Will a greedy algorithm solve Tatham's Flood?

I was just investigating some of the puzzles on Simon Tatham's website, and came across Flood, in which we start with an $n\times n$ grid of cells each of which is filled with one of $k$ predetermined ...
30
votes
7answers
5k views

Dinosaur egg drop

Archeologists discover two dinosaur eggs, and you are given the chance to test the durability of these eggs (bad move on their part). Suppose that these eggs will absorb a specific amount of force ...
30
votes
5answers
3k views

Biggest army on a chessboard

Reminder: Everybody knows that we can place 8 queens in a chessboard without threatening each other (see here). Same reasoning can be applied for knights, bishops, rooks and kings. Giving ...
30
votes
5answers
6k views

Two spies throwing stones into a river

There is a puzzle about two spies: Two spies must pass each other two secret numbers (one number per spy), unnoticed by their enemies. They have agreed on a method for doing this using only 26 ...
30
votes
3answers
3k views

Cross-road optimization - what is the proper way to solve this type of puzzle?

This puzzle has 3 levels of increasing complexity. Each "level" is separate and complete, so feel free to post partial solutions to the individual levels only. I'm most interested in the principal ...
29
votes
6answers
3k views

Swapping rooks in a 4x4 board

You have a 4x4 chessboard with four black rooks on the top and four white rooks in the bottom. Your goal is to swap these rooks using the minimum number of steps. It does not matter which rook is ...
28
votes
3answers
3k views

12 Birds in the petshop

You decided to buy 2 birds from a pet shop and went to a pet shop for it. There are 12 budgerigars at the pet shop and you want a male and a female for your home. You cannot distinguish the gender of ...
27
votes
10answers
3k views

One prize, infinitely many choices

Having reached the final stage of a game show, you face an endless row of doors labelled $1$, $2$, $3$, ... The game show host has selected a whole dollar amount, and has put this exact amount as a ...
26
votes
6answers
5k views

A Special Parking Lot

There is a special kind of parking lot that stores special 1x1 cars that only can move to adjacent squares not including diagonals if they are empty (provided no car occupies the square). Every car ...
24
votes
2answers
2k views

The tilted labyrinth - Can you find the fastest path in this 3D-puzzle? (Simulator now included.)

This is a puzzle was inspired by the board game labyrinth, which I very much enjoyed as a kid. It either requires very good 3D-visualization skills in your brain or some paper & scissors work. (...
23
votes
3answers
977 views

How much money can we make?

My five friends and I used to loan each other money all the time. But over the past several years we have moved apart. We don't trust PayPal, banks, or the postal service so transferring money over ...
21
votes
7answers
2k views

How much water do you need to cross the desert?

This question is inspired by Terry Pratchett's "Small Gods," in which an army crosses a vast desert by making multiple trips and caching water along the way. 1. Provide an answer. 2. I doubt I'm the ...
20
votes
2answers
2k views

A thirsty king and his knights

The black king has spent his life fighting over this strange checkered land, the white king has finally been defeated and his troops have surrendered and pledged allegiance to him. Now he's not sure ...
20
votes
3answers
672 views

Concentrating tokens on an infinite board

One token is placed on each square of an infinite checkerboard. One square is marked with an X. You want to get as many tokens on the marked square as possible. To do this, you may make any finite ...
19
votes
6answers
3k views

Trapped in my Cellar

I have taken Doorknob hostage in my cellar. He is "perfectly" trapped - solid walls, solid floor, solid roof, no windows, etc. The only way out is a steel door and the only way to unlock the door is ...
19
votes
5answers
610 views

Square Spin #1: Sun and Moon

Defining Square Spin Lets play a game! The aim of this game is to transform one image into another using the least amount of moves possible. Here is what a move consists of: ...
19
votes
4answers
2k views

How many boxes are conductors?

The Question (Some knowledge of potential difference, resistor combinations, etc. required) You have 1000 boxes. Some (or none) of them are conductors (of negligible resistance). The rest are ...
19
votes
5answers
1k views

Island of Knights, Knaves and Spies

There is an island with $N$ inhabitants (for example $A_1, A_2, \dots, A_N$), each of them is either a knight, a knave, or a spy. As usual: knights will always tell the truth upon answering a ...
18
votes
3answers
3k views

Knights and jokers

There are $N$ men. $K$ of them are knights, $M$ of them are jokers. $N$ is known, $K$ and $M$ are unknown. You know that: $K + M = N$, $K \gt M$, $M \ge 1$, $N$ is odd. Knights always tell ...
18
votes
8answers
2k views

30 fake coins out of 99 coins

You are given 99 coins which consists of 30 fake ones. You also have a digital balance scale with perfect precision that shows how much difference between weighs you put on. For example, if you put 10 ...
17
votes
2answers
885 views

numbers want to cross a river, but their sum must be a square number

In the world of numbers, numbers 1 to 9 want to cross a river, They have a boat which can take 1 to 3 numbers, But sum of the numbers must be a square number. The boat can not sail back itself, so ...
16
votes
7answers
2k views

Soldiers in the Parade Ground

Twenty-five soldiers are standing in a parade ground consisting of a five-by-five grid of large concrete slabs, laid out in a neat north-to-south, east-to-west square array. Each soldier is standing ...
16
votes
4answers
936 views

Universal dissection

Alice has a squared paper 8 by 8. She cuts out one 1x1 square from it, at row N, column M. Bob cuts the rest of the paper into pieces. Once he is done, Alice asks Bob to put the pieces together in a ...
16
votes
8answers
2k views

Rigged casino that prevents pairs

This question is still active as the answer from @Sleafar has just arrived. Not yet solved. Scenario The heads of 3 top terrorist organisations are planning to play an extremely high-stake poker ...
16
votes
5answers
770 views

Maximize the number of paths

You have exactly 990 edges. Assemble them into a simple undirected graph with two distinguished vertices A and B, such that the number of different simple paths from A to B is as large as you can make ...
16
votes
3answers
2k views

Bulls without cows: how many steps are needed to solve this?

I'm bad at this sort of minimum-solve problems so I'm asking for you, proud riddle solvers! There's this huge hangar with 72 different airplanes. They come in six different colors Each color has ...
15
votes
3answers
1k views

6 Water Glasses Upside Down

There are 6 water glasses as shown in the picture below: You need to turn all of them upside down with the rules below: You have to choose any 5 of them at every turn. Chosen ones need to be turned ...
15
votes
2answers
786 views

Santa Claus flies to the South Pole

It is a little known fact that Santa Claus is in fact a vampire. Why else would he spend so much time near the North Pole and travel only at night? Yes, he fears daylight! His problem is that ...
14
votes
4answers
2k views

Leveling up and Getting Items!

You are playing an online RPG game with 9 friends of yours (10 people in total) and in the game, there is a 2-player dungeon where you level up every time you enter and complete it. Only up to two ...
14
votes
1answer
442 views

Keeping a ball lost forever

Suppose you can make a rectangular maze, where each cell (apart from the bottom-right) can contain an arrow in one of the four directions (up, down, left or right) of your choosing, except for those ...
14
votes
5answers
2k views

Three riders, two horses

We have three riders which need to travel some distance (say, 13.5km) through a rough terrain (no running, no skiing etc., only walking or horse trot), but they have only two horses. The speed of a ...
14
votes
2answers
1k views

How many clues are required to ensure Einstein's Puzzle is solvable?

I used to play Einstein's puzzles a lot when I was younger, and very quickly learned to assess quite rapidly whether I thought a puzzle would be a quick solve or more time-consuming, but I never ...
14
votes
2answers
786 views

Flood on the top floor

There has been a water incident on the top floor of a building, and one apartment has suffered some water damage. As in, a lot of water damage. The entire apartment is filled waist deep with ...
13
votes
3answers
2k views

99 coins into the sacks

You have 99 coins that you need to place into any number of sacks. After doing so, you write on each one the number of sacks that are lighter than that sack. For example, if you put 98 coins into one ...
13
votes
4answers
3k views

A dice game, what is the optimal strategy?

Alice was walking on the street when she came across a man playing with a die. She could not help trying to check if the die was loaded and while she was concluding that it wasn't loaded, the man ...
13
votes
1answer
398 views

Inequality with strange equality conditions

Question: For positive real numbers $a,b,c$ and $d$, find the smallest possible value of the following expression: $$\large{\left \lfloor{\frac{b+c+d}{a}} \right \rfloor+ \left \lfloor{\frac{a+c+d}{...
13
votes
1answer
397 views

Candy Button Paper

An entry in Fortnightly Topic Challenge #35: Restricted Title 1. Title based on this xkcd. Your biggest dream has come true: you have an infinite supply of your favorite five-flavor candy button ...
13
votes
3answers
794 views

Searching for a secret door

You have reached the final stage of a game show, and now face an endless row of doors labelled $\ldots,-3,-2,-1,0,1, 2, 3,\ldots$, going from minus infinity to plus infinity. Your goal is to detect a ...
13
votes
1answer
466 views

Hiding Cat Puzzle on a Grid

The Youtube channel MindYourDecisions posted a video about the "Hiding Cat Puzzle". In the puzzle, you have a line of five boxes, one of which contains a cat. You don't know where the cat is, and your ...
12
votes
5answers
767 views

More than equilibrium

Assume you have 2 identical metal cubes, the only difference being their temperatures $T_1 = 0 \, \text{°C}$, $T_2 = 100 \, \text{°C}$: The task is now to transfer as much heat as possible to the ...
12
votes
4answers
1k views

Get 6 pawns in file A or H

This is somehow inspired by my other chess related question: Possible pawn combinations How can you get 6 pawns (white or black) on a chessboard on the files A or H using legal moves? Start with a ...
12
votes
2answers
4k views

Connect four towers by roads

Four guard towers are situated in a square formation of side length 1km. A general wants to build roads to connect the towers so that one can walk from any tower to any tower along the roads, possibly ...
12
votes
3answers
2k views

Removing 100 digits from the first 100 numbers

Write the first 100 positive integers next to each other to form one big number: $$123456789101112131415161718192021\dots90919293949596979899100.$$ If we remove 100 digits (not necessarily consecutive)...
12
votes
4answers
497 views

Red and White Squares

There are two grid boards with the dimension of 9x9 and 14x14, consist of all white squares. You are supposed to color some squares with a red color on the conditions below: In a board, if two square ...