Questions tagged [graph-theory]
A puzzle built around graphs: sets of nodes joined together by paths. Use with [mathematics]
261 questions
1
vote
4
answers
375
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. Is it always possible to color each polygon with one of two colors so that any two polygons that share an edge are of ...
- 7,863
21
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 ...
- 6,179
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
629
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,650
7
votes
2
answers
605
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.7k
14
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 ...
- 20.9k
11
votes
2
answers
798
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.7k
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:
...
- 7,863
3
votes
1
answer
283
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
16
votes
3
answers
3k
views
Are there other LEGO Duplo track layouts with two trains that trigger all the switches indefinitely?
My daughter has a LEGO Duplo railway set that she loves to play with. Here are some basic track elements in the set (I made the figures myself): the red element is a circular arc of 30°, the green ...
- 20.9k
4
votes
3
answers
948
views
Knight’s One-Way Pawn Hunt (6x6)
Variant of this lovely puzzle
The playable version of the game
You are given an empty chessboard as in the link above as 6x6.
Place one knight anywhere you like.
Then place as many pawns as possible ...
- 34.1k
4
votes
2
answers
2k
views
You mean, I can't just put my space-filling curve anywhere I want??
In the making of this puzzle, I had to generate every possible space-filling curve for both the 5x8 grid and the 5x9 grid.
The 5x8 grid went as expected. No matter where my space-filling curve ...
- 15.5k
9
votes
2
answers
919
views
Minimum Crossed Knight Chess Tour
The Knight's Tour is a famous sequence of moves in a Chessboard.
We now search for a Knight Tour such that the number of intersections drawn by the tour is minimal.
Here is a valid Knight tour given ...
- 7,968
5
votes
1
answer
602
views
Europe Country Flags Max Forest
You are given the next map where many flags are shown on their corresponding countries.
Construct a forest of maximal weight such that:
There exist at most one edge between two flags if and only if ...
- 7,968
4
votes
3
answers
553
views
Making the connection
You have an array of fence posts sticking out of the ground. Each column has 4 posts, but the columns proceed west and east until they meet on the other side of the planet.
You need to tie the posts ...
- 24.3k
