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
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
937 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
134 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
189 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 ...
10
votes
6answers
9k 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
378 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
278 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 ...
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 ...
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
361 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
530 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
435 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
417 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
261 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
270 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
476 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
330 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
373 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
143 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
715 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
191 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
210 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
418 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
330 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
265 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
771 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
509 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
610 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
268 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
836 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 ...
-3
votes
4answers
572 views

Variation of 1000 bottles of wine puzzle

So I came up with a variation of the famous problem https://www.reddit.com/r/math/comments/3o0mfi/a_king_1000_bottles_of_wine_10_prisoners_and_a/ There are n ...
8
votes
3answers
540 views

Halve time with two timers

Two motorized 24-hour light timers are daisy chained between a power outlet and a light bulb. For these timers, devise schedules and choose initial times that produce the following repeated lighting ...
7
votes
3answers
737 views

Odd hours with two timers

Two motorized 24-hour light timers are daisy chained between a power outlet and a light bulb. For these timers, devise schedules and choose initial times that produce the following repeated 9-hour ...
9
votes
3answers
660 views

What is the 'best' way to tilt through a D20?

A regular D20 die (icosahedron) as depicted above has the number 1 to 20 arranged on its faces such that the sum of opposing faces is 21. Each triangular face touches three other faces directly by a ...
9
votes
3answers
3k views

$n$ couples crossing a river

There are $n$ couples on one side of the river. Nobody is on the other side. They have a boat that accommodates up to 2 people. For every trip across, someone(s) must bring the boat back as well. The ...
11
votes
5answers
2k views

Sorting cards using max 3 stacks

You have a stack of N cards numbered from 1 to N in random order. You want to sort the cards in ascending order using the following procedure: Your initial stack is stack 1. You distribute the cards ...
2
votes
2answers
3k views

The case of the 4 campers and the rickety bridge! [duplicate]

Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough battery left for seventeen minutes. The bridge ...
6
votes
1answer
973 views

Frying Three Steaks

You invite your friend to the dinner. so you would like to prepare 3 fried steaks but you do not have much time to cook. You are trying to figure out how to cook all steaks perfectly (fried and ...
11
votes
6answers
750 views

Lots of Gold Stacks and a Balance Scale

You are given X amount of stacks of golden coins, each stack consisting of ten (10) golden coins and a digital balance scale with perfect precision that shows how much difference between weights you ...
7
votes
3answers
563 views

What is the minimum number of steps to solve this cloning particles on chessboard puzzle?

I'm creating a puzzle based on the idea from this numberphile video: pebbling a chessboard. You can see a working (yet unfinished) version here. I would like to give the user a feedback of how well ...
5
votes
2answers
880 views

Largest cages Killer Sudoku

Task 1: Find the maximum value of $n$ for which it is possible to create a regular uniquely-solvable Killer Sudoku (9x9) such that every cage has atleast $n$ cells in it. Rules for killer sudoku ...
2
votes
3answers
379 views

Optimal path around a variable-position wall [closed]

This is a harder version of the fixed wall variation. Every day you walk across a flat plane from a point $A$ to a point $B$. The points are $3$ miles apart. However, every day there is a 50% ...
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 ...