Category Archives: Combinatorics

Class-metric

In two weeks I start lecturing Topology I at our University. I am excited. This course was my favourite among the basic undergraduate courses. The course concentrates on metric topology and its goal is to prove simple results about complete … Continue reading

Posted in Combinatorics, Logic, Mathematics, Ramsey Theory, Set Theory, Topology, Wednesday Problem | Leave a comment

Prisoners’ problem 6

Three prisoners meet a guard. The guard says: I have hats with me, two of which are black and the others are white. The prisoners ask: “How many hats there are all together?” He says: “It’s a secret!”. The guard … Continue reading

Posted in Combinatorics, Recreation, Wednesday Problem | Tagged | 2 Comments

Doodling with Fractals and Persistent Worms.

Suppose we have a rubber line of length 1 m and a worm at the other end. The worm moves 10 cm in a minute and its goal is to reach the other end moving along the rubber line. However … Continue reading

Posted in Combinatorics, Geometry, Mathematics, Recreation | 1 Comment

A Year Problem

There are more year problems than years. But since I have been pondering on this particular one, I will present it here. You are allowed to use +, -, / and * (plus, minus, division and multiplication) signs and bracketing. … Continue reading

Posted in Algebra, Combinatorics, Mathematics, Recreation, Wednesday Problem | 12 Comments

More Chessboard

You are free to comment your solutions, questions and remarks.. You have two kinds of allowed moves. One move is to jump with a piece over another piece in a horizontal or vertical direction like this: and to jump with … Continue reading

Posted in Combinatorics, Games, Mathematics, Recreation, Wednesday Problem | Tagged | 3 Comments

Prisoners’ Problem 5

There is a famous class of problems concerning public announcements. There is a philosophical (sociological) appeal in these problems. Can a public announcement change the behaviour of the citizens? Of course, if it is for example a news article about … Continue reading

Posted in Combinatorics, Mathematics, Philosophy, Recreation | Tagged | Leave a comment

Incomplete Chess Board

Please comment your solutions, questions and remarks.. I learned this puzzle from Juha Oikkonen, but it is probably quite famous anyway. You have left your chess board on the table in the summer house and when you came back you … Continue reading

Posted in Combinatorics, Games, Mathematics, Recreation, Wednesday Problem | Tagged | 2 Comments

Map Colouring Problem And Compactness

Suppose G is a planar graph embedded into the plane. The graph divides the plane into regions. Let us say that two regions are adjoint if they have a common edge. Question: (Q) Is it possible to colour the regions … Continue reading

Posted in Combinatorics, Geometry, Logic, Mathematics, Topology | Leave a comment

Poisoned Bunnies

Please comment your solutions, questions and remarks.. Imagine that you have one thousand bottles in front of you. You know that one of them is filled with poison and others with water, but you do not know which one is … Continue reading

Posted in Combinatorics, Mathematics, Recreation, Wednesday Problem | 7 Comments

Using Abstract Algebra To Understand Basic Combinatorics

Pascal’s triangle has many fascinating properties. One of them is for any given prime number p, the number of k-element subsets (0< k < p) of a p-element set is divisible by p: [tex]p | \binom{p}{k}\qquad \qquad \qquad (*)[/tex] You … Continue reading

Posted in Algebra, Combinatorics, Mathematics | Tagged | 5 Comments

Prisoners’ problem 4

The rules are as in the previous problem, but this time there are only 100 prisoners. How should they do so that 50 of them certainly survives? 3/5

Posted in Combinatorics, Mathematics, Recreation, Wednesday Problem | Tagged | Leave a comment

Prisoner’s problem 3

Please comment your solutions, questions and remarks.. There are infinitely many prisoners in a prison. The prisoners are taken to the yard and everyone is given a hat which is either black or white. No one knows the colour of … Continue reading

Posted in Combinatorics, Mathematics, Recreation, Set Theory, Wednesday Problem | Tagged | 2 Comments

Prisoner’s problem 1

Please comment your solutions, questions and remarks.. We are going to have several prisoner problems! Better solve them before you end up in jail. There are 2010 prisoners in the prison. One day the chair of the prison gathers the … Continue reading

Posted in Combinatorics, Mathematics, Recreation, Wednesday Problem | Tagged | 5 Comments

How Many Good Colorings?

Please comment your solutions, questions and remarks.. Suppose G is a graph in which each vertex has three neighbours, for example: Suppose we have three colors, red green and blue, with which we want to color the edges of the … Continue reading

Posted in Algebra, Combinatorics, Mathematics, Wednesday Problem | Leave a comment

Nasty Finite Combinatorics

Please comment your solutions, questions and remarks.. I was blamed for having too easy Wednesday problems. So beware! The level is coming up! Suppose that K is a set of n elements, [tex]n\in\mathbb{N}[/tex]. Suppose that [tex]K_1,\dots,K_n,K_{n+1}[/tex] are subsets of K. … Continue reading

Posted in Combinatorics, Mathematics, Set Theory, Wednesday Problem | Leave a comment

Andre’s Reflection Method

I promised to post something about random walks. I learned the content of this post while listening to Vilppu Tarvainen’s bachelor’s degree talk and I consider it is quite cute. Let us consider a one dimensional random walk: formally it … Continue reading

Posted in Combinatorics, Mathematics, Probability, Recreation | 1 Comment

Even More On BFPT

I wouldn’t mind writing this unless I haven’t already posted two different proofs of Brouwer’s Fixed Point Theorem. Namely a friend of mine and a reader of this blog, exposed me to another way of proving it. This proof has … Continue reading

Posted in Combinatorics, Mathematics, Topology | Tagged | Leave a comment

Games in Topology (Another Proof of Brouwer’s Fixed Point Theorem)

Theorem (Brouwer’s Fixed Point Theorem, BFPT). Suppose that [tex]B\subset \mathbb{R}^n[/tex] is the closed n-dimensional unit ball and [tex]f\colon B\to B[/tex] is a continuous function. Then there exists a point [tex]x\in B[/tex] such that [tex]f(x)=x[/tex]. Theorem (Jordan’s Curve Theorem) Let [tex]f\colon … Continue reading

Posted in Combinatorics, Games, Mathematics, Topology | Tagged | 2 Comments

Stable Marriages

Suppose n men and n women survived after a spaceship crush on a planet orbiting Alpha Centauri. They happen all to be heterosexuals and all single (or their partners died in the crush). Each man then ranks women in order … Continue reading

Posted in Combinatorics, Mathematics, Recreation | Leave a comment

Brouwer’s Fixed Point Theorem: Many in One Post

In this post I will (1) give a simple proof of Brouwer Fixed Point Theorem (2) fulfill the promise given here (3) present the Wednesday Problem in the form fill in the details in the below text Theorem (Brouwer’s Fixed … Continue reading

Posted in Combinatorics, Mathematics, Topology, Wednesday Problem | Tagged | 2 Comments

How Old Are The Kids?

Please comment your solutions, questions and remarks.. This is quite famous. But maybe you haven’t heard it yet: A math student goes to a party organized by her supervisor. The student asks: How many daughters do you have? And the … Continue reading

Posted in Combinatorics, Recreation, Wednesday Problem | 2 Comments

MAD families

Please comment your solutions, questions and remarks.. Maximal Almost Disjoint families. This is not so much of a riddle than just a theorem, but the solution is fun, so I would like to place it here. This is like a … Continue reading

Posted in Combinatorics, Mathematics, Set Theory, Wednesday Problem | Leave a comment

The Game Discrete

Inspired by my post about tic-tac-toe I want to introduce a game. It is played on a 3x3x3 grid or equivalently on a 9×3 grid:

Posted in Combinatorics, Games, Mathematics, Recreation | Leave a comment

Handshaking Lemma

Please comment your solutions, questions and remarks.. This one I learned from Sam Hardwick. Show that the number of those, who have shaken their hands with others an odd number of times, is even. Level 1/5 P.S. This lemma has … Continue reading

Posted in Combinatorics, Recreation, Wednesday Problem | 2 Comments

The Chocolate Game

Please comment your solutions, questions and remarks.. I heard this from Lauri Hella, but he doesn’t remember from whom he heard this. The game is played between two players as follows. There is an [tex]n\times m[/tex] bar of chocolate on … Continue reading

Posted in Combinatorics, Games, Mathematics, Recreation, Wednesday Problem | 2 Comments

Tic-tac-toe And A Non-Constructive Proof

Usually the game tic-tac-toe is played on an infinite board (i.e. 30 times 40 or something). The two players draw X:s and 0:s to the squares of a notepad paper. Player 1 (beginner) is the X-drawer and the Player 2 … Continue reading

Posted in Combinatorics, Games, Mathematics, Ramsey Theory, Recreation | Leave a comment