Questions tagged [graph-theory]
A puzzle built around graphs: sets of nodes joined together by paths.
145
questions
2
votes
1answer
165 views
A robot moving on a grid
In the spirit the question I propose the puzzle:
A robot is placed on a vertex of a grid. At each move the robot must take three steps along the edge of the grid. After each step the robot must turn ...
5
votes
2answers
338 views
Seventeen positive integers
Find 17 positive integers such that no four of them have, pairwise, a common divisor greater than 1, but, likewise, no four of them are, pairwise, relatively prime.
Do so in such a way that the ...
5
votes
1answer
91 views
The sandpiles on the beach
We call a convex polyhedron a sandpile if one of the faces, called base, has a common edge with all the other faces. Furthermore, each vertex is linked with three edges. We consider the sandpiles by ...
1
vote
2answers
161 views
LGBT+ SpeedDating
Congratulations!
You are now the lucky franchise owner of 'SpeedDating Inc'.
We are the number one organiser of speed-dating events in WhereverYouAre.
We would love for you to start organizing new ...
6
votes
2answers
189 views
Phone pattern security
My phone is unlocked using a security pattern. This is a path drawn through a 3x3 grid of dots with the following rules:
The path can start at any dot
The path visits neighbouring dots: horizontally,...
8
votes
2answers
167 views
Intersecting shapes on a flat surface
What is the maximum number of enclosed regions that you can create by drawing two circles and two triangles on a flat surface? Try answering with mathematical arguments.
10
votes
4answers
791 views
Draw this planar graph
The playing board for this puzzle is a short list of digits; there is one rule governing possible moves: The 1 may swap with a digit one place to the right; the <...
11
votes
1answer
301 views
Gaby´s Puzzle (Primes Around a Circle)
To keep them busy during lockdown, Gaby asked her children to find a way to place the first sixteen primes (2 to 53) around a circle so that either the sum or difference (or both) of any two of them ...
2
votes
1answer
54 views
What's the graph relation? #4
What's the relation that joins the nodes?
Previous
What's the graph relation? #1
What's the graph relation? #2
What's the graph relation? #3
4
votes
1answer
170 views
What's the graph relation? #3
What's the relation that joins the nodes?
Previous
What's the graph relation? #1
What's the graph relation? #2
6
votes
2answers
383 views
Primes in a Line
Place the first 20 primes (2 to 71) in a line so that the sum or difference (or both) of any two primes that find themselves next to each other is always a perfect square.
For which other values of N ...
3
votes
2answers
201 views
How many ways to draw the figure without lifting pencil? [duplicate]
The rules are very simple ...
Star at A, end at A.
From one point you can to go to the other point by only one line (no turning at cross roads).
No going over any line more than once.
find the ...
7
votes
3answers
262 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: ...
3
votes
1answer
103 views
Sing me the song of days gone by, sing me the song that made me cry
Sing me the song of days gone by,
sing me the song that made me cry.
The remorse, regret, and pain I'm in,
reflects the memories of what has been.
Hint 1
6
votes
1answer
207 views
What's the graph relation? #2
What's the relation that joins the nodes? Open the image in a new tab if you'd like to see the diagram with better resolution.
Previous
What's the graph relation? #1
Hint 1
4
votes
1answer
98 views
3
votes
1answer
78 views
Name that node #2
What is the value of the unknown node?
Previous
Name that node #1 (Beginner's Level Puzzle)
5
votes
1answer
75 views
Name that node #1 (Beginner's Level Puzzle)
While Puzzling.SE has some extremely clever and difficult puzzles that are being solved by people whose intellect amazes me, I wanted to make some graph puzzles that were specifically meant for ...
2
votes
2answers
115 views
A complex matter of relations (What am I?)
There is many-a-kind of number,
which sometimes makes me feel dumber.
Let's say that we start from zero to four,
and see if that leads us to learn some more.
Some numbers you might see as a ...
1
vote
1answer
64 views
A simple matter of relations (What am I?)
Don't overthink it,
just a little fun.
Relations are part of graphs,
of which I am one.
What is my relation?
Hint 1
4
votes
1answer
104 views
Which node(s) does 0 connect with in this simple graph?
If we add 0 as a node to the graph below, which node(s) will it connect to?
Hint 0
Hint 1
Hint 2
0
votes
1answer
241 views
What's the number in the last node of this directed graph?
Hint 1
Hint 2
Hint 3
Background on puzzle (Spoiler Alert)
3
votes
1answer
188 views
I'm singing a song, can you follow along?
What song am I singing?
I apologize for the resolution. If you open the image itself in a new tab you can magnify to get a better look at the words.
11
votes
1answer
429 views
Which node(s) does 16 connect with in this simple graph?
If we add 16 as a node to the graph below, which node(s) will it connect to?
Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
16
votes
1answer
1k views
What node does 11 point to?
If we included 11 in the diagram below, which node would it connect to?
Hint 1
7
votes
1answer
222 views
Largest set of independent hexominoes
What is the largest set of hexominoes that can be found in which no two of them are such that one can be converted into the other by cutting out one of its component squares (thus obtaining a ...
5
votes
1answer
510 views
Find how many colors are needed to color all vertices
In this puzzle you need to identify the minimum number of colors needed to color vertices such that no two adjacent vertices ...
7
votes
2answers
340 views
Finding the most flexible of all 35 hexominoes
Of all 35 hexominoes, which is (or are) the most flexible of all, that is, the one (or ones) that can be converted into the most other hexominoes just by cutting out one of its component squares (thus ...
2
votes
1answer
110 views
Happy Birthday, Don!
My friend Johan de Ruiter has made a nice puzzle for Donald Knuth's Birthday. The numbers indicate how many connections that candle has. Can you solve it?
Original link: https://www-cs-faculty....
20
votes
1answer
1k views
Four mathematicians and their ages
Four mathematicians, none yet a centenarian, meet for coffee. The graph-theorist among them noticed that the common divisor graph of their ages (that is, the graph whose vertices are their ages, two ...
4
votes
1answer
149 views
Playing Collatz with graphs
a) Given a set of positive integers, its common divisor graph (CD-graph) is the graph whose vertices are the integers, two of which are joined by an edge if (and only if) they have a common divisor ...
17
votes
2answers
625 views
Another Rook's Tour
Place numbers 1 to 100 in the cells of this 10 x 10 board in such a way that consecutive numbers, and also numbers 1 and 100, occupy neighboring cells (either vertically or horizontally). Prime ...
9
votes
1answer
298 views
A Demetri Puzzle
Apparently, yesterday was National Puzzle Day (in the US, I think).
As part of the celebration, American comedian Demetri Martin posted a puzzle on Twitter: https://twitter.com/DemetriMartin/status/...
19
votes
3answers
3k views
A 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, and also numbers 1 and 64, occupy neighboring cells (either vertically or horizontally). Shaded cells ...
4
votes
1answer
140 views
Another series of fortunate (and sideways) transpositions
Using only a sequence of transpositions, see if you can take this:
to this:
while maintaining English words on each of the three horizontals.
At each step, you may transpose any two neighboring ...
14
votes
2answers
397 views
A series of fortunate transpositions
Using only a sequence of transpositions, see if you can take this:
to this:
while maintaining English words on each of the three horizontals.
At each step, you may transpose any two neighboring ...
7
votes
1answer
165 views
Given a 7x7 grid, what moves need to be made to get two agents on their respective opposite sides of the grid on the diagonal?
Say I had the following 7x7 grid and two agents on the grid facing one another as shown.
The agents can follow the following commands: moveForward, turnRight, turnLeft.
The agents have to follow the ...
12
votes
2answers
493 views
Heavens to Megatron!
See if you can fill in all the blank letter tiles in this graph
using the clues sets below.
Each set of clues yields a name or word. The name or word is guaranteed to follow some connected path ...
13
votes
2answers
291 views
Happy birthday Ramanujan!
On December 22 2019, Ramanujan would have been 132 years old. In his memory here are two puzzles around 132.
In the six vertices of each of these graphs place six positive integers that add up to ...
5
votes
1answer
145 views
The grandest zoo in Appelhaken
In the magnificent country of Appelhaken there is a zoo. Not just any zoo, but a grand zoo, a magnificent zoo, called Appelhaken Grand Magnificent Magnificent Grand Grand Zoo.
In this zoo there are ...
8
votes
1answer
172 views
The grandest bridge in Appelhaken [duplicate]
In the capital of the grand country of Appelhaken there is a plane garden containing four magnificent monuments. So magnificent are they that the country has a Law requiring that there must be a ...
2
votes
3answers
163 views
Problems on Graphs
I want to test if someone with no experience in Graph Theory can solve my Problems involving Graphs. If you do know some Graph Theory I'd appreciate if you let me know in your answer.
They do not ...
0
votes
2answers
114 views
Painting edges of a 3x3 grid with 4 colours
Can you paint the edges of a 3x3 grid with 4 colours, such that:
The colours of edges of every 1x1 square are different.
The colours of edges adjacent to every vertex are different.
Here is a ...
0
votes
1answer
73 views
Painting edges of a 2x2 grid with 4 colours
Can you paint the edges of a 2x2 grid with 4 colours, such that:
The colours of edges of every 1x1 square are different.
The colours of edges adjacent to every vertex are different.
Good luck!
9
votes
1answer
521 views
Connect the wires without setting off the bomb
You just saw a planted time bomb! Just 5 minutes are remaining until it explodes and as you are in currently in a rural area (no bomb disposal squad) and you know how bombs usually work it is up to ...
8
votes
1answer
579 views
Winning the Lottery
Bob: I hear you won the lottery.
Alice: So I did!
Bob: What six numbers did you win it with?
Alice: Can't remember. All I recall is that they were all different, and none greater than 28.
Bob: ...
10
votes
2answers
592 views
National Graph Lottery
In UK's National Lottery players choose 6 different whole numbers in the range 1 to 59, and win a large prize if all six match with the day's draw.
Each choice of six numbers by a player gives rise ...
12
votes
1answer
432 views
The arrow of time flies in reverse
Here is the puzzle:
(Click on the image to see a larger image.)
Overview:
This is a word graph. The nodes are short words, the edges are long words.
Whenever an edge (i.e., a long word) connects ...
10
votes
2answers
598 views
A Magic Flying Saucer
Place 19 different positive integers on the vertices of this graph so that the 13 products of three numbers in a straight line are all equal. Do so in such a way that the product is as small as ...
5
votes
1answer
218 views
Uncover Lenny Fingers' street hustle
Lenny Fingers is out on the street again, hustling people with his shell games. This time, he's using words.
As you walk by, Lenny grabs you with an enthusiastic smile and shows you two words side-...
