Walks On Math

Irrational Rectangles

By Vadim Kulikov July 21, 2010 – 4:30 in Geometry, Mathematics, Wednesday Problem

Please comment your solutions, questions and remarks..

This riddle is not easy. I solved it only after I got a hint. I got the hint without wanting it though, and I was already thinking in the right direction; so with hindsight I say that I probably was able to solve it without the hint. Given time. And passion.

Suppose a rectangle R is divided into smaller rectangles in a way similar to that pictured below, i.e. the small rectangles cover R and they do not mutually intersect except at their boundaries. Suppose that each of the smaller rectangles has the following property: its height or length (or both) is an integer. Show that then R has the same property: the height or length (or both) of R is an integer.

Rectangle

5/5

I can offer hints in the comments by request. Good luck!

Comments (0)

Uncountable Borel Sets

By Vadim Kulikov July 10, 2010 – 15:41 in Logic, Mathematics, Set Theory

Here I promised post some tough stuff. Well, I meant some fruits of our recent research by Hyttinen, Friedman and I. I will not go into the subject here, just post a link to the forthcoming paper. There is an introduction which is supposed to be understandable by a wide class of people; also definitions of these special Borel sets are accessible; see Section II.3. The text is written by me using $\LaTeX$ .

Here is the PDF file

Comments (0)

Ambient Isotopy

By Vadim Kulikov July 7, 2010 – 5:19 in Algebraic Topology, Mathematics, Topology, Wednesday Problem

Note: One is able to do puzzles 2 and 3 without reading or understanding the text before them.

In knot theory, people define equivalence of knots using the concept of ambient isotopy. Two knots (embeddings of the unit circle into the 3-dimensional Euclidean space) are equivalent, intuitively, if they could be modified to look like each other if they were made of very elastic rope. Thus the intuitive idea is clear. However any of the common definitions of continuous deformations are not usually suitable here:

Any two knots are homeomorphic to each other (as the homeomorphic images of the circle).
Any two knots are homotopic.
Any two knots are isotopic!

Isotopy means the following: two mappings

$f\colon X\to Y\text{ and }g\colon X\to Y$

are isotopic if there exists a homotopy $H\colon X\times I\to Y$ ( is the unit interval) such that for all $t\in I,\,H\restriction(X\times \{t\})$ is an embedding from to , i.e. $H\restriction X\times\{0\}=f\circ i^{-1}$ and $H\restriction X\times\{1\}=g\circ j^{-1}$ , where: i,j are (the obvious) inclusions $X\hookrightarrow X\times \{0\}$ and $X\hookrightarrow X\times \{1\}$ .

Puzzle 1. Show that any two knots, i.e. embeddings $f\colon S^1\to \mathbb{R}^3$ and $g\colon S^1\to \mathbb{R}^3$ are isotopic. Hint: Use a heuristic argument. I mean, rigorous proof is not what is expected here.

We would like to define something which would be like isotopy, but still distinguish different knots! The solution is ambient isotopy. Instead of moving the knots alone, we move the whole space in which they sit and try to move one knot onto the other in this way. This leads to the definition equivalent to the intuitive definition given above.

Thus, two maps

$f\colon X\to Y\text{ and }g\colon X\to Y$

are ambient isotopic, if there is a homeomorphism $H\colon Y\to Y$ which is isotopic (by the definition above) to the identity map id_Y with the property that $g=H\circ f.$

Now, knot theory is seeking ways to prove that two knots are not equivalent and algorithms to check whether or not / verify that two knots are equal. For instance knot theory can prove that the knots

Unequal knots

are not equal.

Knots can be generalized to links and other embeddings: Embeddings of multiple circles at the same time (links), embeddings of graphs into $\mathbb{R}^3$ and embedding of two-manifolds to $\mathbb{R}^3$ . The following links are not equal:

Unequal links

and the following embeddings of graphs are not equal:

Unequal graphs

For the possible surprise of the reader, I state the following two puzzles concerning the last mentioned generalization, embedding of two-manifolds in $\mathbb{R}^3$ :

Puzzle 2. Show that the following two embeddings of the genus two surface are equivalent (ambient isotopic; continuously deformable into one another):

Genus two surfaces

Puzzle 3. Show that the following two embeddings of the genus two surface together with a torus are equivalent (ambient isotopic; continuously deformable into one another):

Genus two surfaces with torus

Comments (0)

Around Jordans Curve Theorem I

By Vadim Kulikov July 2, 2010 – 0:23 in Mathematics, Topology

Tagged Brouwer's Fixed Point Theorem, Jodan's Curve Theorem

There are more or less three theorems that are often called Jordan Curve Theorems, while there is a distinction between them. Let us denote by E the Euclidean plane, $E=\mathbb{R}^2$ and by E^n the Euclidean n-dimensional space, $E^n=\mathbb{R}^n$ .

The Jordan Curve Theorem. Let $f\colon S^1\to E$ be an embedding of the unit circle into the plane. Then the complement of f[S^1] has two connected components, one bounded and one unbounded.

The Jordan-Schönflies Theorem. Let $f\colon S^1\to E$ be an embedding of the unit circle into the plane. Then the complement of f[S^1] has two connected components, one bounded and one unbounded; and the complement of f[S^1] is homeomorphic to the complement of S^1 .

The Jordan-Brouwer Theorem. Let $f\colon S^n\to E^{n+1}$ be an embedding of the unit n-sphere into the n+1-dimensional space. Then the complement of f[S^n] has two connected components, one bounded and one unbounded.

These theorems are closely related and seems weird why are they not combined into one. Probably, to underline that the following is wrong:

The Wrong Theorem. Let $f\colon S^n\to E^{n+1}$ be an embedding of the unit n-sphere into the n+1-dimensional space. Then the complement of f[S^n] has two connected components, one bounded and one unbounded; and the complement of f[S^n] is homeomorphic to the complement of S^n .

Thus, Jordan Curve Theorem (J.C.T) generalizes to the Jordan-Brower Theorem (J.B.T) (I will point out how to prove it using Brouwer’s Fixed Point Theorem), but the stronger theorem, The Jordan Schönflies Theorem (J.S.T.) does not generalize to the Wrong Theorem, because it is wrong. This video on YouTube gives a counter example, the Alexander Sphere. (For some reason I cannot embed it here.)

It is intuitively quite obvious that after the limit process of the video is done (one can formalize it using countable union or countable intersection depending on the preferred way to do that), the surface is an embedded sphere, which satisfies J.S.T.. On the other hand the fundamental group of the complement is not trivial. Which means that you can flip a rope around one of the horns of the surface and if you glue the loose ends of that rope together, you cannot (homotopically) disconnect the rope from the surface. Thus the complement cannot be homeomorphic to the complement of S^n . Why? Because the homeomorphism would somehow map the flipped rope to one of the connected components of the complement of S^n , where it can be undone (freed from the surface) and shrinked to a point. This would give (by the homeomorphism’s inverse) a way to disconnect the rope from the Alexander Sphere.

Comments (0)

Euler’s Riddle

By Vadim Kulikov June 16, 2010 – 5:10 in Algebra, Mathematics, Recreation, Wednesday Problem

Please comment your solutions, questions and remarks..

I found in a recreational book the following riddle attributed to Leonard Euler. The book gives a clumsy solution involving solutions of quadratic equations, a lot of fractions and half a page of text. I challenge you to find an elegant solution! (I am sure elegance was Euler’s intension!),

Euler’s riddle: Two traders went to a market to sell eggs. Each of them had her own eggs and they had 100 eggs altogether. After selling all their eggs they earned the same amount of money. One of them says to the other: If I had as many eggs as you had, I would have earned 15 Kreuzers. Then the other replies: If I had as many eggs as you had, then I would have earned $6\frac{2}{3}$ Kreuzers. How many eggs did each of them bring?

Level 1/5 for a solution, 2/5 for an elegant one, 3/5 for a solution more elegant than that I have in mind.

Comments (0)

Apology

By Vadim Kulikov June 9, 2010 – 19:53 in Meta

There was a generous break in the posts lately and I apologize for that. I promise to counterbalance this by posting some really tough stuff! soon… ;-)

Comments (1)

How To Find Your Way Out of Woods

By Vadim Kulikov June 9, 2010 – 19:33 in Geometry, Mathematics, Recreation, Wednesday Problem

Please comment your solutions, questions and remarks..

A lumberjack got lost in a forest. He knows that the area of the forest is S and that there are no meadows in the forest. Show that he can get out from the forest after walking at most

$2\sqrt{\pi S}$

It is assumed that the lumberjack can walk along a curve of a given shape.

2/5

Caution: This is modified since first published. The originally published riddle was not solvable.

Comments (0)

The Most Important Relation In Mathematics 1

By Vadim Kulikov June 7, 2010 – 8:38 in Education, Foundations, Mathematics, Philosophy

Part 1: Basics

In this and few following posts I will argue that not only in mathematics, but in all human reasoning, the role of equivalence relations is crucial. The notion of an equivalence relation is the key to any abstractions; the only way to classify things in one’s mind; the ultimate way to simplify reasoning whenever it is natural and reasonable to do so.

On that basis I encourage to emphasize the notion of equivalence relation in the basic courses on mathematics and philosophy.

Because of the wideness described above, I will explain equivalence relations from scratch so that non-mathematicians can follow.

This first post in this series is devoted to just the mild basics of the subject, merely for those who are not familiar with equivalence relations.

The definition follows. If X is a set of objects, then $x\in X$ means that x is one of the objects in X (a member or an element of X). A relation R between the elements of a set X is called an equivalence relation if it is
(S) Symmetric: for all $x, y \in X$ the element x is related to y (denoted xRy) if and only if y is related to x (yRx).
(R) Reflexivity: Each element $x\in X$ is related to itself: xRx.
(T) Transitivity: For all $x,y,z\in X$ , if xRy and yRz, then xRz.

Suppose we have a set X and an equivalence relation R on that set. Given an element $x\in X$ , the equivalence class of x, denoted [x], is the set of all elements that are related to x. It follows easily from (S), (T) and (R) that for $x,y\in X$ either [x]=[y] or there are no common elements in [x] and [y], i.e. $[x]\cap [y]=\varnothing$ .

Examples

Comments (0)

Jouko Väänänen’s Birthday Meeting

By Vadim Kulikov May 6, 2010 – 21:44 in Education, Logic, Meta

Let me advertise the meeting (in September 2010) whose web page I am maintaining:

http://www.helsinki.fi/~kulikov/jouko/

All logicians, are most welcome to the meeting! Other people are also welcome! :-P

There will be two tutorials before the conference: by Andres Villaveces from Bogota and by Boban Velickovic from Paris.

Comments (0)

If You Beg For Money, You Might End Up Doing Math

By Vadim Kulikov May 5, 2010 – 14:04 in Education, Meta, Recreation, Wednesday Problem

Yesterday I was walking around with my friend in a market hall. Two girls of age 15 asked us whether we could give them 40 euro cents. It is about $0.6. We asked them what could we gain in response. They didn’t figure anything out (and the girls refused to sing for us), we proposed that they should solve some mathematical problem. Our mistake was probably that we didn’t invent a problem that would suit the girl’s level (*). I suppose first we gave a bit too hard a problem and then maybe a too easy one. They solved the easy one and we gave them the money. I regret a bit about (*) and that we didn’t keep them thinking a bit longer. Maybe that was the only chance to think in their lives. That is why I decided to write down some classical problems that are simple enough to be understood by someone who is 15 and has low mathematical self-esteem. The last of the following problems is the one that the girls were able to solve.
Read More »

Comments (3)

Prisoner’s problem 4

By Vadim Kulikov April 28, 2010 – 17:20 in Combinatorics, Mathematics, Recreation, Wednesday Problem

Tagged Prisoners' problems

See the Wednesday Problem’s vague rules here.

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

Comments (0)

Prisoner’s problem 3

By Vadim Kulikov April 21, 2010 – 1:58 in Combinatorics, Mathematics, Recreation, Set Theory, Wednesday Problem

Tagged Prisoners' problems

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 his or her own hat, but sees the other’s hats. Then everyone have to guess his or her own hat’s colour. Those who guess correctly are given freedom. The prisoners knew about this event in advance and have had some time to agree on a strategy. How can they agree such that

(a) infinitely many of them get freedom? Level 1/5
(b) only finitely many of them stay in the prison? 4/5

The prison looked like this btw:
infinite prison

Comments (1)

Prisoner’s problem 2

By Vadim Kulikov April 14, 2010 – 5:37 in Mathematics, Probability, Recreation, Wednesday Problem

Tagged Prisoners' problems

Please comment your solutions, questions and remarks..

Consider a prison with several millions prisoners. The head of the prison arranges the following challenge to the prisoners. One prisoner at a time will be called to a room with a lamp. The lamp is always on or off and the prisoner may change the state of the lamp or leave it as it was. Every hour a randomly picked prisoner is called to the room. Whenever a prisoner is in the room, he or she may say “now everybody have been in this room”. If this prisoner is right, everybody get freedom. If not, the game stops immediately and everybody are hanged. What is the strategy for the prisoners to agree, before the challenge starts, so that they all get freedom with probability 1?

Level 3/5

prisoner & lamp

Comments (0)

Prisoner’s problem 1

By Vadim Kulikov April 7, 2010 – 4:21 in Combinatorics, Mathematics, Recreation, Wednesday Problem

Tagged Prisoners' problems

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 prisoners and tells them the following. Tomorrow all of you will come to the yard in a queue, all of you gazing forward. I will put a hat on each of your heads. A black or a white hat. No one of you will know which one is on their own head but everyone will see those hats that are in front of them. Then I will ask each of you, starting from the last in the queue, which is the colour of his or her hat. If he or she gives the wrong answer, I shoot him/her with a bazooka.

The prisoners have some time to agree on a strategy before they have to come to the yard. Once they are there, they cannot communicate except for that they can hear what the previous prisoners in the queue answer and whether or not they are killed with a bazooka.

What is the best strategy they can agree on?

(Thanks to Yilong Li for this problem)

Level 2/5
bazooka Prisoners in a queue

Comments (3)

LHC And Artifial Inteligence Going Beyond Us

By Vadim Kulikov April 1, 2010 – 0:03 in Meta, Philosophy

Two days ago, people of the CERN Control Centre and many other scientists in the world celebrated the successful collisions of LHC. LHC is a device mainly to obtain physical data about the microscopic world, but in fact also mathematicians were waiting for it.

The only reason, why mathematical problems are still solved by human mathematicians, but not machines, is because of the lack of computational power. Imagine a computer that is able to check all valid proofs of length $10^{74}$ starting from the axioms of ZFC* in less than a year. Here ZFC* means the axioms of set theory that have quantifier rank less than $10^{30}$ . This is far beyond any human mathematician has ever used or encountered. All known proofs are estimated to be shorter than $10^{24}$ digits if written in the formal language of set theory. And certainly no axiom of quantifier rank more than $10^{30}$ has ever been really needed for a proof

Such huge computational power has only been a dream. But in fact, the Large Hadron Collider gives the possibility of such a quantum computer I described above! This not only guarantees a machine-check for all known theorems, but will also provide answers to many open mathematical questions, maybe even such as P=NP, not even mentioning calculations of the digits of pi etc.. This Computer started running the same minute, LHC provided its first collisions. There are several reasons, why this has not been published in press: such possibilities will change the research of contemporary mathematics to completely new areas. This will change lives of many people and in particular affect the global economics, as there will be vastly more predictions about it, and as we know such predictions affect reality.

Just wait for a few months, and you will see how the number of mathematical results will grow.

Comments (2)

The Drunken Finn

By Vadim Kulikov March 31, 2010 – 18:01 in Meta

I just learned that the guy I talked about here, the one who goes randomly left or right, is known as the Drunken Finn.

:-)

Comments (0)

How Many Good Colorings?

By Vadim Kulikov March 31, 2010 – 6:02 in Algebra, Combinatorics, Mathematics, Wednesday Problem

Please comment your solutions, questions and remarks..

Suppose G is a graph in which each vertex has three neighbours, for example:

A three valent graph

Suppose we have three colors, red green and blue, with which we want to color the edges of the graph. For instance like this:

A three valent graph

Call such a coloring good if at each vertex either three different colors meet or only one color occures. Thus the coloring in the picture above is not good, but the following two are good:

A three valent graph

Show that the number of good colorings of G is 3^n for some $n\in \mathbb{N}$

Level 3/5 (Maybe 4/5 or even 5/5 depending on your mathematical prerequisites.)

Comments (0)

Nasty Finite Combinatorics

By Vadim Kulikov March 24, 2010 – 7:51 in Combinatorics, Mathematics, Set Theory, Wednesday Problem

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, $n\in\mathbb{N}$ . Suppose that $K_1,\dots,K_n,K_{n+1}$ are subsets of K. Show that there exist $I\textrm{ and }J\subset \{1,\dots,n,n+1\}$ such that

$I\cap J =\varnothing$

$I\cup J\ne \varnothing$

and

$\displaystyle \bigcup_{i\in I}K_i =\bigcup_{j\in J}K_j$

4/5

Hint below printed in white, so that if you are using a common OS with common settings, you have to drag with your mouse over the text in order to see it:
Read More »

Comments (0)

Andre’s Reflection Method

By Vadim Kulikov March 20, 2010 – 13:09 in Combinatorics, Mathematics, Probability, Recreation

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 is a sequence $\bar a=(a_1,\dots, a_n)$ where a_i can be either 1 or -1 with equal probability. That is, at each step we either go right (+1) or left (-1); a_1 is the first step, a_2 the second and so on. Suppose a fellow stands at some natural number and then executes such a random walk: an n-step walk, and at each step goes left or right by one:

You standing on the number line

For example, if the starting position is the picture above and the walk is given by (-1,-1,1,1,1,-1,-1) , then you end up at 4.

Question: Suppose a fellow stands at the positive natural number k and makes a random walk of length n which ends up back at k. What is the probability that the fellow never visited zero? (n is assumed to be even, or otherwise it is impossible to get back to k)

This problem seems to be originated as the so-called Ballot Problem: Suppose A and B are candidates for office and there are 2n voters, n voting for A and n for B. In how many ways can the ballots be counted so that B is never ahead of A? To formulate this in the previous setting, let a vote for A be +1 and a vote for B -1. The random walk is now determined by the order of counting the votes and the starting point is 1. If you visit zero during the counting, then B is necessarily ahead of A at this step. Note that since the voters voted equally for A and B, the walk ends up at 1.

More generally one can of course ask: if 1 occurs with probability p and -1 with probability 1-p in the walk and we know that the walk starts at k>0 and ends at m>0, what is the probability that the walk does not visit zero? The answer below generalizes easily to this extend.

Answer: André’s Reflection Method. Désiré André (1840-1917)
Read More »

Comments (1)

Back To College

By Vadim Kulikov March 17, 2010 – 8:07 in Calculus, Mathematics, Wednesday Problem

Please comment your solutions, questions and remarks..

Show that the following inequality holds for all k>0 and $x\in \mathbb{R}$ :

$e^x>kx-k\ln k.$

Level 1/5

Comments (2)

Even More On BFPT

By Vadim Kulikov March 13, 2010 – 2:01 in Combinatorics, Mathematics, Topology

Tagged Brouwer's Fixed Point Theorem

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 the disadvantage that it uses approximation by piecewise linear maps, although it retains the elementarity.

Comments (3)

How Many Are True?

By Vadim Kulikov March 10, 2010 – 5:45 in Logic, Mathematics, Recreation, Wednesday Problem

Please comment your solutions, questions and remarks..

At most 1 statement of this post is true.
At most 2 statements of this post are true.
At most 3 statements of this post are true.
At most 4 statements of this post are true.
At most 5 statements of this post are true.
At most 6 statements of this post are true.
At most 7 statements of this post are true.
At most 8 statements of this post are true.
At most 9 statements of this post are true.
At most 10 statements of this post are true.
At most 11 statements of this post are true.
At most 12 statements of this post are true.
At most 13 statements of this post are true.

Comments (1)

walksonmath.net

By Vadim Kulikov March 7, 2010 – 19:21 in Meta

Now this address redirects here. Also whitemath.org still redirects here.

Comments (0)

Solution To The Previous Problem

By Vadim Kulikov March 6, 2010 – 18:57 in Calculus, Mathematics

Exceptionally I will present a solution to the previous Wednesday Problem. Only not shall I present any simplest solution but a cool one.

The question was the following.

Suppose a function $f\colon \mathbb{R}\to\mathbb{R}$ has the property that given any reals a < b, the function $f\restriction [a,b]$ takes all possible values between f(a) and f(b). Call this property iv-property (for intermetiate value). Can a function with iv-property be discontinuous?

The solution I give here shows that it can be discontinuous at every point.

(And not measurable).

Comments (3)

By Vadim Kulikov March 6, 2010 – 13:31 in Meta

We’ve got a new name. The new name attempts to give a better impression of the nature of this blog. The posts mostly concern those mathematical entities that are currently dominating my mind in addition to my main research. Includes discussions with colleagues, students, friends, articles that I happen to read, books, ideas and so on. In three words: Walks On Math.

In order to celebrate this I will post in the near future another post concerning random walks.

The address www.whitemath.org still redirects here, but there’s going to be www.walksonmath.net soon.

Update: walksonmath.net works now.

Comments (0)

Intermediate Value Functions

By Vadim Kulikov March 3, 2010 – 6:20 in Calculus, Mathematics, Wednesday Problem

Please comment your solutions, questions and remarks..

A continuous function $f\colon\mathbb{R}\to\mathbb{R}$ on the real numbers has the following property: Given any two reals a<b, the function f gets all possible values between f(a) and f(b) on the interval [a,b] (i.e. the function $f\restriction [a,b]$ takes all possible values between f(a) and f(b)). Without words:
$\forall a,b\in\mathbb{R}$
$\quad\forall x(f(a)\leqslant x \leqslant f(b)\lor f(b) \leqslant x\leqslant f(a))\rightarrow (\exists y\in [a,b] f(y)=x)$

Let us call functions with the described property iv-functions (for intermediate value).

Is an iv-function necessarily continuous?

2/5

Comments (1)

Sorry I Am Late

By Vadim Kulikov February 26, 2010 – 13:58 in Logic, Recreation, Wednesday Problem

Please comment your solutions, questions and remarks..

How many of the statements below the line are true?

2/5

————

This post was not published on Wednesday 24. February 2010
There are at least 2 true statements in this post (after the line)
There are at least 3 true statements in this post (after the line)
There are at least 4 true statements in this post (after the line)
There are at least 5 true statements in this post (after the line)
There are at least 6 true statements in this post (after the line)
There are at least 7 true statements in this post (after the line)
There are at least 8 true statements in this post (after the line)
There is exactly one true statement in this post (after the line)

Comments (3)

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

By Vadim Kulikov February 21, 2010 – 9:10 in Combinatorics, Games, Mathematics, Topology

Tagged Brouwer's Fixed Point Theorem

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

Theorem (Jordan’s Curve Theorem) Let $f\colon S^1\to \mathbb{R}^2$ be an embedding of the unit circle to the plane. Then $\mathbb{R}^2=A\cup B\cup C$ where A and B are open and disjoint and $\partial A=\partial B=C=f[S^1]$ .

Two weeks ago I presented a relatively simple proof of BFPT. Today I will introduce the game Hex and show that at least one player always wins (the game cannot end such that none of the players is in a winning position). Then I will show how this implies BFPT. Then I will show how BFPT implies a version of Jordan’s Curve Theorem and then show how this in turn implies that there is always exactly one winner in Hex.

So the table of contents is:

(1) At least one player wins in Hex implies
(2) a simple proof of BFPT implies
(3) a version of Jordan’s Curve Theorem implies
(4) that at most one player wins in Hex.

In my opinion this is mind-explodingly cool. Some reference:

The Game of Hex and the Brouwer Fixed-Point Theorem
David Gale, The American Mathematical Monthly, Vol. 86, No. 10 (Dec., 1979), pp. 818-827.
The Jordan Curve Theorem Via the Brouwer Fixed Point Theorem
Ryuji Maehara, The American Mathematical Monthly, Vol. 91, No. 10 (Dec., 1984), pp. 641-643 .

The game Hex

Source: HexWiki, licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.

Comments (2)

Pinocchio Is Omnipotent

By Vadim Kulikov February 19, 2010 – 12:57 in Logic, Mathematics, Philosophy, Recreation

What if Pinocchio says: “My nose will grow now?”

I’d rather write my own post about it, but can’t make better than this wonderful combination of picture & text

Thanks to Rami Luisto for pointing out.

In case the link above is not permanent, I stole the image with the text and you can see it below.

Comments (6)

More Tricks With Triangulations

By Vadim Kulikov February 17, 2010 – 8:15 in Geometry, Mathematics, Recreation, Wednesday Problem

Please comment your solutions, questions and remarks..

I learned this riddle from Sergei Chmutov. It is also a problem concerning triangulation and sharp angled triangles. Suppose we have a triangulated regular polygon with odd number of edges. The vertices of the triangles must coincide with the vertices of the polygon like in the picture below. Show that exactly one triangle has only acute (sharp) angles and all other triangles have at least one obtuse (blunt) angle.

Triangulated heptagon

$\frac{5}{2}/5$

Comments (0)

Stable Marriages

By Vadim Kulikov February 14, 2010 – 3:29 in Combinatorics, Mathematics, Recreation

Happy Valentines Day!

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 of preference and each woman ranks all men in order of preference. We could formalize this as follows. Denote the set of men by M and the set of women by W. Each man $m\in M$ picks a bijection $b_m\colon W\to \{1,\dots,n\}$ and each woman $w\in W$ picks a bijection $b_w\colon M\to \{1,\dots,n\}.$ The bigger number is assigned by b_m to the higher ranks and vice versa.

Good News: It is possible for all of them to get married such that if $m\in M$ and $w\in W$ are not married to each other then either m prefers his wife to w or w prefers her husband to m.

This is called the Stable Marriage Theorem and was proved by D. Gale and L. S. Shapley in their 1962 published article
College Admissions and the Stability of Marriage
in The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), pp. 9-15.

Of course marriage is not the only application of this theorem and the initial interest of authors was the question of how to pair applicants with colleges taking into account that each applicant has a preference list of the colleges and each college has a preference list of the applicants. Also it appears that the algorithm given by Gale and Shapley has been widely applied to the assignment of graduating medical students to their first hospital appointments.

Happy Valentines Day!

The proof Read More »

Comments (0)

Triangulation

By Vadim Kulikov February 10, 2010 – 5:52 in Geometry, Mathematics, Recreation, Wednesday Problem

Please comment your solutions, questions and remarks..

In the last week’s many in one post I explained what is a triangulation. Can you triangulate a square using only sharp angled triangles (i.e. triangles whose all angles are < $\pi/2$ )? For example the triangulation in the picture is not as needed:

A triangulated square

I heard this from Marcin Sabok.

Comments (0)

Brouwer’s Fixed Point Theorem: Many in One Post

By Vadim Kulikov February 3, 2010 – 14:42 in Combinatorics, Mathematics, Topology, Wednesday Problem

Tagged Brouwer's Fixed Point Theorem

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

There are funny interpretations of this theorem.

The traditional proof of this theorem is rather difficult and despite I have attended courses on algebraic topology, I have never really understood it in depth. Sometimes this result is even quoted as intuitive but hard to prove and is celebrated as a triumph of algebraic topology. The hardest part of the proof is to show that $\pi_n(S^n)\ne \{0\},$ let alone defining homotopy groups which takes about a month in a regular homotopy theory course held in our department; and I am not even mentioning the amount of necessary group theoretical and topologican prerequisites.

Spending some time on the internet though, one is able to find simpler proofs. From now on also in this blog. The easy proof I will present here uses the Handshaking Lemma that has been as a Wednesday Problem in this blog. In addition to that, it uses the fact that any sequence in a closed unit ball has a convergent subsequence. These are fairly meagerer prerequisites than those mentioned above.

Since BFPT implies $\pi_n(S^n)\ne \{0\},$ this is also a way to prove that.

Comments (2)

The Coin Placing Game.

By Vadim Kulikov January 27, 2010 – 3:38 in Games, Recreation, Wednesday Problem

See the Wednesday Problem’s vague rules here.

Some games again. According to Sam, from whom I heard this riddle, it divides people into cathegories i) those who realize the answer immidiately and ii) those who think quite long about it.

The game board is a round table of diameter d>0. The two players place one after another coins of diameter s>0 on the table. The coins cannot overlap. If there is no place left on the table to place the next coin, the player whose turn it is, loses. Which one of the players has a winning strategy?

$2\frac{1}{2}/5$

Comments (5)

TopoLogic

By Vadim Kulikov January 25, 2010 – 18:16 in Logic, Mathematics, Topology

The Continuum Hypothesis trilogy will continue later. Today I’ll recall some discussion I made a year ago or so in the student seminar.

I guess someone would say that it is surprising, how closely related these two branches of mathematics — topology and logic — are.

Applications of logic to topology include non-standard homology theory (compare to non-standard analysis), independence results, for example properties of Cech-Stone compactification of N depend on continuum hypothesis to some extend. Also many set theoretical constructions serve as counter examples in topology. For example $\omega_1$ is sequentially compact, but not compact space.

I am going to give here an example of an application of topology to logic. That probably sounds even more hc, becase people tend think of logic as the foundation of mathematics. That is a good point, but note that logic is also done in ZFC, as any other branch of mathematics.

Applications of topology to logic include Stone spaces (spaces of types — which appear Stone-Cech compactifications of certain spaces), Baire cathegory theorem is equivalent with the axiom of Dependent Choice (a weak version of the Axiom of Choice) and is considered one of the most important mathematical theorems by the leading logician of our department; determinacy of games depends on topological (Borel/Analytic/etc) properties of certain sets…

Comments (0)

How Old Are The Kids?

By Vadim Kulikov January 20, 2010 – 6:48 in Combinatorics, Recreation, Wednesday Problem

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 supervisor answers: three. The student asks about their ages and the supervisor replies: “If you multiply their ages, you get 36 and if you sum the ages, you get the number of our house.” The student thought for a while and said “There is something you didn’t tell” and the supervisor replied “Oh yeah, the oldest one plays piano.” Then the student immidiately realizes the ages.

Do you?

2/5

Comments (2)

Continuum Hypothesis III

By Vadim Kulikov January 18, 2010 – 17:21 in Foundations, Mathematics, Philosophy, Probability, Set Theory

Tagged Continuum Hypothesis Trilogy

Suppose you pick randomly a real number. What is the probability that it equals to 1? The probability is zero. Suppose $X\subset [0,1]$ is a countable subset of the unit interval. What is the probability that a randomly picked real from the unit interval is in X? Again, it is zero, because the Lebesgue measure of X is zero, X being countable. Suppose now, that we are having a function

$f\colon [0,1]\to \{\text{Countable subsets of }[0,1]\}.$

This means that f attaches a countable set of reals in the unit interval to each real in that interval. Let us consider the following statement

Feiling’s axiom. For every f (as above), there exist $x\in [0,1]$ and $y\in[0,1]$ such that $x \notin f(y)$ and $y \notin f(x)$ .

Let us see what does it mean if Freiling’s axiom does not hold. If it does not hold, then there is a function f attaching countable sets of reals to reals with the property that given two random reals x and y, either $y\in f(x)$ or $x\in f(y)$ . This is supposed to be counterintuitive according to Freiling. Indeed, suppose we choose x first. Then because f(x) is countable, the probabilty for y to be in f(x) is zero. On the other hand, if y is chosen first, then the probability for x to be in f(y) is zero! But one of them happens certainly, provided Freiling’s axiom fails.

Freiling proposed this as an argument against Continuum Hypothesis, since

Theorem. The following are equivalent
1. Continuum Hypothesis
2. Freiling’s axiom fails.

In the abstract to his paper Axioms of Symmetry: Throwing Darts at the Real Number Line (see below for exact reference), Freiling writes boldly without hiding his believes:

We will give a simple philosophical “proof” of the negation of Cantor’s continuum hypothesis. [...] We will assume the axioms of ZFC together with intuitively clear axioms [...that] are justified by the symmetry in a thought experiment throwing darts at the real number line. We will in fact show why there must be an infinity of cardinalities between the integers and the reals. We will also show why Martin’s Axiom must be false, [...] Following the philosophy — if you reject CH you are only two steps away from rejecting the axiom of choice.

The proof of Freiling’s Theorem is quite simple. Read More »

Comments (2)

The Monk

By Vadim Kulikov January 13, 2010 – 7:12 in Calculus, Recreation, Wednesday Problem

Please comment your solutions, questions and remarks..

The posts have been a bit advanced lately. Let us lighten the atmosphere by this riddle which admits a simple solution, though mathematicians tend to use calculus in solving it:

An Indian monk lives near a mountain. He wakes up in the morning at 6 a.m. and goes up the mountain. The journey takes six hours and at noon he is on the top. Then he meditates 18 hours and when it is 6 a.m. again, he goes down following exactly the same route as on the way up and it also takes six hours. Show that there is a point on the route which is passed by the monk at exactly the same time on both days.

1/5

This image is licensed under the Creative Commons Attribution-ShareAlike 2.5 License. I took from Wikipedia.

Comments (0)

Continuum Hypothesis II

By Vadim Kulikov January 10, 2010 – 6:16 in Calculus, Foundations, Mathematics, Set Theory

Tagged Continuum Hypothesis Trilogy

Differentiability of Space Filling Curves

A Peano curve is a surjective (onto) function $f\colon\mathbb{R}\to\mathbb{R}^2$ . Apparently such an f cannot be smooth. To see this consider the restrictions of this function to closed intervals $f\restriction [n,n+1]$ . By smoothness and compactness the image of each of them under f has finite length, and hence measure zero in the 2-dimensional Lebesgue measure of $\mathbb{R}^2$ (twice continuously differentiable is enough for this argument). Thus their countable union, the range of f, cannot be the whole plane.

On the other hand, f can be continuous, see the exercise I gave in the end of the post about continued fractions.

Let us try something between smooth and continuous. Denote f=(f_1,f_2) , where f_1 and f_2 are the co-ordinate functions. Is it possible that at each point either or has a derivative?

Theorem The following are equivalent
1. Continuum Hypothesis
2. There exists a Peano curve such that at each point one of the components is differentiable.

Reference: Michal Morayne Colloq. Math. 53 (1987), 129-132

UPD: The argument as it is below uses the assumption that a set whose complement has measure zero has the size of continuum. This is true under Martin’s axiom, but seems to me independent from ZFC. By putting one more assumption on the Peano curve the proof below goes through: assume that there is are open intervals such that in the function is differentiable and the derivative is non-zero for k=1,2.

For a proof Read More »

Comments (0)

White Math Days

By Vadim Kulikov January 9, 2010 – 17:00 in Meta

We had literally white Mathematics Days in Jyväskylä.

Snowy landscape 1

For more pictures Read More »

Comments (2)

MAD families

By Vadim Kulikov January 6, 2010 – 6:02 in Combinatorics, Mathematics, Set Theory, Wednesday Problem

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 dual to the earlier problem.

Suppose A is a family of subsets of natural numbers. A is called almost disjoint (AD) if the intersection of any two elements of A is finite. For example a family of subsets in which all elements are pairwise disjoint is AD. The latter can be at most countable. Show that an almost disjoint family of subsets of natural numbers can be

(a) uncountable
(b) of size continuum (i.e. as big as the power set of natural number)

4/5

A hint below; after the hint the level becomes 2/5 I guess.

Comments (0)

Continuum Hypothesis I

By Vadim Kulikov January 3, 2010 – 8:04 in Foundations, Mathematics, Philosophy, Set Theory

Tagged Continuum Hypothesis Trilogy

This is the first part of the forthcoming trilogy in four parts. The trilogy will be devoted to the understanding of the Continuum Hypothesis by looking at some statements that are equivalent to it.

In this post I just expose some philosophical background concerning the foundations of mathematics, the Continuum Hypothesis and its independence. So if you are a set theorist, then you should probably do something else.

Comments (0)

New Year Report

By Vadim Kulikov January 2, 2010 – 16:56 in Meta

I started this blog November 18:th last year, almost one and a half months ago. I want to thank Mittag-Leffler Institute for providing the inspiring atmosphere which enabled me to do so. Since then White Math has had

461 visits by
196 visitors from
17 countries, the top three of which are

Finland
Sweden
United States

No visits from the southern hemisphere. Yet.

Thank you for reading W.M!

Comments (0)

Happy Transition 2009-2010!

By Vadim Kulikov December 30, 2009 – 6:43 in Mathematics, Wednesday Problem

Please comment your solutions, questions and remarks..

Which one is bigger:

$\sqrt{2009 + \sqrt{2010}} + \sqrt{2010 + \sqrt{2009}}$
or
$\sqrt{2009 + \sqrt{2009}} + \sqrt{2010 + \sqrt{2010}}$ ?

(If you use a calculator, show that it does not lie)

2/5

Happy New Year, folks!

Comments (0)

My Brain Is Open, the mathematical journeys of Paul Erdös: A Book Review

By Vadim Kulikov December 27, 2009 – 9:02 in Book & Article Reviews, Ramsey Theory

During my stay at the Mittag-Leffler Institute I read this book written by Bruce Schechter. The book is written in accessible English, so that I had no problems reading it though English is not my mother tongue. It tells the life story of Paul Erdös almost chronologically beginning from his childhood in Budapest to the end of his extraordinary career full of traveling from place to place.

In the story telling, one thing I found uncomfortable. The author quite often slides away from his main topic. For instance in the second chapter called Proof the author spends some time telling stories from Friedrich Gauss’ childhood. The story is interesting, no doubt, but it was not really fitting the context, and moreover it is a well known story. In the same chapter the author dives also into the ancient history of mathematics.

What I liked is the really good picture of Paul Erdös. The author cites him a lot and manages somehow to transfer the feeling which was maybe present when Paul was around. The latter is quite impressive since the author never met Erdös. This side of the book is reviewed in the review behind this link. One particular thing in this spectrum, is the Erdös’ attitude to death; merely his own death. He realised at an early age that he will die and after that he never dismissed that fact. He would say “Let us continue our discussion tomorrow. If I live.”. At some stage he started to add a couple of new letters to his signature every five years. When he turned 75 the signature became Paul Erdös PGOMLDADLDCD which means Paul Erdös Poor Great Old Man, Living Dead, Archaeological Discovery, Legally Dead, Counts Dead. These words have some external meaning, for instance “Counts Dead” comes from the fact that at the age of 75 the members of Hungarian Academy of Science were not counted as working members any more.

Let me quote one of the stories I liked. Erdös was around his eighties at that time.

Erdös needed a cornea transplant to restore vision to one of his eyes. As he was leaving Memphis, a donor became available. At first Erdös did not want to delay his travels for the operation, but after a lengthly argument his friends convinced him that his eyesight was more important. Nevertheless, he insisted on taking a pad with him to the operating room to continue his calculations. When the surgeon saw this he said, “You won’t need that. I’ll be working on your eye.”Erdös replied, “I’ll do math with the other eye.”

The author of the book also gives some insights to mathematics in a popular way. Read More »

Comments (0)

Joulupukki Is Fair: Your Christmas Riddle

By Vadim Kulikov December 23, 2009 – 2:46 in Mathematics, Recreation, Wednesday Problem

Please comment your solutions, questions and remarks..

Joulupukki came to a kindergarten. He had some number of candies to give to the children. He saw that there are more boys than girls and that he could divide the candies evenly among the girls and also among the boys. On the other hand he could divide the candies evenly among all the children and that is what he did. Each child got three candies.

How many candies would each girl get, if Joulupukki divided the candies only among the girls?

Merry x-math, everyone!

Comments (0)

The Game Discrete

By Vadim Kulikov December 20, 2009 – 6:32 in Combinatorics, Games, Mathematics, Recreation

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

Game board for the game discrete

Comments (0)

A Pizza Pun

By Vadim Kulikov December 17, 2009 – 23:37 in Mathematics

$\textrm{Suppose we have a pizza with radius }z$
$\textrm{ and thickness }a\textrm{. Then the volume is}$

$\pi \cdot z \cdot z \cdot a.$

Comments (0)

Handshaking Lemma

By Vadim Kulikov December 16, 2009 – 5:33 in Combinatorics, Recreation, Wednesday Problem

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 deep applications. I’ll get back to it!

Comments (2)

Where Do Random Walks Lead

By Vadim Kulikov December 14, 2009 – 10:01 in Calculus, Mathematics, Probability

Rami Luisto asked the following question:

Pick randomly n unit vectors from the plane, $x_1,\dots,x_n\in \mathbb{R}^2$ . What is the probability that the sum of these vectors has magnitude less than or equal to one, $|x_1+\cdots+x_n|\leqslant 1$ ?

(magnitude = norm = distance from the origin)

I will present here a brute force solution to this problem, but unfortunately the formula for the probability is a complicated iterated integral. I am able to calculate the answer for n=1, n=2 and n=3 . For n=4 it seems complicated. The corresponding values are

1, $\frac{1}{3}$ and $\frac{1}{4}.$

This inspired me actually to force my computer to make some random walks. It made 10^4 random walks of each of the lengths 3,4,5,6,7,8,9,19 and 39. On the basis of that and the mentioned calculations, I conjecture:

The probability for the sum of n>1 random unit vectors to be in the unit disc is $\displaystyle\, \frac{1}{n+1}.$

This is a bit surprising since one would expect the probaility to be proportional to $\frac{1}{n^2}$ , not to $\frac{1}{n}$ , because the area of the possible outputs (end points) grows proportionally to n^2 .

If it is indeed 1/(n+1), the simplicity of that suggests that there could be a simple solution. For instance there are simple solutions to similar problems. If you have a simple solution, then I am interested in it!

Comments (3)

September 2010
M	T	W	T	F	S	S
« Jul
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

Categories

Like this blog? Add to your RSS-feed

Search Walks On Math

Recent Posts

Archives

Tags