Questions tagged [graph-theory]
A puzzle built around graphs: sets of nodes joined together by paths. Use with [mathematics]
268 questions
4
votes
2
answers
177
views
The Emperor’s Magic Trick: The Omnipotent Compass
This is a follow up question to my previous question: The Emperor’s Command: All Roads Lead to Rome, because our emperor wants more!
The Emperor was pleased that all roads led to Rome, but his thirst ...
- 36.6k
11
votes
3
answers
627
views
The Emperor’s Command: All Roads Lead to Rome
This is follow-up question to All (red and blue) roads lead to Rome
Eight cities lie in a kingdom, with Rome at the center of power.
Every morning, the Emperor shouts a sequence of colors from his ...
- 36.6k
29
votes
4
answers
1k
views
All (red and blue) roads lead to Rome
(This problem is from the 2024 Konhauser Problemfest, written by Stan Wagon.)
Eleven cities, one of them being Rome, are arranged in a circle, with adjacent cities joined by a pair of one-way roads, ...
- 2,766
5
votes
1
answer
458
views
The Plot Armor of the Galactic Engineer
The puzzle reads:
Suppose you are a galactic engineer. You are building a communication network between many distinct star systems. To prevent signal interference, every single pair of stars must be ...
- 487
19
votes
1
answer
531
views
Lost in a Desolate Hypercube
Each vertex of a $n$-dimensional hypercube is a room with a whiteboard and $n$ buttons labeled $1$ to $n$. Each vertex is labeled with a binary string from $00\cdots0$ to $11\cdots 1$($n$ digits), and ...
- 345
18
votes
3
answers
981
views
20 people where each person bears a grudge against exactly one other person in the group
Here's a problem I recently saw (not my own):
In a group of 20 people, each person bears a grudge against exactly one other person in the group. No matter how these grudges are arranged (multiple ...
- 58k
5
votes
3
answers
890
views
Prove/disprove that polygons on a sheet of paper having a common edge, can always be colored with one of two different colors.
Several straight lines drawn on a sheet of paper divide it into polygons. Each line crosses the entire sheet of paper, touching two of its edges. Is it always possible to color each polygon with one ...
- 8,703
23
votes
2
answers
1k
views
A single magical ant wandering in a vast garden of cubes
The following image depicts a small part of a vast "cube garden":
This garden started as a single 1x1x1 cube, which was grown into the complex shape you see here by performing the following ...
- 7,411
18
votes
3
answers
2k
views
How many computers can be connected at once?
Netwalk (and other names) is a puzzle game with randomly generated "networks" consisting of computers (nodes), a source node, and connectors (either a straight through pipe, a right-angled ...
- 424
7
votes
4
answers
761
views
How many trails from A to C?
Consider the following graph (3 edges between A,B; 3 edges between B,C; 2 edges between A,C).
How many trails are there that start from vertex A and end at vertex C? Two trails are considered the same ...
- 4,924
7
votes
2
answers
627
views
Memorizing Three-digit Primes
I am trying to memorize the 143 three-digit primes. It would help if I could arrange them around a circle in which any two next to each other share at least two (not necessarily different) digits. For ...
- 18.6k
15
votes
3
answers
2k
views
A tour through a city of circular roads with no sharp turns
Anita lives in a city with a peculiar road system: every road is a circle (not necessarily of the same radius). The rules of the system are simple: no sharp turns. That is, if you are at a transversal ...
- 28.6k
11
votes
2
answers
834
views
Ten Friendly Numbers
Find a set of ten positive integers such that in any subset of five of them there is at least one number with a common divisor (not necessarily the same) with all the other four, and yet, among the ...
- 18.6k
17
votes
7
answers
2k
views
Prove that there’s some citizen of the town who knows all the others.
A problem proposed by Ashay Burungale of Satara, Maharashtra, India, in the November 2008 issue of American Mathematical Monthly:
In a certain town of population 2n + 1, all relations are reciprocal:
...
- 8,703
3
votes
1
answer
297
views
Partial knight's tour with crosslinks
We have many puzzles to find complete knight's tours – including on 4D boards, irregular boards and nonplanar boards – but few puzzles to find partial tours where only some cells are visited. I ...
- 10.5k