# Tagged Questions

68 views

### A game on a smaller graph

In this question Alice and Bob play a game on $K_{2014}$, Alice directing one edge, Bob directing $1$ to $1000$ edges with Alice trying to make a cycle. The proof that Alice can win depended on the ...
830 views

### A problem I can't solve from my childhood to now.

When I was a child I was given this problem to send a wire from electricity, water, and internet to each of the houses, all three houses must have all three wires connected without being crossed ...
41 views

### Graph-like problem

Each shop in a town has an odd number of customers and each pair of shops shares an even number of customers. Prove that there are at least as many customers as there are shops. Any hints are ...
72 views

### For which chess boards do solutions exist for this generalised Knight's Tour problem?

We know from a theorem by Schwenk that for any (m x n) chess board with $m \leq n$ it is always possible to create a knight's tour unless one or more of these three conditions are met: m and n are ...
3k views

### The Best Strategy and Highest Possible Score for the “Threes!” Game.

[There's still the strategy to go. A suitably robust argument that establishes what is statistically the best strategy will be accepted.] Here's my description of the game: There's a $4\times 4$ ...
42 views

### Degree sequence in $O(n)$

How can we determine the whether a sequence of non negative integers is a valid degree sequence in $O(n)$. I have determined an $O(n\log n)$ algorithm using erdos-gallai theorem.
116 views

### Mathematicly Untangeling Untangle.

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it. some free games: (but be warned highly addictive) Javascript: ...
88 views

### How to find the planar embedding of a graph in general?

I need to find the planar embedding of a graph in general if one exists and specifically want to solve the problem for the graph in the figure below. I am acquainted with the graph algorithms but have ...
328 views

### Counting the number of polygons in a figure

I often come across figures like this on the net, or as contest problems, asking to find the number of a specific type of polygon in the figure (triangles, in this case). But I've never really found ...
271 views

### What am I getting for Christmas? Secret Santa and Graph theory

I live with four people, who thankfully don't spend much time on maths.se. We decided this year that we'd do a Secret Santa. We can represent the arrangement of who's buying for whom using a directed ...
866 views

### Proof Involving a Problem from “Good Will Hunting”

I don't know if any of you have seen the movie "Good Will Hunting" but there is a particular mathematics problem in the movie that is of interest to be. One of the problems used in the movie is "Draw ...
112 views

### Monotonically increasing path in a complete graph

Given a complete graph with n vertices such that all edge weights are distinct. Prove that we can find a monotonically increasing path of length n-1. I tried finding such a path by sorting the edges ...
207 views

### If we draw infinitely many lines on a table, can we find a triangle somewhere? [closed]

If we draw infinitely many lines on a table, can we find a triangle somewhere? We prove that there is a subgraph $C_3$ in $C_n$, which will be called a triangle. Suppose we have an infinite ...
1k views

### How does the divisibility graphs work?

I came across this graphic method for checking divisibility by $7$. $\hskip1.5in$ Write down a number $n$. Start at the small white node at the bottom of the graph. For each digit $d$ in ...
57 views

### What's the difference between a $2$-sided and $2$-sided strip polytan

There are $14$ $2$-sided tetratans and $13$ $2$-sided strip tetratans. The sets are identical, except the square is missing in the strip version. My best guess is that for strips, no vertex can have ...
98 views

1k views

### The $n$ Immortals problem.

I saw this riddle posted on reddit a long time ago, called the "Seven Immortals." In the beginning, the world is inhabited by seven immortals, ageless and sexless, who begin to multiply and ...
266 views

### A less challenging trivia problem

There are 25 people sitting around a table and each person has two cards. One of the numbers 1,2,..., 25 is written on each card, and each number occurs on exactly two cards. At a signal, each person ...
160 views

### 100 roads in a city, 1 is closed

In a certain country, 100 roads lead out of each city, and one can travel along those roads from any city to any other. One road is closed for repairs. Prove that one can still get from any city to ...
75 views

### List number of moves to defeat the opponent

Given the position of chess board of two players, we have to find the minimum number of moves (and output them) so that only one player playing continuously and optimally defeat the other one ...
4k views

### Average Scrabble graph structure: diameter?

Tonight a game of Scrabble ended in what I consider a very unusual graph structure, unlike this generic web image, which seems more typical: ...
379 views

### What's behind Conway's Game of Life search algorithms?

I've been looking at a program gfind, that searches for spaceships in Conway's Game of Life. The documentation says a bunch of stuff about searching De-Bruijin graphs. I couldn't find any useful ...
968 views

### Handshake problem

I was given the following math puzzle which (I thought) has an interesting solution. A mathematician and her husband attended a party with $n-1$ other couples. As is normal at parties, handshaking ...
136 views

### A game played on graphs by “flipping” the state of a vertex and its neighbors

This is a well-known game: We are given a finite undirected graph $G=(V,E)$ whose vertices are labeled by "0". At each turn, we pick a vertex, and then it and all its neighbors flip their label (0 ...
546 views

### How to create mazes on the hyperbolic plane?

I'm interested in building maze-like structures on the [5, 4] tiling of the hyperbolic plane, where by maze-like I mean something akin to a spanning tree of the underlying lattice: a subgraph of the ...