Questions tagged [graph-theory]

A puzzle built around graphs: sets of nodes joined together by paths. Use with [mathematics]

Filter by
Sorted by
Tagged with
10 votes
2 answers
2k views

Can you eat a 4-dimensional Rubik's Cube?

If you follow the traditional Rubik's cube eating conventions, Start by eating any piece except the central one Next, eat a piece orthogonally adjacent to the previously eaten piece (repeat) The last ...
  • 70.8k
4 votes
1 answer
217 views

Non-separable sudoku numbers

The standard rules for sudoku say that you have a 9×9 grid and need to put in every digit from 1 to 9 in a way that each digit occurs exactly once in each row, column and 3×3 box. So the grid can be ...
  • 337
3 votes
2 answers
227 views

Directed Graphs from numbers

Bob and Alice play a game. Bob sends a sequence of positive numbers to Alice and using that information she forms a directed graph. For each number in the sequence, she splits it into two non-empty ...
  • 1,532
-2 votes
1 answer
193 views

What is the solution to this room maze? I still don't know!

There are 3 rooms (two on top, one on bottow- like an upside down pyramid) with 12 doors, each room with 5 doors (three doors are shared between multiple rooms). You have to make one solid line (...
  • 15
8 votes
1 answer
334 views

Snowy, snowy night

Notice that each snowflake is composed of seven hexagons, and each hexagon has a word written clockwise around its perimeter.
  • 12.5k
5 votes
1 answer
249 views

Who wins this game of graphs?

Albert and Bob are playing a game. This time it works like this: there are n points and Albert can ask whether or not $2$ points are connected. Bob then decides whether or not the points are connected....
11 votes
1 answer
801 views

It comprises that which composes it

Text version: ...
  • 12.5k
14 votes
4 answers
2k views

Labyrinth of Teleporters

You find yourself in an empty room, with a few distinctly numbered elevated platforms on the floor; your only possession is a pebble that can easily be picked up and placed down. You step on one of ...
  • 243
3 votes
1 answer
135 views

Tetromino tilings of a 4x5 rectangle with minimal diversity

This is a relatively easy manual tiling puzzle. In fact the tiling is all done for you, you just have to specify how many of each of the 26 given tilings to use. The puzzle is: Using N complete sets ...
3 votes
1 answer
362 views

Largest word tree

I was inspired by this awesome puzzle. Here is an image of a word tree borrowed from there: In a word tree every path from the root to the leaves must form a distinct word. The size of the tree is ...
26 votes
1 answer
2k views

Two mystical trees

Behold, the mystical Tree of B: Notice that every path from trunk to canopy forms a word. You should see 16 words (from left to right: BLOOM, BLOOD, BLOWN, BLOWS, BLAND, BLANK, BLASÉ, BLAST, BROOK, ...
  • 12.5k
4 votes
2 answers
858 views

D&D dice for literary people

Put a letter on each face of an icosahedron such that a five-letter word can be read clockwise around each vertex. Specifically, these words: ...
  • 12.5k
17 votes
7 answers
1k views

Efficient Mowing at PSE

Your task: Find the most efficient mowing path around the dark green bushes that mows (passes over) all of the grass (light green). For those who cannot view the image above, there are 9 rows of 16, ...
  • 17.4k
5 votes
2 answers
226 views

Robot painting a $K_5$

A robot starts at a node of a fully connected graph of 5 nodes (shown below). Each turn the robot can move across an edge and paint it in one of two colours - blue for odd turns and red for even turns....
3 votes
2 answers
644 views

The longest path of edges on a 3x3 grid

A robot is placed on some vertex of a 3x3 grid. At each move the robot can take one step (up, down, left or right) along the edge of the grid to the adjacent vertex, but it cannot go outside the grid. ...
6 votes
4 answers
324 views

Cover an n times n grid with non-diagonal non-intersecting n-1 shortest paths

This puzzle was given to me by PhD student colleagues. Suppose that you have a $n\times n$ grid. Is it possible, for a given $n$ to cover all its $n^2$ nodes with $n-1$ non-diagonal and non-...
  • 5,881
6 votes
2 answers
219 views

Splitting the integers 1 to 36

Split the integers 1 to 36 into two sets, A and B, such that any number in set A has a common divisor greater than 1 with no more than two other numbers in A, but for every number in B there are at ...
-1 votes
1 answer
161 views

How to arrange the colored cells in game grid?

Puzzle: In a game grid some cells are missing. Each line has only one colored cell with a label (a number greater than zero). This is an example grid and the number of columns/rows can be less than ...
  • 1,701
2 votes
2 answers
229 views

Planar Investigator

Use logical deduction to place a different digit from 1 to 9 in each circle below so that 8 of the arrows form the primes 23, 31, 41, 53, 59, 79, 89, and 97. (We view an arrow starting at digit A and ...
  • 15.3k
3 votes
4 answers
265 views

Travel in the USA

If you decide to travel from state to state in US in alphabetical order how many states can you cover if: The state you are in must share a border with the previous state. The last state in your list ...
  • 38.9k
12 votes
3 answers
2k views

Longest infinite loop of 5 states

This is based on a question I posed in The Nineteenth Byte: What group of 5 states have the longest total name, under the constraint that you must be able to travel from one state to another in the ...
7 votes
1 answer
1k views

Can you stop the falling piano with 23 nets?

MIT's Baker House has a tradition of dropping an irrepairable piano six floors every Drop Day, the last day one can drop a class without penalty (the 2022 date is 19 April). This year, in order to ...
  • 6,340
8 votes
1 answer
201 views

A Knight's Tour

A lonely chess knight stands on a cell somewhere in the first row of a 3x13 board, and elsewhere there is a castle. The knight takes a tour of all the remaining 37 cells of the board, missing just the ...
9 votes
1 answer
304 views

Be Paired or Be Square

8 white and 8 black dots are drawn on a piece of paper. Parcly and Tori take turns drawing edges, always between white and black dots not already adjacent (so the graph is always bipartite); the first ...
  • 6,340
2 votes
1 answer
247 views

Prove the existence of a triangle such that all of its sides are of the same color [closed]

Seventeen points have been picked in a plane, and each pair of points has been connected by a line segment of one of three colors: red, yellow, or green. Prove that there are three points which are ...
3 votes
1 answer
423 views

Genies' chess on a 10×10 board

The work of Hearth Taxel revealed some other results related to genies' chess. For example, there is an arrangement $A$ of pawns on a 10×10 board such that no 3×3 submatrix is empty and $A$ is ...
  • 6,340
13 votes
1 answer
1k views

Cracking the Cryptic Logo

The well-known Cracking The Cryptic YouTube channel has a logo consisting of 12 circles joined by 16 straight lines running horizontally, vertically or diagonally. What is the significance of this ...
  • 6,631
4 votes
2 answers
370 views

The Divisibility Graph... Again!

The divisibility graph of a set of positive integers is the graph whose vertices are the integers, two of which are joined by an edge if one divides the other. What is the smallest positive integer ...
8 votes
2 answers
558 views

Divisibility Graph

The divisibility graph of a set of integers is the graph whose vertices are the integers, two of which are joined by an edge if one divides the other. What is the largest integer N such that the ...
3 votes
1 answer
864 views

Most efficient way for people along the edges of a grid to move to the center

I'm considering a $2k\times 2k$ square grid ($k\in\mathbb Z^+$) with $8k$ highly rational people standing along the vertices forming the perimeter. All of these people want to go to the centre of the ...
  • 309
2 votes
2 answers
191 views

Powerful Octagon

Place different integers on the vertices of an octagon so that the sum of the integers in any two vertices joined by one of its edges is a power of 2. Do so in such a way that the largest integer used ...
7 votes
2 answers
433 views

Another 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 occupy neighboring cells (either vertically or horizontally). Shaded cells must be occupied by prime ...
22 votes
3 answers
1k views

Knight tour on a racetrack

Help the chess knight complete four clockwise laps on this racetrack, so that he lands on every square and never lands on the same square twice! The final square the knight lands on will be the same ...
  • 31.7k
-4 votes
1 answer
154 views

Show that every finite directed acyclic graph has at least one source vertex [closed]

Easy puzzle courtesy of a paper I'm reading rn: Show that every finite directed acyclic graph has at least one source vertex. That is, a vertex such that all the directed edges incident to it are ...
7 votes
1 answer
308 views

Existence of index-uniform Hashi puzzles

On the left, we have a starting configuration for a game of Hashi, and on the right, its solution: That is to say, the goal is to make connections (planar, and traveling only in cardinal directions) ...
  • 1,848
2 votes
1 answer
275 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
1 answer
149 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 ...
7 votes
2 answers
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 ...
  • 11.7k
2 votes
1 answer
122 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
1 answer
77 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
3 answers
198 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
3 answers
394 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 ...
  • 1,848
2 votes
1 answer
107 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
1 answer
88 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
1 answer
126 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
1 answer
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
1 answer
172 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
1 answer
126 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
2 answers
235 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 ...
  • 283
2 votes
0 answers
73 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 ...
  • 3,327

1
2 3 4 5