1
vote
1answer
36 views

Number of ways to travel from 1 to n in this graph?

You can move from 1 to 2, 2 to 3, and so on, step by step, till 100. Also, between the points give below, you can move directly within every pair: (10 and 60) (50 and 100) (70 and 100) (80 and ...
3
votes
0answers
67 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 ...
2
votes
0answers
42 views

Number of tries to guess M-1 letters from M-letters-code.

There are N letters in an alphabet. There is a combination lock, the code to it consists from M different letters. You can input M letters combination to try to open the lock. If you guess at least ...
2
votes
0answers
73 views

A mathematical game: moving tiles

There is a mathematical game called moving tiles. There are $8$ different movable tiles on a $3 \times 3$ board, At the beginning the tiles' location is given as following: ...
1
vote
1answer
49 views

Piping three circles to three squares

How I can prove the impossibility of joining three circles to three squares with non-intersecting lines (not strictly straight). Shapes of squares and circles are only representative. Each circle ...
2
votes
2answers
125 views

Winning a restricted game of Nim?

Given the following piles, find the Grundy number of the initial position and make the first move in a winning strategy given that no more than two sticks may be removed from a pile at any time. Pile ...
4
votes
1answer
56 views

Get from point A to point B efficiently.

This is a question I thought about while crossing the street. Suppose you're standing at the bottom-left corner of a rectangle. Your goal is moving to the the top-right corner, efficiently, ...
2
votes
1answer
42 views

Why must the subgraphs that make up the solutions to Instant Insanity be disjoint?

I keep hearing that the subgraphs to the game Instant Insanity must be disjoint. Why is this true? What if the same two colour on the front and back of a cube are the same two colours on the sides of ...
3
votes
1answer
160 views

puzzle on parks

A park contains paths that intersect at various places. The intersections all have the properties that they are 3-way intersections and that, with one exception, they are indistinguishable from each ...
6
votes
1answer
165 views

A puzzle on gcd

Consider a directed graph whose nodes are positive integers. There is a directed edge from $a$ to $b$ if $a<b$ and $a$ is relatively prime to $b$, i.e. $\mathrm{gcd}(a,b)=1$. Given two integers ...
5
votes
2answers
121 views

Are there connected, planar graphs of size $N$ with minimal degree $\left( N−2 \right)$ for any $N \in \mathbb{N}$?

I was doing a bit of doodling today with graphs of N vertices, trying my best to make sure that every vertex had minimal degree of $\left( N-2 \right)$ without any crossings. I was able to form ...
3
votes
2answers
145 views

Efficiently identifying spam honeypots

I realise that the title is computing specific, but I think the underlying problem is general - I just don't know how to phrase it more generally (which may be part of my problem). So I am asking ...
3
votes
3answers
260 views

A puzzle about graph coloring.

Let $G$ be a graph with three disjoint triangles(i.e. the graph is not connectd and has three connected components each of which is a triangle). If each vertex of G is assigned a red or a green color, ...
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
265 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 ...
5
votes
2answers
747 views

Instant insanity question

My question is regarding the necessary conditions that a graph must fulfill to satisfy instant insanity problem. Now take for example the left, right, front and back face colors of the four cubes ...
5
votes
1answer
964 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 ...
4
votes
1answer
321 views

Transforming puzzle to graph theory?

I am trying to solve the puzzle below and am thinking that there ought to be some way of formulating it as a problem about counting matchings, but I can not make it work. I would appreciate a hint or ...
19
votes
2answers
478 views

Connecting a $n, n$ point grid

I stumbled across the problem of connecting the points on a $n, n$ grid with a minimal amount of straight lines without lifting the pen. For $n=1, n=2$ it is trivial. For $n=3$ you can find the ...
11
votes
3answers
639 views

Two seemingly unrelated puzzles have very similar solutions; what's the connection?

I think it's an interesting coincidence that the locker puzzle and this puzzle about duplicate array entries (see problem 6b) have such similar solutions. Spoiler alert! Don't read on if you want to ...
6
votes
4answers
2k views

3 Utilities | 3 Houses puzzle?

There's a puzzle where you have 3 houses and 3 utilities. You must draw lines so that each house is connected to all three utilities, but the lines cannot overlap. However, I'm fairly sure that the ...
4
votes
2answers
2k views

How to prove the optimal Towers of Hanoi strategy?

In the towers of Hanoi game, how do we know that we have the optimal algorithm for solving it? I thought about this and it seemed like any deviation from the standard strategies would be putting you ...