Skip to main content

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
-6 votes
0 answers
63 views

Temporal graph sequence [closed]

I came across a sequence of relative interest: 1, 1, 1, 20, 4524, 23218501, 3129434545680 The sequence describes the number of different simple temporal graphs up to isomorphism, more precisely simple ...
Fluorine's user avatar
  • 1,170
1 vote
2 answers
617 views

Graph needed which satisfy both properties 1 and 2

We were conducting a tournament where we had 5 teams named- A,B,C,D,E. And in the first round every team played with every other team. So there were 10 matches. But these matches happened during rainy ...
Durgesh Patel's user avatar
4 votes
1 answer
170 views

Curious statements about black cells on a grid

Consider a finite rectangular grid consisting of unit squares (cells). Some cells are colored black, and the rest are white. Some definitions: Two black cells are neighbors if they share an edge. Two ...
Bubbler's user avatar
  • 15.1k
14 votes
7 answers
3k views

Join six cities with roads

Warmup question: Each of five cities is connected to the others by four roads. Show that it is possible for the roads to intersect only once with exactly two roads crossing over at that single ...
Will Octagon Gibson's user avatar
6 votes
2 answers
342 views

While 2024 arrives

There are about $9.266 \times 10^{45}$ partitions of 2024, a handful! To each of these partitions corresponds a graph in which the vertices are each of the parts, two of which are joined by an edge if ...
Bernardo Recamán Santos's user avatar
5 votes
1 answer
208 views

Puzzling Pelican Pebbles

Story Setup It's Percy the Pelican's first day running the front desk of his master's magical pebble shop. His job is to fetch pebbles from the stock room to fulfill customer orders. The stock room ...
DqwertyC's user avatar
  • 8,216
17 votes
1 answer
777 views

Poetry of the stars

Prof. Levenshtein is meant to be teaching us astronomy, but they fancy themselves as a poet. Can you figure out the name they've given to each star?
andypea's user avatar
  • 273
14 votes
5 answers
3k views

Are there always 2 teams such that they have together defeated every other team

In a tournament without draws, every two of the nine teams play against each other exactly once. Must there always be two teams such that every other team has lost to either or both of them? From the ...
Hemant Agarwal's user avatar
12 votes
3 answers
2k views

An immortal ant on a gridded, beveled cube divided into 3458 regions

This puzzle takes place on the surface of the following gridded, beveled cube: The surface of this cube is divided into 3458 small regions separated by black lines. Of these regions, 3450 of them are ...
plasticinsect's user avatar
32 votes
2 answers
8k views

Is this Hashi puzzle unsolvable?

I found this puzzle in my dad's bathroom. The book is "Things To Do While You Poo On The Loo". I think the puzzle is malformed. Here is a Penpa link to an online solver. Is there actually an ...
ConnieMnemonic's user avatar
1 vote
1 answer
207 views

How many ways are there to mark a way to walk around every edge of the triforce?

A triforce for the purposes of this question is a plane figure with an equilateral triangle at its center, with one additional vertex connected to each pair of original vertices (forming an additional ...
Cong Chen's user avatar
  • 179
19 votes
1 answer
674 views

World Tour of Planet Rhombicosidodecahedria

This is the planet Rhombicosidodecahedria: This lovely planet has 62 countries, each with its own distinct history and culture. By an amazing coincidence, the countries all happen to coincide ...
plasticinsect's user avatar
29 votes
4 answers
3k views

Rolling cube on an infinite chessboard

Imagine a six-sided die, D6, the right size to exactly occupy a square on a chessboard. The die can move to any adjacent square, but does so by rolling rather than sliding, so the topmost side of the ...
Laska's user avatar
  • 1,919
1 vote
4 answers
319 views

Coordinating trains? [closed]

In the picture below, each node represents a train station. On each node there is a train. Two trains can change the location / node they are in, if they are connected by an arrow. The puzzle is this: ...
stackExchangeUser's user avatar
35 votes
5 answers
3k views

A Queen and her Pawns

Place a queen and as many pawns as possible on a chessboard so that the queen has just one way of capturing all the pawns in precisely as many moves as there are pawns. Pawns do not move and do not ...
Bernardo Recamán Santos's user avatar
2 votes
3 answers
237 views

Detecting Connected Components on an Infinite Graph after Modification

This puzzle was inspired by thinking about how to implement a system like Factorio's power grid. Start with an infinite connected undirected acyclic graph. Graph = A set of nodes (called "...
Tim C's user avatar
  • 2,554
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 ...
Bass's user avatar
  • 77.6k
4 votes
1 answer
240 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 ...
Nurator's user avatar
  • 379
3 votes
2 answers
253 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 ...
Manish Kundu's user avatar
  • 2,684
-2 votes
1 answer
208 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 (...
Kevin's user avatar
  • 15
8 votes
1 answer
349 views

Snowy, snowy night

Notice that each snowflake is composed of seven hexagons, and each hexagon has a word written clockwise around its perimeter.
SlowMagic's user avatar
  • 13.8k
5 votes
1 answer
264 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....
NielIGuess's user avatar
  • 1,024
11 votes
1 answer
817 views

It comprises that which composes it

Text version: ...
SlowMagic's user avatar
  • 13.8k
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 ...
Christian E. Ramirez's user avatar
3 votes
1 answer
286 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 ...
theonetruepath's user avatar
3 votes
1 answer
426 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 ...
Dmitry Kamenetsky's user avatar
27 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, ...
SlowMagic's user avatar
  • 13.8k
4 votes
2 answers
884 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: ...
SlowMagic's user avatar
  • 13.8k
18 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, ...
JLee's user avatar
  • 19.4k
5 votes
2 answers
247 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....
Dmitry Kamenetsky's user avatar
3 votes
2 answers
2k 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. ...
Dmitry Kamenetsky's user avatar
6 votes
4 answers
429 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-...
JKHA's user avatar
  • 6,033
6 votes
2 answers
770 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 ...
Bernardo Recamán Santos's user avatar
-1 votes
1 answer
220 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 ...
Nick's user avatar
  • 1,695
3 votes
2 answers
240 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 ...
noedne's user avatar
  • 15.4k
3 votes
4 answers
285 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 ...
DrD's user avatar
  • 39.3k
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 ...
caird coinheringaahing's user avatar
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 ...
Parcly Taxel's user avatar
  • 7,720
8 votes
1 answer
222 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 ...
Bernardo Recamán Santos's user avatar
9 votes
1 answer
313 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 ...
Parcly Taxel's user avatar
  • 7,720
2 votes
1 answer
259 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 ...
Hemant Agarwal's user avatar
3 votes
1 answer
432 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 ...
Parcly Taxel's user avatar
  • 7,720
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 ...
happystar's user avatar
  • 7,664
4 votes
2 answers
1k 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 ...
Bernardo Recamán Santos's user avatar
8 votes
2 answers
1k 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 ...
Bernardo Recamán Santos's user avatar
3 votes
1 answer
944 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 ...
Ice Tea's user avatar
  • 309
2 votes
2 answers
217 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 ...
Bernardo Recamán Santos's user avatar
7 votes
2 answers
1k 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 ...
Bernardo Recamán Santos's user avatar
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 ...
Mike Earnest's user avatar
  • 32.4k
-4 votes
1 answer
166 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 ...
Hemant Agarwal's user avatar

1
2 3 4 5