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
6 votes
2 answers
734 views

Make a square table top with the minimal needed amount of straight cuts

inspired by : Make a square table top with six (or fewer) pieces A carpenter has three pieces of beautiful wood, measuring 12 inches, 15 inches, and 16 inches square, respectively. They want to use ...
Retudin's user avatar
  • 8,601
4 votes
1 answer
218 views

Dishonest dungeon staff

You are faced with the difficult task to set up a dungeon for adventurers. However you made a deal with the guild: any adventurer brave enough to beat the dungeon and reach the treasure room will be ...
Fluorine's user avatar
10 votes
2 answers
438 views

Make a square table top with six (or fewer) pieces

A man had three pieces of beautiful wood, measuring 12 inches, 15 inches, and 16 inches square respectively. He wanted to cut these into the fewest pieces possible that would fit together and form a ...
Will Octagon Gibson's user avatar
18 votes
3 answers
1k views

Winning chance in coins game with fixing

A player plays the following solitaire game. The game consists of as many rounds as are needed to produce a result. They have 20 fair coins, which may in any round be live or fixed; each coin starts ...
Rosie F's user avatar
  • 8,631
5 votes
1 answer
293 views

Number operation problem - find minimum number of operations

On the blackboard, there are nine numbers from 1 to 9. In each operation, two of the numbers are chosen, erased, and replaced with their sum and difference. If two identical numbers appear on the ...
Vincent's user avatar
  • 53
6 votes
5 answers
633 views

Circles crossing every cell of an NxN grid

What is the least number of circles you need to draw, such that every cell of an NxN grid is crossed? A circle crosses a grid cell if one of the points on its circumference lies completely inside the ...
Dmitry Kamenetsky's user avatar
13 votes
3 answers
2k views

Circles crossing every cell of an 8x8 grid

What is the least number of circles you need to draw, such that every cell of an 8x8 grid is crossed? A circle crosses a grid cell if one of the points on its circumference lies completely inside the ...
Dmitry Kamenetsky's user avatar
6 votes
4 answers
863 views

Flip counters in a grid so that they alternate in color

Beginner puzzle This puzzle is intended to be suitable for people who are new to puzzle solving. Clarification: Both experienced solvers and new solvers are welcome to post solutions to this puzzle. ...
Will Octagon Gibson's user avatar
9 votes
1 answer
448 views

Tile a square as small as possible using two different sizes of square tiles

There are two types of square tiles. One type has a side length of 1 cm and the other has a side length of 2 cm. What is the smallest square that can be made with equal numbers of each type of tile? ...
Will Octagon Gibson's user avatar
16 votes
4 answers
929 views

Make the three products equal and as large as possible

Beginner puzzle This puzzle is intended to be suitable for people who are new to puzzle solving. Clarification: Both experienced solvers and new solvers are welcome to post solutions to this puzzle. ...
Will Octagon Gibson's user avatar
4 votes
1 answer
433 views

75 integers are squared or cubed: minimum distinct results? [closed]

75 different integer numbers are written on a blackboard. Each is erased and replaced with either its square or its cube, the operation being random for each. What is the minimum quantity of different ...
Alexander's user avatar
  • 595
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
5 votes
6 answers
1k views

Minimum number of questions for real treasure

There are 2000 treasures, among which only one is real and the others are fake. There are also 2000 knights, among whom one always tells the truth while the others always lie. You can ask the knights ...
Emma's user avatar
  • 69
4 votes
1 answer
179 views

Approximate ln(2) out of small numbers

Given numbers 1,2,...n, the goal of this puzzle is to make a number as close to the mathematical constant $\ln(2) ≈ 0.69314718055$ as possible. Rules You can only use the four mathematical ...
CrSb0001's user avatar
  • 2,241
13 votes
5 answers
2k views

General attacking chessboard squares

This is a general version of this beautiful puzzle. Place any number of standard chess pieces on a 8x8 chessboard, such that there is at least 1 empty square attacked by exactly 1 piece, at least 1 ...
Dmitry Kamenetsky's user avatar
13 votes
7 answers
2k views

Fewest number of prisoners needed

You are an assistant to the king, who has scheduled a party tomorrow. There are 1000 wine bottles in the king's possession, and unfortunately, 3 of them are poisonous. Consuming from any of these ...
Durgesh Patel's user avatar
11 votes
3 answers
600 views

New record for minimally clued 5x5 Hidato

CrSb0001 has been studying the minimum number of clues to force a unique solution in Hidato for variously sized boards. They came up with a 5x5 Hidato with 5 clues but it was found that it has ...
Bubbler's user avatar
  • 13.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
13 votes
3 answers
1k views

What is the minimum amount of numbers needed to create a 4x4 Hidato with a unique solution?

Goal of Hidato: Fill in a grid with a series of consecutive numbers that connect each other horizontally, vertically, or diagonally. So I have been working on figuring out the minimum number of ...
CrSb0001's user avatar
  • 2,241
1 vote
1 answer
175 views

How long will it take for the horse to be captured?

Source: https://open.kattis.com/problems/ambush Problem: When Farmer Oskar doesn’t watch his cows closely enough, they tend to wander off into the forest to hunt for horse spies. To catch an enemy ...
user88178's user avatar
  • 103
19 votes
1 answer
1k views

An Amazing Configuration

Ed Pegg found in December 2019 this amazing configuration consisting of 22 points in 28 lines of 4. On those points place 22 different positive integers such that the sum of any of the four points in ...
Bernardo Recamán Santos's user avatar
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
1 vote
1 answer
192 views

Maximum filled days

I have two types of items, $i_1$ and $i_2$. $i_1$ items can be used at most $50$ times and $i_2$ items can be used at most $120$ times. I have $7000$ items $i_1$ and $800$ items $i_2$. Each item $i\in ...
JKHA's user avatar
  • 6,033
12 votes
1 answer
2k views

Add rules to Minesweeper until you can start with nothing

Think of classic Minesweeper game, with the following list of restrictions on the placement of mines: C (Connected): All mines are connected via 8-way neighborhood (orthogonal and diagonal). Q (Quad):...
Bubbler's user avatar
  • 13.8k
5 votes
1 answer
948 views

Anna and Boris play the Red Blue game

Anna and Boris play a game on a 9x9 chessboard. Anna goes first and turns alternate thereafter. In each move, Anna puts a red counter on a vacant square while Boris puts a blue counter on a vacant ...
Will Octagon Gibson's user avatar
4 votes
3 answers
1k views

Two 10-letter words consisting of 20 unique letters?

I'm looking for two words, 10 letters each, 20 unique letters. Below are my by-hand attempts. https://www.wordunscrambler.net/word-list/10-letter-words-with-no-repeating-letters Find words with 3 or ...
user87072's user avatar
9 votes
3 answers
886 views

Minimum number of flips needed to fully set a binary string

Source: My school teacher, it was just given as a problem statement. Problem: You are given a binary sequence $S$ of up to $10^6$ bits. You wish to set all the bits in the string to $1$, but the catch ...
user88178's user avatar
  • 103
9 votes
1 answer
311 views

Designing a four-pan scale

You are an ancient merchant, and you need to weigh out many different items of many different weights. To do so, you'll design a scale to weigh objects. Unlike a standard scale, your scale will have ...
isaacg's user avatar
  • 6,944
0 votes
1 answer
382 views

Rooks covering Dark Squares on a Chessboard

How many rooks are required such that all dark squares on the chessboard are covered by at least one rook.
Sunny Lu's user avatar
  • 2,854
11 votes
1 answer
565 views

List Roman numerals to minimize total distance

This is based on a discussion with @mousetail. List the numbers from 1-100 in Roman numerals in the order that minimizes the total sum of the Levenshtein distances between consecutive numbers.
Simd's user avatar
  • 7,845
6 votes
2 answers
190 views

River crossing cats and dogs

A farmer and his $n$ cats and $m$ dogs are on one side of a river. There is a boat that can carry the farmer and at most $k$ animals at once. The boat doesn't move without a person operating it. The ...
Bubbler's user avatar
  • 13.8k
15 votes
2 answers
2k views

Maximum number of pieces on a board

Suppose we have a 3x3 board. On this board, several squares are empty and several squares are filled with pieces. A legal move on the board is made using the same idea as taking in checkers: one piece ...
Ocelot's user avatar
  • 153
12 votes
2 answers
638 views

Arithmetic-progression-free sequences

This question Sudokus with no 3-term arithmetic progressions within made me wonder about the following question. What is the longest sequence composed of the integers 1..N (or 0..N-1 if you have a ...
Florian F's user avatar
  • 29.8k
3 votes
2 answers
359 views

Approximate e out of small numbers

Given the numbers 1, 2, ..., n the puzzle is to try to make a number as close as possible to the mathematical constant $e$ using only the four mathematical operations +, -, *, / and parentheses (...
Simd's user avatar
  • 7,845
6 votes
1 answer
324 views

Sudokus with no 3-term arithmetic progressions within

A complete (or solved) sudoku is said to be 3-term arithmetic progression free (3-AP free) if none of its rows or columns contain three terms which are in arithmetic progression (i. e. in none of its ...
Bernardo Recamán Santos's user avatar
3 votes
2 answers
256 views

Longest word where each prefix is another word

What is the longest English word, e.g. “someword” where “s”, “so”, “som”… “someword” are all also valid English words? The longest such word I could come up with is 6 letters: Can you do better?
Peter Pepper's user avatar
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
3 votes
2 answers
328 views

Find maximum circular array sum [closed]

Take this 10 by 10 grid of numbers. ...
Simd's user avatar
  • 7,845
3 votes
1 answer
365 views

Longest cycle on a cube

What is the length of the longest straight path on the surface of a unit cube, such that it starts and ends at the same point? The path can cross itself and must be straight on every edge and face ...
Dmitry Kamenetsky's user avatar
5 votes
1 answer
238 views

Decent Knights - Chess

In Naughty knights it’s asked to prove that it’s impossible to fit more than 32 knights such that no knight attacking other. Can you find the minimum number of knights, filling the table in a way that ...
ulutku's user avatar
  • 151
6 votes
2 answers
338 views

While 2024 arrives

There are about $9.266 \times 10^{45}$ partitions of 2024, a handful! To each of these partitions corresponds a graph in which the vertices are each of the parts, two of which are joined by an edge if ...
Bernardo Recamán Santos's user avatar
18 votes
3 answers
3k views

Naughty knights

Recently the British newspaper The Guardian published the following puzzle, titled Naughty Knights: And here's the solution published by the newspaper later: Unfortunately, this solution doesn't ...
Mitsuko's user avatar
  • 2,035
5 votes
1 answer
183 views

Find the optimal partition in this matrix

Given a particular matrix of integers, the challenge is to draw a boundary line through the cells so that the sum of the numbers on the boundary line or above is as large as possible. In this case &...
Simd's user avatar
  • 7,845
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
6 votes
3 answers
534 views

Find the optimal dividing line

Consider the following grid of numbers: In machine readable form: ...
Simd's user avatar
  • 7,845
0 votes
1 answer
121 views

Chess with gravity #2: Keys, Locks, and Lava

Previous Puzzle If you're having trouble understanding the key/lock thing, watch this until 9:30 which might be a better explanation of what I'm trying to say General Rules: In this puzzle, you ...
CrSb0001's user avatar
  • 2,241
6 votes
1 answer
348 views

Add as few plus signs as possible to make equation true

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
1 vote
2 answers
2k views

Chess, but with gravity? #1

Based off of this puzzle and this Youtube video Rules: You control the pieces labeled kn (knight), b (bishop), and ...
CrSb0001's user avatar
  • 2,241
6 votes
1 answer
593 views

Minimum number of swaps

This puzzle is related to this math question. Consider $4$ lists of integers: $(0,0,0,0,0,0,0,0)$, $(1,1,1,1,1,1,1,1)$, $(2,2,2,2,2,2,2,2)$, $(2,2,2,2,2,2,2,2)$ where order does not matter. We want to ...
Fabius Wiesner's user avatar
18 votes
3 answers
947 views

PSE Advent Calendar 2023 (Day 8): A Quilt for Santa

This puzzle is part of the Puzzling Stack Exchange Advent Calendar 2023. The accepted answer to this question will be awarded a bounty worth 50 reputation.< Previous Door Next Door > Mrs. Claus ...
Aaron Windsor's user avatar

1
2 3 4 5
17