Questions tagged [optimization]

A puzzle where you have to optimize a certain objective function (maximize profit, minimize cost). There should ideally be a provable best answer, to avoid making the puzzle into an [open-ended] game.

Filter by
Sorted by
Tagged with
129 votes
5 answers
142k views

Is this duplo train track under too much tension?

My kids were making this train track of duplo the other day, and this is what they put together. They are still very young, and for them, this is something big. They were really proud that they ...
Lezzup's user avatar
  • 5,066
118 votes
3 answers
12k views

Prove that π > 3

It seems that once upon a time some politicians tried to pass a law fixing the value of π to be exactly 3. The idea being to "make math simpler so that our children can get better at math". ...
Florian F's user avatar
  • 29.8k
85 votes
16 answers
208k 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 ...
user avatar
58 votes
8 answers
6k 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 ...
klm123's user avatar
  • 16.2k
51 votes
6 answers
5k 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 ...
Thomas Blue's user avatar
  • 6,962
45 votes
17 answers
9k 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 ...
Martin Frank's user avatar
44 votes
8 answers
7k views

How many Chess Pieces are needed to control every square on the board? No Piece Restriction

You may use as many pieces as you like. Pieces do not control the square they occupy. Accepted Answer goes to the person that has the least score. Piece cost: Pawn - 1 Knight - 3 Bishop - 3 Rook - ...
warspyking's user avatar
  • 14.5k
41 votes
7 answers
6k 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 ...
boboquack's user avatar
  • 22k
40 votes
11 answers
5k 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 ...
ghosts_in_the_code's user avatar
40 votes
6 answers
2k views

Packing pentominoes in a circle

You want to prepare a pizza of 12 flavors. You have 12 oddly-shaped pieces of cheese that you decide to use for the pizza. The shapes happen to be ... Oh, well, forget it! This isn't going to be ...
Florian F's user avatar
  • 29.8k
38 votes
4 answers
3k views

Pythagorean pentagons

To follow up on the theme of so called "pythagorean" dissections, here is one more for you to chew on. I hope you don't get bored. The pentagons above have sides respectively 3, 4 and 5. ...
Florian F's user avatar
  • 29.8k
38 votes
8 answers
4k views

The Bee Lover's Hotel

Dr Bees likes bees. Dr Bees is not his real name, but that is what everybody calls him. I should actually say that he is obsessed with bees. Bees are his whole life. He knows everything about them. ...
Florian F's user avatar
  • 29.8k
35 votes
5 answers
3k views

A Queen and her Pawns

Place a queen and as many pawns as possible on a chessboard so that the queen has just one way of capturing all the pawns in precisely as many moves as there are pawns. Pawns do not move and do not ...
Bernardo Recamán Santos's user avatar
34 votes
8 answers
6k 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 ...
Neil's user avatar
  • 2,116
33 votes
6 answers
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 ...
Chaotic's user avatar
  • 1,605
33 votes
3 answers
5k views

What is the largest n-way tie possible for Mario Kart?

In a $12$ player race, the scoring system of Mario Kart awards $15$ points for 1st place, $12$ for 2nd, then $13-x$ for $3\leq x\leq 12$. A standard cup is $4$ races. What is the largest $n$ such that ...
ApexPolenta's user avatar
  • 2,690
33 votes
5 answers
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 ...
Untitpoi's user avatar
  • 2,700
32 votes
5 answers
5k views

How can 3 queens control the white squares?

It is well known that there is no way of arranging 4 queens on a checker board in such a way that every square is occupied or threatened. Now consider a slight variation where we only need to cover ...
Paul Panzer's user avatar
  • 10.3k
32 votes
6 answers
6k 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 ...
Rand al'Thor's user avatar
32 votes
3 answers
5k views

How many squares can 4 queens control?

Though there is no strict mathematical proof, it has been shown via brute-force that no arrangement of 4 or fewer queens can control every square on a standard 8x8 chessboard. So, out of the 64 ...
Unsigned's user avatar
  • 471
31 votes
3 answers
1k views

Rook River (Chess Sliding Puzzle)

The absent-minded king has gotten himself lost. Help him return to his palace on h8 using as few moves as possible. Only legal chess moves are allowed. Pawns are not promoted on the final rank. You ...
DyingIsFun's user avatar
  • 9,176
31 votes
5 answers
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 ...
klm123's user avatar
  • 16.2k
31 votes
4 answers
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 ...
BmyGuest's user avatar
  • 18.1k
30 votes
10 answers
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 ...
Johannes's user avatar
  • 4,392
28 votes
7 answers
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 ...
user avatar
28 votes
4 answers
4k views

1000 gold coins to share with the king

You are the knight of a great kingdom in an unknown world. Your king sent you to a dungeon and you killed the dragon and got 1000 gold coins from the dragon’s lair. Normally, you are supposed to give ...
Oray's user avatar
  • 30.3k
28 votes
3 answers
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 ...
Oray's user avatar
  • 30.3k
27 votes
6 answers
5k views

Checkmate 30 kings with rooks

Using only kings, and as few rooks as possible, set up a position where 30 of black's kings are checkmated. Checkmate: The king is in check The king has no moves out of check Black only has kings, ...
SE - stop firing the good guys's user avatar
27 votes
4 answers
4k views

A COVID-19 puzzle: How large a class do you need to fit 30 pupils?

Some countries are proposing to reopen high schools soon. To ensure safety, they want to make sure that all pupils in a class are at least 2 m apart. To help them find the smallest room that can ...
Simd's user avatar
  • 7,845
27 votes
2 answers
3k 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. (...
BmyGuest's user avatar
  • 18.1k
27 votes
0 answers
2k views

Is there a move-efficient way to rotate the center pieces on the Octo-Star?

I'm looking for a more efficient algorithm to rotate the center column of the Octo-Star puzzle 45 degrees. The situation below occurs when four properly-oriented edges are next to each other, ...
user avatar
26 votes
7 answers
2k views

Approximate pi out of small numbers

Given the numbers 1, 2, ..., n the puzzle is to try to make a number as close as possible to pi using only the four mathematical operations +, -, *, / and parentheses (brackets). You don't have to use ...
Simd's user avatar
  • 7,845
26 votes
4 answers
1k 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 ...
Arcanist Lupus's user avatar
25 votes
5 answers
2k views

Colouring a rug

I have a rectangular rug in my living room composed of coloured patches (shown below). For convenience I have labelled each distinct colour from 1 to 6. Let's suppose that it was created by starting ...
Dmitry Kamenetsky's user avatar
25 votes
3 answers
4k views

Rock climbing at the Tokyo Olympics

The idea for this puzzle came from my friend Jan. The puzzle is based on real world events from the Tokyo Olympics. The Olympic rock climbing preliminary round has 20 climbers. Each climber competes ...
Dmitry Kamenetsky's user avatar
24 votes
7 answers
3k views

What is the minimum number of helpers that an explorer need to cross the desert?

There is a desert which can be crossed only by walking and this takes six days. The explorers of the desert can carry at most four days' water and food. If they want, they can take helpers with them. ...
F Nishat's user avatar
  • 517
24 votes
6 answers
3k views

Chess solitaire: The King's longest walk

Challenge: maximize the number of moves white needs for its king to reach a square of your choosing, adhering to the following rules: Black does not move. Like normal: The king may not be in a ...
Retudin's user avatar
  • 8,601
24 votes
7 answers
3k views

From Puzzling to StackExchange

This is a variation of a game I used to play with my friends in my childhood. You are given a starting word, and using the following operations, you have to reach the target word. The solution that ...
CodeNewbie's user avatar
  • 11.8k
24 votes
2 answers
1k views

Hexominos from pentominos, heptominos from hexominos

All twelve pentominoes can be obtained by attaching a single unit square (edge to edge) to one of the squares that make up one (or more) of the following four tetrominoes: a) What is the least number ...
Bernardo Recamán Santos's user avatar
24 votes
2 answers
4k views

What if I told you that guessing in Sudoku is very bad and might give you a bad karma?

Yesterday, I tried to solve a regular Sudoku puzzle. Of course, the Sudoku puzzle had a unique solution. But, I was feeling a little lazy, so, rather than solve the puzzle properly, I made guesses! At ...
athin's user avatar
  • 34.2k
24 votes
7 answers
1k views

Fit the most chess pieces on a board with these rules

Fit the most pieces on a chess board. You are only allowed to place Rooks, Knights and Bishops. The number of rooks, knights and bishops must be approximately equal (specifically, the number of rooks,...
Tweakimp's user avatar
  • 1,820
24 votes
1 answer
1k views

Peaceful Encampments

This math puzzle is due to Donald Knuth (as far as I know; maybe he got it from someone else) circa 2014. Consider a plain represented by the unit square. On this plain we want to “peacefully encamp” ...
Quuxplusone's user avatar
  • 1,846
23 votes
7 answers
3k views

You are at a crossroads with five roads leading away from it

To allow new users to solve this puzzle and earn reputation points, I encourage all users whose reputation is 200 or more to not post an answer until 48 hours after this question is posted. Thank you! ...
Will Octagon Gibson's user avatar
23 votes
5 answers
2k views

Numerical Boggle

You are probably familiar with the word game Boggle, where you need to construct words by concatenating letters from a grid. Here we will play a numerical version of the game. The rules are as follows:...
Dmitry Kamenetsky's user avatar
23 votes
3 answers
797 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 ...
f'''s user avatar
  • 33.7k
22 votes
7 answers
5k views

Can you irrigate your lawn with 23 sprinklers?

You have a perfectly circular lawn with radius exactly 4 metres. Lately the grass has been turning yellow and quite rough, so you go to Stiv's Diabolical Instruments and describe your problem. "...
Parcly Taxel's user avatar
  • 7,678
22 votes
7 answers
3k views

Two prisoners and twenty marbles

Two prisoners are planning their escape. Their cells are locked with a padlock that must be opened with a 5-digit code (numbers 00000 to 99999). Each prisoner knows the code of the other prisoner's ...
Dmitry Kamenetsky's user avatar
22 votes
7 answers
4k 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 ...
Aaron P's user avatar
  • 533
22 votes
2 answers
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 ...
Jon.G's user avatar
  • 1,498
22 votes
3 answers
2k views

Dividing a piece of land

Alice and Bob try to divide a piece of land $D$, shaped in a perfect closed disk of radius 1. Alice moves first to mark some finite (at least one) number of points in $D$. Bob then draws any number of ...
Eric's user avatar
  • 6,498

1
2 3 4 5
17