Questions tagged [graph-theory]
A puzzle built around graphs: sets of nodes joined together by paths. Use with [mathematics]
200
questions
3
votes
2
answers
273
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. ...
- 25.8k
6
votes
4
answers
277
views
Cover an n times n grid with non-diagonal non-intersecting n-1 shortest paths
This puzzle was given to me by PhD student colleagues. Suppose that you have a $n\times n$ grid. Is it possible, for a given $n$ to cover all its $n^2$ nodes with $n-1$ non-diagonal and non-...
- 5,557
5
votes
2
answers
197
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 ...
- 14.5k
-1
votes
1
answer
138
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,691
2
votes
2
answers
225
views
Planar Investigator
Use logical deduction to place a different digit from 1 to 9 in each circle below so that 8 of the arrows form the primes 23, 31, 41, 53, 59, 79, 89, and 97. (We view an arrow starting at digit A and ...
- 14.5k
3
votes
4
answers
257
views
Travel in the USA
If you decide to travel from state to state in US in alphabetical order how many states can you cover if:
The state you are in must share a border with the previous state. The
last state in your list ...
- 38.8k
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 ...
7
votes
1
answer
1k
views
Can you stop the falling piano with 23 nets?
MIT's Baker House has a tradition of dropping an irrepairable piano six floors every Drop Day, the last day one can drop a class without penalty (the 2022 date is 19 April). This year, in order to ...
- 3,681
8
votes
1
answer
200
views
A Knight's Tour
A lonely chess knight stands on a cell somewhere in the first row of a 3x13 board, and elsewhere there is a castle.
The knight takes a tour of all the remaining 37 cells of the board, missing just the ...
- 14.5k
8
votes
1
answer
286
views
Be Paired or Be Square
8 white and 8 black dots are drawn on a piece of paper. Parcly and Tori take turns drawing edges, always between white and black dots not already adjacent (so the graph is always bipartite); the first ...
- 3,681
2
votes
1
answer
244
views
Prove the existence of a triangle such that all of its sides are of the same color [closed]
Seventeen points have been picked in a plane, and each pair of points has been connected by a line segment of one of three colors: red, yellow, or green. Prove that there are three points which are ...
- 1,465
3
votes
1
answer
403
views
Genies' chess on a 10×10 board
The work of Hearth Taxel revealed some other results related to genies' chess. For example, there is an arrangement $A$ of pawns on a 10×10 board such that no 3×3 submatrix is empty and
$A$ is ...
- 3,681
13
votes
1
answer
1k
views
Cracking the Cryptic Logo
The well-known Cracking The Cryptic YouTube channel has a logo consisting of 12 circles joined by 16 straight lines running horizontally, vertically or diagonally.
What is the significance of this ...
- 6,569
4
votes
2
answers
316
views
The Divisibility Graph... Again!
The divisibility graph of a set of positive integers is the graph whose vertices are the integers, two of which are joined by an edge if one divides the other.
What is the smallest positive integer ...
- 14.5k
7
votes
2
answers
540
views
Divisibility Graph
The divisibility graph of a set of integers is the graph whose vertices are the integers, two of which are joined by an edge if one divides the other.
What is the largest integer N such that the ...
- 14.5k
3
votes
1
answer
758
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
188
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 ...
- 14.5k
7
votes
2
answers
416
views
Another Rook's Tour of the Chessboard
Place numbers 1 to 64 in the cells of this 8 x 8 board in such a way that consecutive numbers occupy neighboring cells (either vertically or horizontally). Shaded cells must be occupied by prime ...
- 14.5k
22
votes
3
answers
1k
views
Knight tour on a racetrack
Help the chess knight complete four clockwise laps on this racetrack, so that he lands on every square and never lands on the same square twice! The final square the knight lands on will be the same ...
- 31.4k
-4
votes
1
answer
148
views
Show that every finite directed acyclic graph has at least one source vertex [closed]
Easy puzzle courtesy of a paper I'm reading rn:
Show that every finite directed acyclic graph has at least one source vertex. That is, a vertex such that all the directed edges incident to it are ...
- 1,465
7
votes
1
answer
292
views
Existence of index-uniform Hashi puzzles
On the left, we have a starting configuration for a game of Hashi, and on the right, its solution:
That is to say, the goal is to make connections (planar, and traveling only in cardinal directions) ...
- 1,768
2
votes
1
answer
269
views
Trees from integers [closed]
A set of distinct positive integers is said to be a prime tree of integers if the graph obtained by letting the integers be its vertices, two of which are joined by an edge if (and only if) their sum ...
- 14.5k
-2
votes
1
answer
148
views
Trails on a grid filled with skinny tetrominoes
Let's have a 10x10 grid with 12 empty bases. The rest of the grid is filled with skinny tetrominoes. The 5 regular tetrominoes are marked with a red color and the 2 reflections are marked with a green ...
- 2,779
7
votes
2
answers
1k
views
Coloring positive integers 'black or white'
Each of the positive integers from 1 to n is colored either black or white.
You can repeatedly choose a number m and recolor m together with those numbers, which are not coprime to m. At the beginning ...
- 11.5k
2
votes
1
answer
121
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 ...
- 1,962
0
votes
1
answer
76
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 ...
- 1,962
2
votes
3
answers
198
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 ...
- 1,962
8
votes
3
answers
362
views
Toroidal Pipes Puzzle: T's and Bulbs Only
A continuation in the Pipes puzzle series.
Problem statement for math nerds: Let $G(N)$ denote the graph consisting of cardinally adjacently linked lattice points on an $N \times N$ toroidal grid. For ...
- 1,768
2
votes
1
answer
105
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 ...
- 1,962
2
votes
1
answer
88
views
Fetching Alchemist IV
This is the fourth puzzle in the Fetching Alchemist series, and is another puzzle that is exclusive to Puzzling SE until solved.
This one might be a little too easy for those of you who have already ...
- 1,962
4
votes
1
answer
126
views
Fetching Alchemist III
This is the third puzzle in the Fetching Alchemist series, and I am experimenting with a new format here. This time, I won't tell you in advance what the perfect score is. The first guess may be ...
- 1,962
3
votes
1
answer
125
views
Fetching Alchemist II
This is a puzzle from the Expert section of my game Fetching Alchemist, visually modified for presentation here. It is a variant of the Travelling Salesman problem where you are trying to complete a ...
- 1,962
2
votes
1
answer
164
views
Fetching Alchemist I
This is a puzzle from the Expert section of my game Fetching Alchemist, visually modified for presentation here. It is a variant of the Travelling Salesman problem where you are trying to complete a ...
- 1,962
0
votes
1
answer
119
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,779
3
votes
2
answers
230
views
Pirates dividing booty around a circular table
A group of pirates have plundered one of his majesty's cargo ships and they all carried as much gold coins as each one could find. When they get back to their ship, they sit at a round table and pass ...
- 283
2
votes
0
answers
73
views
Fair and square island hopping [duplicate]
If amateur fiction is not your thing skip to the bottom.
As IP (Implausible Physics) expert for DREAM, the Department for Reckless Engineering and Advanced Megalomania you have been tasked by sheikh ...
- 2,961
1
vote
2
answers
255
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 ...
- 25.8k
0
votes
1
answer
148
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 ...
- 25.8k
13
votes
7
answers
884
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 ...
- 10.6k
0
votes
1
answer
108
views
Gaby's 21 students sitting around a circle [closed]
Gaby numbers her 21 students with the primes between 11 and 97. She now asks them to sit around a circle making sure that any two of them sitting next to each other have either their tens or units ...
- 14.5k
3
votes
1
answer
167
views
My sixteen graph theory students
I will have sixteen students in my graph theory course this semester. In our first session I asked each of them with which of the other 15 students in the class they were already acquainted before the ...
- 14.5k
3
votes
0
answers
215
views
Infected Cylinder and Torus
A variant of the well known Infected Checkerboard problem. If we've a 𝑛x𝑛 square, then we fold it along top and bottom row to form a cylinder. A cell in this cylinder becomes infected if at least ...
user73244
1
vote
1
answer
98
views
Painting a plane!
Paint the points on a plane with three colors, so that the points on each line are a maximum of 2 colors, and all three colors are used. (Math Festival 1990)
4
votes
1
answer
177
views
Visiting streets, not houses
The section points are houses and lines are streets, all with one unit length. What is the fewest number of units you must travel to visit every street at least once?
- 742
22
votes
1
answer
623
views
New Year Graph Puzzle
In the graph below, each node is coloured either red or yellow, except for the white node in the bottom left, which I've marked with an X.
Can you tell me what the white node marked with X represents?...
- 124k
-1
votes
2
answers
89
views
Show that no lines need cross [closed]
There are n red points and n blue points in the plane. Show that you can always join all the red and blue points with straight lines so that no two lines cross. Each point can have exactly one line ...
- 5,298
14
votes
1
answer
439
views
Currency connections
Two Forex traders are trying to communicate about their trades.
They send each other images with a hidden meaning like this one:
Can you work out which currencies they are trading?
Hint:
- 373
8
votes
2
answers
887
views
Frog game on a dandelion graph
There is some noise in the local pond. A group of frogs wants to host a birthday party!
There is a total of 22 lily pads in the pond, each housing a single frog. They are labelled as numbers from 0 to ...
- 2,788
9
votes
2
answers
527
views
Dragon summoning spell
The parchment shown below got stained with something. See if you can determine the obscured parts.
- 10k
7
votes
1
answer
202
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 ...
- 3,016