Questions tagged [graph-theory]
A puzzle built around graphs: sets of nodes joined together by paths. Use with [mathematics]
179
questions
3
votes
1answer
258 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 ...
-2
votes
1answer
137 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 ...
8
votes
2answers
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 ...
2
votes
1answer
108 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 ...
0
votes
1answer
74 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 ...
2
votes
3answers
195 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 ...
8
votes
3answers
322 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 ...
2
votes
1answer
100 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 ...
2
votes
1answer
85 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 ...
4
votes
1answer
123 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 ...
3
votes
1answer
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 ...
2
votes
1answer
162 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 ...
0
votes
1answer
100 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 ...
3
votes
2answers
205 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 ...
2
votes
0answers
68 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 ...
1
vote
2answers
233 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 ...
0
votes
1answer
128 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 ...
13
votes
7answers
848 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 ...
0
votes
1answer
98 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 ...
3
votes
1answer
154 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 ...
3
votes
0answers
201 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 ...
1
vote
1answer
88 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
1answer
166 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?
22
votes
1answer
598 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?...
0
votes
2answers
78 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 ...
14
votes
1answer
421 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:
7
votes
2answers
838 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 ...
9
votes
2answers
483 views
Dragon summoning spell
The parchment shown below got stained with something. See if you can determine the obscured parts.
7
votes
1answer
178 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
votes
1answer
86 views
How many different ways can you color the diagram?
This question is a continuation of this one.
Here are nine squares, connected by lines.
Each square must be colored, and two squares connected by a line must be colored differently.
Question 1. What ...
12
votes
1answer
369 views
Infection (Information Dissemination) Puzzle
There are 2020 people in a room. One person has COVID.
After each minute, each person $\mathrm{P}$ is paired with some other person $\mathrm{Q}$ who was never paired with $\mathrm{P}$ before, and they ...
2
votes
0answers
462 views
A robot moving on a grid. Part 2
This is an extension of the discussion
A robot is placed on a grid point. At each move the robot must take three steps along the edge of the grid. After each step the robot must turn right. Lengths of ...
2
votes
1answer
260 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 ...
6
votes
2answers
358 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 ...
asked Jul 25 '20 at 14:18
Bernardo Recamán Santos
12.9k2 gold badges23 silver badges116 bronze badges
5
votes
1answer
99 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
170 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 ...
7
votes
2answers
219 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
179 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
812 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
314 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 ...
asked May 16 '20 at 14:53
Bernardo Recamán Santos
12.9k2 gold badges23 silver badges116 bronze badges
2
votes
1answer
95 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
231 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
391 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 ...
asked May 14 '20 at 17:18
Bernardo Recamán Santos
12.9k2 gold badges23 silver badges116 bronze badges
3
votes
2answers
274 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
309 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
159 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
256 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
163 views
3
votes
1answer
122 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
123 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 ...
