3
votes
0answers
59 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 ...
14
votes
3answers
814 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 ...
1
vote
1answer
40 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 ...
3
votes
1answer
67 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 ...
13
votes
3answers
2k 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$ ...
0
votes
1answer
41 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.
8
votes
2answers
111 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: ...
0
votes
3answers
75 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 ...
16
votes
2answers
318 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 ...
11
votes
1answer
270 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 ...
5
votes
1answer
556 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 ...
1
vote
1answer
105 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 ...
0
votes
1answer
205 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 ...
33
votes
4answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
97 views

Does this Graph converge in a finite number of steps? How fast is it?

Suppose you have a finite, planar Graph $G = (V,E)$ and a function $f_0:V \rightarrow \mathbb{Q}$. Now you define the function $f_{i \in \mathbb{N}}$ like this: $$f_i(v) := \frac{f_{i-1}(v) + ...
13
votes
3answers
295 views

Integer sequences which quickly become unimaginably large, then shrink down to “normal” size again?

There are a number of integer sequences which are known to have a few "ordinary" size values, and then to suddenly grow at unbelievably fast rates. The TREE sequence is one of these sequences, which ...
9
votes
4answers
339 views

A problem about symmetric relations on finite sets.

We have these assumptions: $X$ is a finite set. $\sim$ is an irreflexive symmetric relation on $X$. for any subset $Y\subseteq X$ we define $$\mathcal{Cl}(Y)=\{A\subseteq Y\mid(\forall a,b\in ...
19
votes
1answer
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 ...
3
votes
2answers
249 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 ...
1
vote
2answers
157 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 ...
1
vote
1answer
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 ...
14
votes
3answers
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: ...
2
votes
1answer
375 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 ...
5
votes
1answer
920 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 ...
8
votes
1answer
135 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 ...
18
votes
1answer
539 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 ...
9
votes
1answer
204 views

Cube skeleton bindings

Imagine that you have a cube skeleton, like so: Further imagine that you have three rubber bands that you can loop through any of the faces. However, only one rubber band may go through any ...
9
votes
1answer
561 views

How many disconnected graphs of the Rubik's cube exist?

Let us say that a Rubik's cube in a particular configuration is in a particular "state". All other configurations of this cube (other "states"), which can be achieved by rotations of the cube can be ...