We’re rewarding the question askers & reputations are being recalculated! Read more.

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
3
votes
1answer
98 views

The Hymns of the Lord - How Many Slates?

From Dante's Infernal Puzzle Collection: Excessive thrift, I learned, may be a sin, when love of wealth does triumph over all, and man forgets his duties to his Lord. In that dark place a preacher ...
10
votes
2answers
473 views

Turn on all squares

Take a square grid of size $a\times b$, with all squares being off. You can tap a square, to reverse the state of that square and all squares located in the same column and row as the tapped square. ...
6
votes
1answer
310 views

Maximize all weights

This question is related to What's the fewest weights you need to balance any weight from 1 to 40 pounds? You had 4 weights to balance any weight from $1$ to $40$ pounds which is answered previously ...
3
votes
2answers
321 views

Return to the Minotaur's Labyrinth

This is an extension of the puzzle The Minotaur's Labyrinth which is inspired by the comments from histocrat. You are trapped (again) in a chamber at the center of the minotaur's labyrinth. There are ...
5
votes
1answer
188 views

Cover 3*2.6 rectangle with the least number convex polygons cut from sheets of given size 1.2*2.4

I want to cover a rectangle of given dimensions ($3\times2.6$) with a minimal number of convex polygons cut from rectangular sheets of material of given size ($1.2\times2.4$). These polygons don't ...
4
votes
5answers
17k views

How can the animals get across the river without a fight breaking out?

There are three dogs and three cats that have to be transported across a river: a big dog, a medium dog and a small dog, a big cat, a medium cat, and a small cat. Rules: The raft can carry two ...
37
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 ...
2
votes
1answer
169 views

King of Captures

The player's black King (above) is about to capture the remaining opponent pieces as continuation of his move and 10 white pieces have already been captured on the same turn/move. What is the position ...
6
votes
3answers
3k views

Impossible 100 Balls Game

You are trying to make an impossible game where there are $100$ balls numbered from $1$ to $100$ and ordered in the worst case and put next to each other. The player is supposed to order the balls ...
12
votes
3answers
835 views

Day and night of the two timers

            Make a non - 24 - hour day /  night cycle       &...
9
votes
2answers
367 views

Third timer's a charm

Three motorized 24-hour light timers are arranged between a power outlet and a light bulb, with timer A parallel to a daisy chain of timers B and  C. For these timers, devise schedules that ...
2
votes
1answer
473 views

Algorithm to Solve Puzzle - Advice Needed

Given the following letters arranged in a circular pattern. A B E C D Each letter can merge with any of its opposite letters to form an adjacent ...
7
votes
3answers
806 views

Dinosaur Egg Drop v2

This question is a little different and kinda follow-up version of Dinosaur Egg Drop 1- You have 100 story building and 6 Apatosaurus dinosaur eggs. 2- You have 81 story building and 3 ...
0
votes
1answer
1k views

Packing circles in a rectangle [closed]

You have a rectangle of dimensions $l \times b$ where $l\geq b \geq 1$ and $l,b \in \mathbb R$. How many circles of diameter one unit can be fitted inside this rectangle without overlapping? (Touching ...
16
votes
4answers
943 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 ...
2
votes
1answer
135 views

How to improve “Universal dissection”?

Yesterday I've posted quite easy puzzle: Universal dissection. Now the actual problem. When we deal with 8x8 board with 1 missing cell it doesn't matter whether we allow to flip parts or not, ...
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 ...
-5
votes
3answers
192 views

How can one reliably prevent pedestrian access to a parking garage, but allow vehicular access? [closed]

Consider a typical private parking garage for a condominium or apartment building. There is currently a typical garage gate that opens and closes (slowly) to allow vehicles to pass safely through the ...
11
votes
6answers
10k views

1 Fake Coin among N Amount of coins

You are given $N$ coins which consists of only $1$ fake coin. You also have a sensitive old-fashioned Pan Balance Scale. You are asked to find the fake coin in totally 5 times weighing on the Pan ...
8
votes
3answers
390 views

Find a straight tunnel 2

You have the same plugging task as in Find a straight tunnel , but now the problem requires a bit more imagination: Bob has a field, which is a regular polygon with $N$ sides and perimeter $P$. ...
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 ...
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 ...
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 ...
-4
votes
3answers
280 views

What's In Your Pocket?

You have in your pocket a set of U.S. coins.1 Using these coins you can count out a face-value total2 of exactly $96¢$, $97¢$, $98¢$, or $99¢$, using exactly the minimum number of coins possible for ...
31
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 ...
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 ...
8
votes
2answers
362 views

16 Two Colored Line up

We have a different type of puzzle which consists of 4x4 board with numbers on it; Your task is to put numbers in the correct order as given in the diagram above. In each step, you can take one ...
9
votes
4answers
1k views

The Universe and Spaceships

It is given that there are infinite planets in the universe and every planet has exactly one spaceship on it. (Thus there are infinite spaceships too.) The distance between planets is unknown. As ...
6
votes
2answers
543 views

A Number Game for your Soul

The devil has suggested a deal to you. You play a game with him, if you win you go to heaven when you die, if you lose you go to hell. Thinking you can beat him, you take him up on the offer. Here is ...
7
votes
3answers
439 views

Minimum money needed for the worst case to guess the right number

You are going to guess a number from $0$ to $100$. If your guess is smaller, you are told and you need to pay $x$; if your guess is larger, you are told and you need to pay $y$. The game stops when ...
8
votes
1answer
424 views

A perfect metro map

You are working for a company and asked to create a perfect metro map where there will be as many stops as possible. But there are two constraints which limits the number of tracks (railroads) and ...
3
votes
4answers
262 views

Trash Bin Factory

Trash bins are to be fabricated from $4ft.$ x $8ft.$ Ga.#16 Aluminum sheets. To produce $1$ bin, it will take some cutting, bending and welding of a single Aluminum sheet. To maximize the ...
9
votes
3answers
271 views

The Flea Circuit

Starting on a square of the checkerboard, "The Flea" is trained to jump to the center of another square. Then it keeps jumping (center to center) from square to square all around the board. It is ...
4
votes
2answers
508 views

Hnefatafl - a lost Art

Hnefatafl (Ner-far-taff-all) is a Tafl Game, though it is a lost art in the modern day. The aim of the game is either to capture the king, or get the king to a corner depending on which side you are ...
-5
votes
5answers
333 views

Access Road System (Formerly Path of the Rat)

There are six towns (see map below) that needs a road system to have access with each other. What is the minimum total length of 10ft. wide road pavement that can be constructed? o---1mile---o---...
3
votes
2answers
389 views

Get the largest number using the crazy circuit board

There is a crazy circuit board with three kinds of elements which can change the signal value. All intersecting paths are connected (but paths touching by a single point are disconnected). There is ...
2
votes
2answers
144 views

Play against all other team members

Situation There are 5 teams, assume they have 10 members per team. Objective Together, the members of each team should be matched pairwise with all opponents in the minimum number of rounds. So, ...
5
votes
3answers
302 views

Minimum steps on a numberline

Given an infinite numberline, you start at zero. On every i'th move you can either move i places to the right, or i places to the left. How, in general, would you calculate the minimum number of moves ...
12
votes
3answers
2k views

Cracking a combination lock

Let's consider the humble mechanical combination lock. The basic type has $n$ dials, with $k$ digits on each dial, for a total of $k^n$ possible combinations. (Typical luggage locks or suitcase lock ...
8
votes
2answers
718 views

Lots of Gold Golden Coins and a Scale

Following my previous question: Lots of Gold Stacks and a Balance Scale You are given 10 stacks, each stack consisting of N golden 10g-coins and a digital scale with perfect precision that shows ...
2
votes
8answers
199 views

Pass the Baton competition 6 members teams

The following diagram depicts a Pass the Baton tournament (Note: due to a merge, some of the answers below use this image instead.) Each team consists of 6 members, 2 at the central point $E$, and ...
-3
votes
1answer
211 views

Shortest path to the middle [closed]

You are in the desert. You are instructed to get to the middle point between to visible marks far from you (meaning you can see them - see the direction to them - but you do not know how far are they ...
5
votes
1answer
427 views

Optimize cloth usage

A factory that manufactures clothing cuts multiple garments at once. Sometimes a number of markers are used for a job. Each marker may have a single size or multiple sizes depending on what is needed....
4
votes
1answer
332 views

Can I Haz My Eye Center'd 2?

I have noticed Can I Haz My Eye Center'd? puzzle, which I know in slightly different formulation: You have a disk on a table and a point A on it. You need to cut the disk into smallest possible ...
0
votes
2answers
271 views

How can 32 teams rotate through 8 games without overlaps? [closed]

So I have to arrange a rotation schedule for a tournament. We're aiming for 32 teams. There will be 8 stations and 4 teams competing simultaneously at each station. We want all 32 teams to hit each ...
16
votes
5answers
774 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 ...
6
votes
2answers
515 views

Create an impossible knight transformation

Some examples: Desegregate the Knights and Switch The Knights You must give two 8x8 chess board positions that have any number of black and white knights. Both boards must have the same number of ...
2
votes
2answers
638 views

Can you help me understanding the Stones game?

I am trying to understand the Stones game stated here. The stones game is a simple game, it is also a very old game which is unknown to almost everyone. The game starts with N stones and M ...
7
votes
1answer
272 views

Least amount of moves is required

You have 8x8 board and 9 identical pieces placed in a 3x3 square at the bottom left corner of the board. You are going to play a very simple game. Your task is to move these 9 pieces to the 3x3 square ...
10
votes
2answers
846 views

Euclid's orchard

Once upon a time Isaac was lounging under a tree in Euclid's apple orchard, when something struck his foresight. “In the future,” he imagined, “the layout of these trees could help ...