If you want to follow my new blog, please visit www.vadimkulikov.org ! A lot of new and unexpected stuff there ! Not only a blog, but also a podcast and much much more.

## (Ir)rational Behavior of Calculation

We had the following set of exercises with a group of secondary school students (in Ressun lukio).

Assume that a and b are positive real numbers. Then assume one of the following:

(i) a and b are both rational
(ii) a and b are both irrational
(iii) a is rational and b is irrational.

Then

(a) can a + b be rational/irrational?
(b) can ab be rational/irrational?
(c) can $$a^b$$ be rational/irrational? In case (iii) consider also $$b^a$$.

This makes 20 exercises total.

Posted in Algebra, Calculus, Education, Mathematics, Wednesday Problem | 1 Comment

## The Product of Topological Spaces Does Not Obey Cancellation

Exercise 1. Find metric topological spaces $$A,B,C$$ such that $$A$$ is not homeomorphic to $$B$$, but $$A\times C$$ is homeomorphic to $$B\times C$$.

Exercise 2. Find path connected metric topological spaces $$A,B,C$$ such that $$A$$ is not homeomorphic to $$B$$, but $$A\times C$$ is homeomorphic to $$B\times C$$.

## Wild Embeddings

Yesterday in a discussion in Komero we concluded that if f is an injective (one-to-one) map from the unit interval [0,1] to the Euclidean plane (or $$\mathbb{R}^n$$), then the interval is homeomorphic with its image. The proof is as follows: we already know that f is continuous and one-to-one, so it remains to show that its inverse is continuous. Continuity is equivalent with the inverse images of closed sets being closed, so the question reduces to the question whether f is closed (maps closed sets to closed). But any closed subset of the unit interval is compact and the image of a compact set is compact and hence closed and we are done.

However, then I carelessly remarked that probably this extends from the interval to whole real line by representing the real line as a counhtable union of compat intervals. This was of course wrong:

Exersice 1. Find a contionuous injective (one-to-one) map from the real line to the plane

$$f\colon\mathbb{R}\to\mathbb{R}^2$$

such that $$\mathbb{R}$$ is not homeomorphic to $$f[\mathbb{R}]$$

Exersice 2. As above but with the requirement that the fundamental group of $$f[\mathbb{R}]$$ is trivial.

## Progress

Posted in Philosophy, Popular | 3 Comments

## 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 and compact spaces
such as the Banach Fixed Point Theorem.

Hence, I am preparing some examples and exercises about metric spaces… and I share one with you:

Exercise: Let $$\mathbb{F}$$ be the class of all finite sets. For every finite sets $$x$$ and $$y$$ let $$d(x,y)=\#(x\triangle y)$$, where $$x\triangle y=(x\setminus y)\cup (y\setminus x)$$ is the symmetric difference and $$\#X$$ is the cardinality of $$X$$. Does $$d$$ define a metric on $$\mathbb{F}$$?

A metric on a class? you say. Well, call $$d$$ a class-metric, if you like!

…and because I am a set theorist:

Fact: Let $$X$$ be any uncountable set (or class) of finite sets. Then there exists an uncountable subset $$Y\subset X$$ such that $$d(x,y)=d(x’,y’)$$ for all $$x,y,x’,y’\in Y$$.

Cool?

## Intellectual Lazyness

My friend gives private mathematics lessons to young pupils, mostly high school students who need some help in their curriculum math. Here is a story about a student of him.

In the beginning the student was lazy to think. Continue reading

Posted in Education, Philosophy, Popular | 4 Comments

## Time Limit: One Minute!

I found this lovely geometrical riddle in Martin Gardner’s book “My Best Mathematical and Logic Puzzles”. The most lovely thing about it is that Gardner gives a time limit: one minute! So, now draw out your stopwatch and read the instructions below. When you are ready, press “SHOW ME” below and the drawing will be revealed. After that you will have only 1 minute (if you wanna beat me, you have 35 seconds)!

Instructions: Click on SHOW ME and start your stopwatch at the same time. You should be exposed to an image of a rectangle inscribed in a circle. The question to be answered is: can you accurately determine the length of the line segment AC? Once you know the answer, glance at your watch to determine how much time is spent.

SHOW ME

It would be fun if post your time as a comment!

## Douglas Hofstadter: I Am a Strange Loop.

Two weeks ago I finished reading Douglas Hofstadter‘s 2007-book I Am a Strange Loop. I haven’t read other Hofstadter’s books and I want to write this review before I read any. My next Hofstadter-book is going to be Gödel Escher Bach — An Eternal Golden Braid which appears to be the most famous of his books, mysterious, misunderstood, deep and long and I can’t wait to start reading it!

The book made a generous impact on me and I recommend its reading to anyone. The book is about conciousness and aims to explain what is the human “I”. Or, what is a soul. Before I opened Hofstadter’s book I often said “What is meant by a soul?”, “What is that soul everybody are talking about?”. After I closed Hofstadter’s book, I understood indeed, at least partially, what this vague concept can mean. Best of all, Hofstadter’s notion of soul is in harmony with both the scientific world view and most soul-discussions out there. Other important mind-buggling questions that I had and that have been given a great chance to be answered (and some of them answered indeed) include those that are listed here.

The author of the book carefully builds analogies after analogies, examples after examples of a concept that he names “a strange loop“. The claim is that “I” is a strange loop, as the title of the book suggests. The loop originates in self-refence and self-representation. That is, a human being’s symbol and representation repertoire is so rich that it can form a symbol, a representation of itself. Accurate that representation need not be, but almost in every thought it is present. “I remember”, “I remember remembering”, “I am here”, “I remember I was here” and so on. The book is not about “I” as word referring to the physical system of our body, it is about the word “I” which refers to our conciousness, our mental activity, our “inner light”, our soul. The author explains via analogies and real and artificial examples, where does this “I” come from, why it feels like being “somewhere” and being us. One delightful (artificial) example is a world in which pairs of persons (which Hofstadter calls pairsons) develope common identities. I hesitated first whether this is a fair analogy, unless… I realized that our brains are formed from two halves which are quite isolated, distinct “brains” with many different functions even.

The language of the book is marvelous, it is pleasant to read. Sometimes (only) Hofstadter is a bit too down-to-Earth with his endless lists of concrete special cases of abstract concepts. They do make the book easier to read for many people, I suppose, but my mathematically adjusted brain would be happy with shorter lists as well.

The book includes a popular exposition of the Gödel’s incompleteness theorem which is one of the best popular expositions of a mathematical theorem I know. It is endowed in the context of the book however, so those who are interested in reading only that part of the book (hopefully not many) will experience some deviations from the main subject. As I already knew a big deal about Gödel’s theorem, I might be a bad judge, but I believe that if the reader is careful and thoughtful, she (or he) will get a good picture of what is going on in Gödel’s ideas.

It is fascinating how deeply Hofstadter is able to analyse entities which are so meagerly explored (human cognition and human brain) and partly the cost that has to be paid is the lack of scientific evindence or a clear-cut sceintific framework which could suggest meaningful experiments… so far!

Posted in Book & Article Reviews, Logic, Philosophy, Popular | 2 Comments

## 0.999999……=1? (continuation)

Earlier, I posted a pretending-to-be-funny discussion on this subject and now continue in a more formal fassion. Namely the dialogue in the previous post didn’t actually arrive to any conclusion as to whether 0.9999… is 1 or not. When you want to prove something in mathematics, you need to look down at the definitions as was suggested in the dialogue. In what follows, I take the axioms of an ordered field with the completeness axiom as the definition of the real numbers, that is the most common definition and equivalent to all others as long as the object is called real numbers and cook up a proof of….. Continue reading

Posted in Calculus, Mathematics | 2 Comments

## Walks on Planets

My gps-equipped radiowave controllable robot Lori is somewhere on the surface of Earth. I order her to drive 100 miles South and she obeys. Then I order her to drive 100 miles West and she obeys. Then I order her to drive 100 miles North and she obeys. After this I look at my gps receiver and notice that Lori is exactly where she was at the beginning of the story.

Classify all points where she could have started given this knowledge

2/5

## 0.999999….. = 1?

The question in the title is constantly discussed on web forums and at our department’s corridors; sometimes even by professional mathematicians and is in fact already quite seen and banal. In our department this question is often raised by the brilliant lecturer of the first-year calculus course as a kind of a test.

The appeal of this question to me is that it is not only a mathematical, but also a philosophical question. Should we derive the answer from our definition of the real numbers or should we cook up the definition of the real numbers according to our answer to the question? In the latter case, how are we supposed to derive the answer then? In the former case which part of the definition of the reals is crucial in that respect? Can that part be dropped or is it a fundamental part of the definition? Finally, what is the connection between sequences of digits and actual real numbers; what is the causes and consequences of these decimal representations?

In what follows I simulate an artifitial discussion:

Teacher: Is 0.999… equal to 1?

Posted in Calculus, Education, Mathematics, Philosophy, Popular | 5 Comments

## 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 immediately picks three of the hats and puts them on the prisoners’ heads. All prisoners see other’s hat colours but not their own. The guard asks them one after another: “what is the colour of your hat?”. The first prisoner replies: “I don’t know”. The second prisoner replies: “I don’t know either”. What does the third prisoner reply and what is his hat colour?

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

## I am back!

Now I can blog again: the ‘publish’ button returned to the user interface. Let me start the new era of Walks on Math by:

* Posting an interview of myself by Heidi Blomqvist that is going to be published by Finnish Academy on the web.

The new name of the blog symbolizes that I am not going to write only about mathematics but also about other things. But math is still going to be a major theme, no worries about that. The interview was done so that I received all the questions by e-mail and then I wrote all the answers.

The interview (oops, it’s in Finnish, sorry):

## A non-associative “group”

Here is what I’ve been doing for the past hour: proving that associativity does not follow from other group axioms including that the left and right inverses are the same and the neutral element is unique.

Let us define the operation * on R, the reals as follows. For each x,y in R let x*y=x+y if x = – y or |x+y| > 1, otherwise define x*y=x if |x|>|y| and x*y=y if |y|>|x|. Now (R,*) has a neutral element, it is 0. Every element has an inverse and it is even commutative, but associativity fails: take x=y=1/4 and z=1. Then (x*y)*z=1/4*z=1.25, but x*(y*z)=1/4*(1.25)=1.5.

Exercise: invent a less ad-hoc example.

Posted in Algebra, Mathematics | 1 Comment

## Why I haven’t blogged

Dear readers, I haven’t blogged for a while. There are several reasons for that of which the main is that my blog server which forces me to use a strange user interface and which doesn’t allow me to access wordpress as I would like to stopped collaborating with me three months ago. I only can post now these “quick” posts which means I cannot use latex for example, nor classify my posts under categories and so on. I will do something upon this in the future, so please be patient.

Other reasons include laziness, vacation and (now gone) lack of enthusiasm.

## 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 every one minute the line is being stretched to be ten times longer than it was. So after one minute the line is 10 m, after two minutes it is 100 m and so on. The rubber grows homogeneously, i.e. the distance both in front and behind the worm grow ten times bigger every minute.

Does the worm ever reach the other end of the rubber line?

There is a video by Vi Hart somehow related to this kind of recreational thinking, in my opinion awesome:

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

## Five groups

Mathematicians are divided into five groups: those who can count to 2, those who can count to 3, those who can count to 4 and logicians.

## Splitting A Rectangle

Find all ways to cut a rectangle into two connected pieces of equal area so that they can be rearranged to get a new rectangle with different dimensions (side lengths) than the orgininal one.

I already know countably many ways.

update: infinitely many.

Posted in Geometry, Mathematics, Recreation, Wednesday Problem | 2 Comments

## Sphere

Pick randomly three points on the unit sphere. The geodesic triangle with these points as vertices divides the sphere into two parts. What is the probability that the north pole is contained in the smaller of these parts?

For instance in the picture the red triangle does not contain the north pole.

Level 3/5

Note: The same question can be raised for an arbitrary convex subset of the plane instead of the sphere. In this case the triangles are normal Euclidean triangles and the “north pole” is a fixed point in the set. In this case the calculation of the probability is much harder. You may consider this as a hint.

## Can Mathematics Solve Philosophical Problems?

This post is not an attempt to answer the question of the subject, but merely to discuss related topics. The idea dates back to the time when I first learned what is the likelihood function in probability theory.

When one encounters a philosophical problem, it is often the case that the problem is stated clearly enough to cook up a paradox in your mind, but vaguely enough not to see any reasonable way to approach the solution. Continue reading

Posted in Philosophy | 2 Comments

## 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. These signs you can put between the numbers

1963

to form mathematical expressions. You must put at least one sign between two numbers and – cannot be used as “negative”, thus -1+9+6+3 is not allowed, but 1-9+6+3 is allowed.

The question is: what is the smallest natural number that cannot be expressed in this way?

Hinty example: 1*9-6-3=0 and (1/9)*(6+3)=1, so the answer is greater than 1.

Level 3.5/5

## 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 a piece over another piece in (any) diagonal direction like this:

Challenge 1:

Is it possible to move four pieces from the lower right corner to the upper right corner like this:

Challenge 2:

Is it possible to move four pieces from the lower right corner to the upper left corner like this:

Challenge 3:

Is it possible to move nine pieces from the lower right corner to the upper right corner like this:

Challenge 4:

Is it possible to move nine pieces from the lower right corner to the upper left corner like this:

????

## 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 dangerous epidemic. But what if it is a news article about something everybody already knew? Can such a news article affect the behaviour of the citizens? Analogously, can our economics theories affect our economics once published? The following mathematical problem and its generalization show that even when the announcement seems to be completely uninformative, it might affect the behaviour of the citizens in a radical way.

Since I want to continue the Prisoners’ Problem series, I reformulate this problem similarly to the previous ones. In the following we assume that the prisoners are very smart which is essential for this argument to work — but clearly such problems may be formulated for populations with limited deductive power and (little) irrationality; such problems would be of much higher complexity of course.

Consider a prison with 60 prisoners. One morning the prisoners are collected to the yard and every one is given a hat. Half of them (30) gets a black and half a white hat, but the prisoners do not know how many there is of a kind. The prisoners see each other’s hats but nobody sees her own hat and they cannot communicate. Every 10 minutes each prisoner can guess her own hat’s colour if she wants. If a guess is correct, the prisoner is freed from the prison and she leaves immediately. We assume that the prisoners never guess unless they are completely sure that they know the correct answer (because they are hanged otherwise). So no one guesses anything… But then the

chairman of the prison gives an announcement: “at least one of you has a white hat!”

What happens? Why?

a more elaborate version:

the chairman announces something non-trivial about the number of the white hats. (Non-trivial means: it is true, but it could be false taking into account the total number of prisoners)

What happens? Why?

## Incomplete Chess Board

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 found out that mice have eaten two opposite angle squares. The chess board looks something like this:

You have also a lot of dominoes with you. One piece exactly covers two adjacent squares of the chess board. Can you fill the chess board with the domino pieces such that they cover exactly all the chess board?

Level: secret.

## 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 using four colours such that any adjoint regions have different colours? (Each region must be coloured into one of the four colours.)

This is often formulated in terms of a map and countries which was the original motivation to study this problem. I did not specify above whether the graph G is finite or infinite. In fact we will prove a theorem connecting these two:

Theorem. If the answer to (Q) is yes for all finite graphs G, then it is yes for all infinite graphs G.

In the proof we will use Compactness Theorem for propositional calculus see this post. Some times Compactness Theorem is used to deduce something about finite objects from knowing something about infinite objects. Some times the other way around. Here we have an example of the latter usage.

## Poisoned Bunnies

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 the poisoned one. The poison doesn’t look or smell different. Apart from that, you have ten bunnies with the following property: if you give a drop of the poison to a bunny, then the bunny will die at midnight. Describe, how would you find out — for sure — in which bottle the poison is, by midnight.

$$\text{Level }\frac{3}{2}/5$$

The image is free.

## 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:

$$p | \binom{p}{k}\qquad \qquad \qquad (*)$$

You can think for a while how would you prove it. There might well be an elementary combinatorial proof of $$(*)$$, although I suspect that it would be rather long and tedious. Fortunately there exists a simple proof using a bit of algebra!:

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

## Irrational Rectangles

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.

5/5

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

Posted in Geometry, Mathematics, Wednesday Problem | 9 Comments

## Uncountable Borel Sets

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

## Ambient Isotopy

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$$ ($$I$$ is the unit interval) such that for all $$t\in I,\,H\restriction(X\times \{t\})$$ is an embedding from $$f$$ to $$g$$, 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

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:

and the following embeddings of graphs are not equal:

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):

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):

## Around Jordans Curve Theorem I

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.

## Euler’s Riddle

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.

Posted in Algebra, Mathematics, Recreation, Wednesday Problem | 2 Comments

## Apology

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… ;-)

Posted in Meta | 1 Comment

## How To Find Your Way Out of Woods

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.

Posted in Geometry, Mathematics, Recreation, Wednesday Problem | 3 Comments

## The Most Important Relation In Mathematics 1

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

Posted in Education, Foundations, Mathematics, Philosophy | 3 Comments

## Jouko Väänänen’s Birthday Meeting

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.

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

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.

Posted in Education, Meta, Recreation, Wednesday Problem | 3 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

## Prisoner’s problem 3

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:

## Prisoner’s problem 2

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’s problem 1

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

## LHC And Artifial Inteligence Going Beyond Us

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.

Posted in Meta, Philosophy | 1 Comment

## The Drunken Finn

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

:-)

## How Many Good Colorings?

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 graph. For instance like this:

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:

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.)

## Nasty Finite Combinatorics

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:

## 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 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 $$k$$ and then executes such a random walk: an n-step walk, and at each step goes left or right by one:

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)

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

## Back To College

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

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

Level 1/5

Posted in Calculus, Mathematics, Wednesday Problem | 2 Comments

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

## How Many Are True?

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.

Posted in Logic, Mathematics, Recreation, Wednesday Problem | 1 Comment