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 ...
- 14.6k
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 ...
- 224
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
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 ...
- 14.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
-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 ...
- 14.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 ...
- 28.1k
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, ...
- 1
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....
- 10.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 ...
- 468
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 ...
- 555
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 ...
- 14.3k
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 ...
- 423