Questions tagged [graph-theory]
A puzzle built around graphs: sets of nodes joined together by paths.
10
votes
1answer
1k views
Primes in a Diamond
Label the vertices of this graph with numbers 1 to 16 in such a way that the edges between any two vertices whose sum and absolute difference are both primes are precisely the edges of a hamiltonian ...
10
votes
4answers
287 views
Choo-choo! Word trains
All aboard the Word Train Express!
Engineering a word train is simple: I'll give you the locomotive (the first word) and the caboose (the last word), and I'll specify the number of boxcars (...
4
votes
1answer
208 views
London Underground puzzle
This is something I have thought about during my commute through the London Underground.
Is it possible to make a trip through the London underground in such a way that:
You have to use all ...
24
votes
5answers
2k views
Superhero words!
Quietly walking among us are words which are actually superheroes in disguise! Just as Diana Prince spins around to become Wonder Woman, some seemingly ordinary words can spin around to reveal their ...
12
votes
2answers
2k views
My Graph Theory Students
I have 18 students in my graph theory course this semester: Anne, Bernard, Clare, David,..., and Rachel. At the start of the course I asked them to draw the graph below, in which each of them is ...
-1
votes
2answers
106 views
Can this be drawn in one line without going over the line?
Can this image be drawn in one line and without going over any lines?
17
votes
2answers
491 views
Maximum Height of a Hotel with Strange Elevators
I encountered this puzzle many years ago, and I think back on it often as it is unique and thought provoking. As far as I know nobody has proved the given solution as optimum, so it may still be ...
6
votes
7answers
312 views
Find minimum number of meeting periods to reach 2 degrees of separation for a group [closed]
I am running a training course and I want to arrange a set of 1:1 meeting periods between the participants such that at the end of the day there is a maximum of 2 degrees of separation between any of ...
10
votes
1answer
1k views
How many colors does it take?
This question is from a popular monthly science magazine in my country:
You have an 8x8 square where any 3 squares forming a tromino (including reflections and rotations) must consist of three ...
4
votes
2answers
121 views
Identify this type of graph puzzle
There are $V-1$ pieces, each with an identifying symbol. The board is a graph with $V$ vertices and some number of edges $E$. The idea is to move around the pieces so that each piece's symbol matches ...
0
votes
1answer
116 views
A Colorful Honeycomb
What strategy can you use to color using only 6 colors the lines in an infinite hexagonal tiling such that no two sides of the same hexagon have the same color?
11
votes
6answers
701 views
I Have To Be With Them!
It's almost time for another year of school! But before school starts, Principal Little needs to form classes. Because there are so many people in a class, the parents are always complaining, asking ...
3
votes
1answer
210 views
Create a map of a game's portals
Given a set of rooms, each with a N, a S, an E, and a W exit/entrance to another of the rooms, create as simple a map as possible that graphically represents their connections.
The rooms in question ...
-4
votes
1answer
363 views
A party of jealous guys
I was really happy for the fact that I won the inter-galactic best magician award. So I decided to throw a party of $n$ people (excluding me).
The people who came to that party was jealous, really ...
22
votes
1answer
733 views
A Tour Around a Triangle
Place the 18 even integers between 2 and 36 in the empty nodes of this triangular graph in such a way that if a path is drawn by coloring in red all the edges joining any two nodes whose numbers add ...
17
votes
1answer
487 views
A partition of 1000 into nine parts
The sum of nine whole numbers is 1000. If those numbers are placed on the vertices of this graph, two of them will be joined by an edge if and only if they have a common divisor greater than 1 (i.e. ...
14
votes
3answers
369 views
Fearful asymmetry
An asymmetric graph (or identity graph) has every vertex unique: no different relabeling of the vertices leaves the edges unchanged.
The trivial graph on one vertex is (trivially) asymmetric. All ...
11
votes
1answer
451 views
Any hope for Humpty Dumpty?
It was inevitable, really... Each fragment of shell has exactly three sharp points, joined by smooth curves. While the King's horses can count reasonably well, his men have been known to confuse ...
4
votes
2answers
242 views
How many nodes in the network?
I don't actually have a solution in mind for these, but it seemed puzzly enough to bring to the table. Seems as though someone must have come up with this before, but if so, I couldn't find it when I ...
5
votes
3answers
357 views
Magic-preserving Permutations on a 4x4 Magic Square
Messing around with some magic-square puzzles, I faced the problem of deciding whether some two magical squares are, in fact, the one and same square wearing a different hat. It seemed to me, that for ...
7
votes
2answers
200 views
A partition of 1000 into six parts with least and greatest product possible
Find six positive natural numbers, not necessarily distinct, whose sum is 1000 and which, if placed appropriately on the vertices of the following graph, two of them will be joined by an edge if and ...
16
votes
3answers
2k views
A partition of 100 into nine parts
The sum of $9$ positive natural numbers, not necessarily distinct, is $100$. If placed appropriately on the vertices of the following graph, two of them will be joined by an edge if and only if they ...
22
votes
7answers
5k views
Hacking an electronic keypad
You are a spy trying to break into an enemy facility. The back door is protected by an electronic keypad lock. You know that this particular lock is opened by a four digit code. Any stream of button ...
1
vote
1answer
269 views
Scheduling Meetings
I came across this problem in real life and thought it could be made into an interesting puzzle. I will enjoy seeing how my eventual solution could be improved!
Here's the situation.
There ...
5
votes
2answers
179 views
Triangle of Safety
Saitama: "The Hero Association called me for a low-level mission, can you meet them as my representative?"
Genos: "No."
Saitama: "Aww, man.. That's not fun."
Then Saitama decided to meet Hero ...
7
votes
1answer
185 views
Trip Routes that Visit 9 of 10 Cities
There are 10 cities on this island. For each pair of cities, they may have a bidirectional path.
A trip route is defined as a route which start on a city e.g. $A$, goes to 8 of 9 other cities exactly ...
4
votes
1answer
309 views
A certain partition of 130
Given a multiset of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than ...
6
votes
2answers
224 views
Teacup geometry
Inspired by the three utilities puzzle from prog_SAHIL I'm now posting a similar puzzle that makes use of the topology of a cup with a handle:
The question is:
How many distinct points can you ...
5
votes
1answer
165 views
A minor rearrangement of the one sided hexominoes in 12 simultaneous shapes
Here are the one sided hexominoes arranged into 12 congruent shapes. But there are one or two flaws: The dark blue hexominoes, which are the symmetric ones, may not occur more than once each in a ...
14
votes
2answers
345 views
Hexominoes into 7 simultaneous congruent shapes
I came up with this puzzle 16 years ago, it was on Ed Pegg's Mathpuzzle site but nobody solved it AFAIK.
The 35 hexominoes (which look like this):
are to be arranged, in groups of five, into seven ...
12
votes
5answers
1k views
Soccer balls in the stadium
The coach asks you take as many soccer balls as possible and put those balls onto the field with the condition that
For any arbitrary set of three balls, at least two of those balls are exactly 10 ...
12
votes
1answer
287 views
Multibranched tree
The Furca Fractalis tree grows in a very special way. Starting with the trunk there are three possibilities to continue growing:
It can split in two branches.
It can grow one branch and one leaf.
...
12
votes
1answer
342 views
Jigsaw Logic: ?s galore
I am working on a 256 piece jigsaw puzzle, but I am having a lot of trouble. Instead of the picture being a landscape or painting, the final image is just a sixteen by sixteen grid of identical ...
3
votes
1answer
400 views
8 Train Stations
You are going to build $8$ train stations and the railroads with it in an area. But you are asked to build these stations and their railroads in a very efficient way where there has to be the least ...
13
votes
1answer
1k views
Hunter chasing a fox on a graph
This is a variant of the sleeping princess puzzle.
There are fifteen foxholes, connected by underground tunnels as shown below. A fox is sleeping in one of them.
Every day, a hunter checks one of ...
8
votes
2answers
2k views
Color this map using only 4 colors (easy)
According to graph theory, in order to color any map so that 2 touching regions don't have the same color, 4 distinct colors are enough.
Can somebody color the following map?
9
votes
2answers
363 views
Looking for another partition of 100
The sum of ten, not necessarily different, positive integers is 100. If placed adequately on the vertices of this graph, two of them will be joined by a line if, and only if, they have a common ...
7
votes
2answers
1k views
Is there a simple algorithm for solving Kami 2 puzzles?
I'm finding my life has been consumed by Kami 2, partly because I seem to have achieved some "insight" and am able to solve the puzzles reliably, almost always on the first try.
The rules are simple: ...
8
votes
2answers
1k views
A mystery partition of 100
Given a multiset (a set with repeated elements allowed) of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if ...
10
votes
1answer
483 views
Labelling a graph with a partition of 100
Label the vertices of this graph with positive integers (repetitions allowed) whose sum is 100 in such a way that any pair of vertices are joined by an edge if (and only if) they have labels with a ...
2
votes
3answers
359 views
Find the least number of Dragons required
The following graph represents the positions at Castle Dragonstone. Each edge indicates that the positions are within sight of each other.
This is not transitive; i.e., you can't see all the way along ...
2
votes
2answers
166 views
Find a tour through the exhibition [duplicate]
Is there a way to take a tour through the exhibition that passes through each door exactly once?
Source: chegg.com
18
votes
1answer
400 views
Interconnectivity
As I was walking through my university's mathematics department, I came across a poster pinned to the notice board. Underneath, it simply said 'In memory'. However, I could not connect the poster to ...
8
votes
1answer
409 views
A perfect metro map
You are working for a company and asked to create a perfect metro map where there will be as many stops as possible. But there are two constraints which limits the number of tracks (railroads) and ...
11
votes
5answers
746 views
Can the idiot's route be less expensive than the genius' route?
In a certain country, there are $n$ cities. Between every pair of cities, there is a fixed travel cost to go from one city to the other.
An idiot and a genius both decide to tour this country by ...
20
votes
2answers
744 views
Honeydripping around the clock
What path could a honeybee follow,
beginning and ending at top center,
visiting every empty cell exactly once
and dripping 2 drops of honey into the last cell?
Start ...
6
votes
2answers
140 views
A problem about oriented face in Square grid
Consider a $n \times n$ square grid (finite) (a square is divided into smaller squares by lines parallel to its sides). The boundary of the square is oriented, (clockwise or anticlockwise) that is, a ...
4
votes
2answers
191 views
Four mutually adjacent US states (not the Four Corners) [closed]
The question Is there a proof that a map of the United States requires 4 colors? was answered by showing that Nevada has five neighbors, each adjacent to the next (an "odd wheel"). "Adjacent" here ...
21
votes
2answers
3k views
Help the prisoners
Given a 5×5×5 cube of identical cubical cells (total 125 cells). In each cell there is a prisoner. There are doors from each cell to the adjacent cells (not diagonally). Their task is to ...
16
votes
5answers
763 views
Maximize the number of paths
You have exactly 990 edges. Assemble them into a simple undirected graph with two distinguished vertices A and B, such that the number of different simple paths from A to B is as large as you can make ...
