Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

A puzzle built around graphs: sets of nodes joined together by paths.

16
votes
5answers
765 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 ...
9
votes
4answers
439 views

Mystery on the trail to Dutch Flat

On a recent amble, I happened upon a sign $\small \raise2mu ( {\normalsize\sf\color{#d90} A} \raise2mu )$ that seemed to indicate a mistake — or— a mystery. ...
2
votes
4answers
227 views

Create a special Playing Schedule - Logical/Mathematical Solution

Last Week in Training (I'm a Cycleball player) a logial problem/puzzle tricked us. And I'm wondering if there exists a logical solution for the next time. Cycleball is played in pairs (2 Players vs. ...
8
votes
2answers
788 views

Eight queens on the chessboard with mirrors

A 8-by-8 chessboard has two mirrors added on its left and right margin. The mirrors reflect the queen moves so that a queen threatens additional squares on the board. A queen threatens all squares in ...
5
votes
3answers
407 views

Crossing Frog Lake

Our Red Frog wants to get to the Orange Frog, but he can only jump right and down, but over multiple lilies if he chooses, although he can't stay still. How many ways can he do it?
14
votes
5answers
519 views

To each his own

You are a graduate student in theoretical mathematics, dabbling every so often in some interesting but equally useless computer science theory. From the beginning of the year, Professor Carl Hayden ...
6
votes
3answers
272 views

Professor Halfbrain and the tennis club

The other day, I met with professor Halfbrain and professor Erasmus in the coffee house. Professor Erasmus told us that he had been working on a schedule for a tennis club with $30$ senior and $30$ ...
41
votes
1answer
3k views

Crippled King Crossing a Canyon

A chess king has been injured in battle against an evil wizard, and can no longer move northeast or southwest. This king is on the North rim of a canyon, and must flee to safety on the South rim. ...
16
votes
2answers
2k views

Professor Halfbrain and the fantasy knight

Professor Halfbrain owns a $99\times99$ board for fantasy chess, whose rows are numbered consecutively from $1$ to $99$ and whose columns are also numbered consecutively from $1$ to $99$. A fantasy ...
14
votes
4answers
2k views

Touching coins flat on a table

On an infinite table are $n$ identical circular coins lying flat. Each coin touches exactly $k$ other coins, and any two coins are connected by a path of touching coins. Determine all possible pairs ...
26
votes
3answers
810 views

Ever increasing highway numbers

A province has 10 cities (arranged in a circular manner). Every pair of cities is directly connected by a straight highway, and each has its own unique number: Highway 1, Highway 2, Highway 3, ..., ...
3
votes
1answer
476 views

The Unknown Prison of Unknown Size

Inspired by The Circular Prison of Unknown Size by @MikeEarnest (Great puzzle, by the way!) The rules are almost same, so I won't waste time by rewriting them all here. (They're still valid, though.) ...
10
votes
2answers
1k views

An old square castle with many square rooms

The grandfather of my friend Bob has built a perfect square castle for himself and his family and divided it into 9 perfect square halls and made an armoury in the middle one. Bob's father divided ...
8
votes
1answer
512 views

Lost In Boston: How do I Get Home?

I'm posting this from my phone again because I've gotten hopelessly lost in Boston, really want to go home, and desperately need the help of some clever people on the internet. Please help me - I'm ...
14
votes
1answer
982 views

A chic party puzzler

(Based on this puzzle by Gamow. The answer there might give you a hint (so don't look yet!)) At a fancy party in Café la Tour, everybody is friends with exactly 14 of the other people present. ...
6
votes
3answers
1k views

A party puzzler

At a party, everybody is friend with exactly $22$ of the other persons present. Whenever two persons are friends, they do not have any friends in common. Whenever two persons are not friends, they ...
9
votes
6answers
1k views

A closed path on the Rubik's cube

Is it possible to draw a closed path on the surface of a standard $3\times3\times3$ Rubik's cube such that the path traverses each of the $54$ little squares exactly once, and such that the path ...
15
votes
3answers
3k views

School where every pair of students share a common grandfather

There are $64$ pupils attending a particular school. Any two of these pupils share (at least) one common grandfather. Does this imply that there are at least $43$ pupils all of which have a common ...
10
votes
2answers
515 views

Lost in Gnu York

Wanda the Wanderer is driving the streets of Gnu York. She doesn't know the what the entire map of Gnu York looks like, but she knows this much: Gnu York is flat Every intersection of streets is four-...
12
votes
5answers
424 views

Twitter Followers

There is a group of 300 Twitter users. Each user is following exactly one other user in the group. Prove that there exists a smaller group of 100 users where no one is following anyone else. Source: ...
1
vote
3answers
293 views

Computer-controlled maze

You have to build a maze whose exit can be changed by a computer. The maze consists of one entrance, hallways which can intersect, and $n$ exits. The computer has several wires leaving it each ...
13
votes
1answer
777 views

Touring the United States

You need to find a continuous path within the US that passes through all 48 contiguous states, visiting each one exactly once. If you start in Delaware, which state do you end in?
2
votes
2answers
840 views

Is there any solution for this puzzle? [duplicate]

There is a house with 5 room and one door with every single wall as shown in following figure. You have to visit every door exactly once but there is a condition that you cannot cross the path. I ...
35
votes
11answers
18k views

Connect 3 houses with 3 wells

Connect every house with every well without the lines intersecting. I am not sure if this puzzle has a solution. I have been puzzled by it for a long long time. An old man from my village mentioned ...
18
votes
6answers
1k views

The Islanders and their Birthday Presents

Once upon a time, a band of colonists, all having distinct birthdays, settled on a remote island. They had brought some mementos from the old country, around which certain mores regarding friendships ...
12
votes
4answers
932 views
7
votes
1answer
387 views

The Robostanchion Exam (a puzzle about game-graph connectedness)

The St. Čapek Crowd Control Academy, June, 2115. Commander Gall is worried. On one hand, the graduating class this year is the most promising in the institution's history, every cadet's reasoning ...
9
votes
1answer
593 views

Building a cheap road

The governor of Reniets (a land far, far away!) is known to be very stingy. He has to build a road which connects all the five cities in the region, which are oddly arranged on the vertices of a ...
7
votes
3answers
880 views

Spreading Gossip

Initially, each of 50 Puzzling Stack Exchange users have a single distinct juicy bit of gossip not known to the others. If $A$ sends an email to $B$, that email can include all the bits of gossip $...
8
votes
2answers
369 views

Bracing a Flexible Grid

Suppose that you build an $n$ by $n$ grid out of metal rods, joined at their ends in such a way that they can rotate about the joints. Below is the grid when $n=3$, along with an illustration of its ...
10
votes
5answers
806 views

Houses in a grid

You are a city planner tasked with the placement of unit-square-sized houses in a rectangular-grid allotment, the size of which is up to you but must be as small as possible to save money. The number ...
15
votes
4answers
10k views

Drawing something using one pen stroke

Can you determine if it's possible to draw a geometric figure (made up from shapes like rectangles, triangles, and other regular shapes) with one pen stroke and not drawing the same line twice. I am ...
-6
votes
2answers
352 views

Checkerboard piece inverting game

Marco and Leonardo decided to play a game on a checkerbard of 4×4 squares. The board is initially filled with two-sided identical coins. The game notes that these two players play turns alternatively ...
7
votes
1answer
601 views

Smallest number of matchsticks for a 3D structure with 6 matchsticks at each vertex

Make an as small as possible three dimensional structure of matchsticks, all of which have equal length, such that the end of each matchstick meets exactly five other ends. A matchstick is not allowed ...
4
votes
2answers
736 views

Puzzle pieces, each in contact with 5 others

You are asked to create puzzle pieces by joining together identical squares. This needs to be done such that the puzzle pieces can be arranged in a pattern with each piece being in contact with ...
14
votes
3answers
1k views

Touching Matchsticks

You are asked to place matchsticks on a flat surface such that each matchstick end meets three others, and no matches cross. It is easy to achieve this for patterns that extend indefintely: The ...
9
votes
2answers
829 views

Dissecting a square

You are asked to dissect an $N \times N$ square into polyomino pieces such that each piece shares portion of its boundary with exactly $D$ other pieces, and no piece has area exceeding $N$. This can ...
9
votes
1answer
412 views

Generalisation of tours on chessboards

It's well-known that a knight placed on one square of a chessboard can get to any other square, but a bishop can only reach half the squares from a fixed starting point. Another question on this site ...
4
votes
3answers
382 views

Every tournament has a dominant player

A tournament was played round-robin: each pair of players played a match where one defeated the other. Prove that there was a player for which every other player either lost to them or lost to someone ...
9
votes
6answers
2k views

The Bunny's Tour

The Bunny is a new chess piece. It can move in 2 different ways: Diagonally, but only exactly one space (so like a bishop with the limitations of a king). It can also "Bunny-Hop" over another bunny. ...
9
votes
1answer
319 views

What factors affect the difficulty of Hamiltonian puzzles?

There is a type of puzzle which can be modelled as finding a Hamiltonian path through a graph. One example is the Icosian game. What factors affect the difficulty of such puzzles, to be solved by ...
31
votes
18answers
28k views

Draw a line through all doors

I saw the following problem on 4chan and couldn't solve it: It's very likely to be some kind of troll (no solution). I'm hoping to see some rigorous proofs that disprove the existence of such a line....
23
votes
5answers
5k views

Is there a proof that a map of the United States requires 4 colors?

The Four color theorem states that no more than four colors are required for any map. Can it be proved or disproved that 3 colors can be used for United States map?
5
votes
1answer
236 views

MPire coloring game basic strategy

The MPire coloring game is a game where several "empires" are laid out touching each other. Your task is to color each empire a different color, and not let two of the same color touch. You also have ...