All Questions
Tagged with optimization graph-theory
30
questions
8
votes
3
answers
1k
views
Largest sequence of adjacent numbers less than 11 such that adjacent number divides the other
Friday writes different positive whole numbers that are all less than 11 next to each other in the sand. Robinson Crusoe looks at the sequence and notices with amusement that adjacent numbers are ...
- 3,323
6
votes
2
answers
349
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 ...
- 19.3k
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 ...
- 19.3k
3
votes
1
answer
444
views
Largest word tree
I was inspired by this awesome puzzle. Here is an image of a word tree borrowed from there:
In a word tree every path from the root to the leaves must form a distinct word. The size of the tree is ...
- 36.3k
18
votes
7
answers
1k
views
Efficient Mowing at PSE
Your task:
Find the most efficient mowing path around the dark green bushes that mows (passes over) all of the grass (light green).
For those who cannot view the image above, there are 9 rows of 16, ...
- 19k
5
votes
2
answers
247
views
Robot painting a $K_5$
A robot starts at a node of a fully connected graph of 5 nodes (shown below). Each turn the robot can move across an edge and paint it in one of two colours - blue for odd turns and red for even turns....
- 36.3k
3
votes
2
answers
2k
views
The longest path of edges on a 3x3 grid
A robot is placed on some vertex of a 3x3 grid. At each move the robot can take one step (up, down, left or right) along the edge of the grid to the adjacent vertex, but it cannot go outside the grid. ...
- 36.3k
6
votes
2
answers
814
views
Splitting the integers 1 to 36
Split the integers 1 to 36 into two sets, A and B, such that any number in set A has a common divisor greater than 1 with no more than two other numbers in A, but for every number in B there are at ...
- 19.3k
-1
votes
1
answer
224
views
How to arrange the colored cells in game grid?
Puzzle: In a game grid some cells are missing. Each line has only one colored cell with a label (a number greater than zero). This is an example grid and the number of columns/rows can be less than ...
- 1,701
12
votes
3
answers
2k
views
Longest infinite loop of 5 states
This is based on a question I posed in The Nineteenth Byte:
What group of 5 states have the longest total name, under the constraint that you must be able to travel from one state to another in the ...
3
votes
1
answer
951
views
Most efficient way for people along the edges of a grid to move to the center
I'm considering a $2k\times 2k$ square grid ($k\in\mathbb Z^+$) with $8k$ highly rational people standing along the vertices forming the perimeter. All of these people want to go to the centre of the ...
- 309
2
votes
2
answers
218
views
Powerful Octagon
Place different integers on the vertices of an octagon so that the sum of the integers in any two vertices joined by one of its edges is a power of 2. Do so in such a way that the largest integer used ...
- 19.3k
2
votes
1
answer
132
views
Fetching Alchemist, Excavation I
This is a puzzle in the Fetching Alchemist series. It has been generated especially for Puzzling Stack Exchange.
Please note that, in my opinion, imperfect solutions should be up-voted so long as they ...
- 2,042
0
votes
1
answer
83
views
Fetching Alchemist, Grand Potion I
This is a puzzle in the Fetching Alchemist series.
There's no selling in this puzzle, just one potion to brew, but with a lot of ingredients.
Please note that, in my opinion, imperfect solutions ...
- 2,042
2
votes
3
answers
201
views
Advanced Fetching Alchemist II
This is a puzzle in the Fetching Alchemist series. From now on, you complete quests at the place you start at as well.
Please note that, in my opinion, imperfect solutions should be up-voted so long ...
- 2,042
2
votes
1
answer
113
views
Advanced Fetching Alchemist I
This follows the same rules as previous Fetching Alchemist puzzles, except you choose where you start, and you may now return to your starting place after leaving it.
How to Play
You are looking for ...
- 2,042
0
votes
1
answer
144
views
Trail passing through squares of a grid
Let's construct a 10x10 grid. 0n the 100 squares you are allowed to place 7 bases (the red dots in the diagram below) in any square on the grid. Then you fill the grid with skinny trominoes. The ...
- 2,915
1
vote
2
answers
279
views
Minimize the longest King chain on a 6x6 ternary grid
This puzzle is an extension of this one: Minimize the longest King chain on a 5x5 binary board
Given a grid filled with numbers, we define a King chain to be a path on the grid such that:
The path ...
- 36.3k
0
votes
1
answer
178
views
Minimize the longest King chain on a 7x7 binary grid
This puzzle is an extension of this one: Minimize the longest King chain on a 5x5 binary board
Given a grid filled with numbers, we define a King chain to be a path on the grid such that:
The path ...
- 36.3k
13
votes
7
answers
980
views
Minimize the longest King chain on a 5x5 binary board
Given a grid filled with numbers, let's define a King chain to be a path on the grid such that
the path can be traversed with chess King's moves (moving to one of 8 adjacent cells at a time),
the ...
- 16.3k
8
votes
1
answer
339
views
Four color a map - but go light on the fourth color!
Here's a map, which I found here:
Your challenge is to four-color this map while minimizing your use of the fourth color.
More specifically, color the map with four colors so each region is a ...
- 7,158
8
votes
3
answers
405
views
What is the minimum count of steps required to complete this dominoes maze?
Here's a map:
How to play
Legend:
(◾) = Start point
★ = Objective
⚑ = End point
Mission: ...
- 964
6
votes
7
answers
329
views
Find minimum number of meeting periods to reach 2 degrees of separation for a group [closed]
I am running a training course and I want to arrange a set of 1:1 meeting periods between the participants such that at the end of the day there is a maximum of 2 degrees of separation between any of ...
- 69
2
votes
2
answers
377
views
Scheduling Meetings
I came across this problem in real life and thought it could be made into an interesting puzzle. I will enjoy seeing how my eventual solution could be improved!
Here's the situation.
There ...
- 23.7k
3
votes
1
answer
485
views
8 Train Stations
You are going to build $8$ train stations and the railroads with it in an area. But you are asked to build these stations and their railroads in a very efficient way where there has to be the least ...
- 30.4k
8
votes
1
answer
469
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 ...
- 30.4k
18
votes
5
answers
1k
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 ...
10
votes
1
answer
665
views
Building a cheap road
The governor of Reniets (a land far, far away!) is known to be very stingy.
He has to build a road which connects all the five cities in the region, which are oddly arranged on the vertices of a ...
- 12.6k
10
votes
5
answers
966
views
Houses in a grid
You are a city planner tasked with the placement of unit-square-sized houses in a rectangular-grid allotment, the size of which is up to you but must be as small as possible to save money. The number ...
- 526
12
votes
3
answers
1k
views
Dissecting a square
You are asked to dissect an $N \times N$ square into polyomino pieces such that each piece shares a portion of its boundary with exactly $D$ other pieces, and no piece has area exceeding $N$. This can ...
- 4,400