Well, it is time for a cool and easy riddle. 100 men are each assigned a number between 1-100 with repetitions (e.g. all of them may be assigned the number 17). Each of the men sees all the numbers assigned to all the other 99 men, but none of them sees the number assigned to himself.

Each of them needs to guess his own number (of course no information is exchanged between them – no one hears what others have guessed etc.). What strategy can they employ in order to make sure at least one of them makes a correct guess?

Some followup thoughts:

• Can they make sure more than one person succeeds?
• How many different solutions to the riddle are there (i.e. how many strategies can the men employ?).

A short introduction to Graph Theory is needed for this one. If you already are familiar with Graph Theoretic constructs feel free to skip it.

A graph G, is a pair (V,E) where V is a set of vertices and E is a set of edges. Each edge is an unordered pair of the form (u, v) where u and v are vertices (i.e. they belong to V). The degree of a vertex t (denoted deg(t)) is the number of edges containing it:

deg(t) = #{ e | e = (s, t) ^ s belongs to V }

In this post I only consider finite and simple graphs. A finite graph is a graph whose vertex-set V is a finite set. A simple graph is a graph in which there are no loops (i.e. edges of the form (u, u)) and no multiple edges (i.e. E is a proper set so it cannot contain the same element twice).

The following is a trivial claim:

The sum of the degrees in a graph equals twice the number of edges.

It is trivial to prove this claim by induction on the number of edges (on a graph with no edges it is clear, and by adding an edge to the edge set of the graph the sum of degrees increases by two).

Use this claim to solve the following riddle:

A rectangle is called whole if at least one of its sides is an integer. For example, a rectangle of 2 by 3/5 is whole as well as a rectangle of sqrt(5) by 3. A rectangle of 1/2 by 1/2 is not whole. Examples:

A set T of rectangles constitues a tiling of a rectangle R if the rectangles in T are disjoint and for every point p in R there is a rectangle S in T such that p belongs to S. Example:

Prove that if R is a rectangle and T is a tiling of R consisting only of whole rectangles (i.e. every rectangle S in T is whole) then R is whole.

This one is a riddle of my own invention. I am really proud of it as it sounds impossible at first, but it can be resolved in a very satisfying fashion. I must admit that had I heard about it from someone else I would not have gone through the trouble of trying to solve it, as it sounds like a ”cheap-trick” riddle. I can only ask you to trust me that it is indeed a purely mathematical riddle. Although it did provoke several harsh disputes with some very smart people (Matan, Eyal, how are you guys?), I was able to finally convince them of the mathematical validity of my solution.

The riddle goes like this:

A group of very smart men perform an experiment. There are no restrictions on the men’s behaviour during the experiment. After the experiment is over, each of the men reveals to all the others everything that he knows. Despite the fact that none of the men lies and they all know of everything that happened, there are 2 individuals in the group that reach different scientific conclusions. Your task is to devise such an experiment.

Note that the experiment is scientific in that it does not concern individual tastes or opinions. All the men are assumed to come from similar backgrounds and have similar likings. The different conclusions regard real aspects of nature.

The dice picture is a (vague) reference to one variant of my solution.

I visited my parents yesterday, for the Jewish holiday of Shavuot. I found there a picture of myself and some friends from the time we sailed on the Tuichi river in Bolivia on a raft we built ourselves with machetes. Here is the picture and a legend:

Note that the picture is very dark, as it was taken in the night time.

I have to admit that looking at the picture, it seems that we are escaping from a prison. To make this post more in the spirit of my site I could have added one of the many prison riddles here, but I must say I am happy with this post just the way it is (maybe I will update it with a prison-riddle in the future).

This other cool picture I stumbled upon in my parents house, I call “What’s for Dinner?”:

I took it in the market of the city of Cusco, Peru.

Happy holidays!

Make sure you have read the first part of this post here.

Now we are ready to define the rules for our second, more complex game – “Construction with a Straight-Edge and a Compass“. These are very similar to the rules of “Constructions with a Straight-Edge Only” (defined in the previous post) except that now, in addition to creating infinite straight lines, you can also create circles, as follows: given 2 points, a and b, you can create the circle with center at a that passes through b. A point is added to the set of points if it is the intersection of 2 lines (as before), of two circles or of a circle and a line.

Now, the addition of the new tool (the compass) enables us to construct many more points than before. If the initial set of points contains only one point then, as before, no new points can be constructed. But if the initial set of points contains two points then a the set of constructable points is infinite (we will shortly prove it). The subject for this second part of the topic will be analysing the set of constructable points in our new game.

Note that it is enough to examine the constructable-points’ set, P, from the initial set A = { (0,0), (1,0) }. This is because if the initial set of points contains the two points a and  b(instead of (0,0) and (1,0)), then there is an affine operator M acting on the euclidean-plane and consisting of translations and rotations, such that a becomes the origin and bbecomes (1,0). Denote the inverse of M by N. Then the set of points constructable from the initial set { a, b } is the same as the set { N(x) | x belongs to P }.

So our question is, “what points belong to P, the set of constructable points, from the initial set A = { (0,0), (1,0) }?”

In order to answer this question we shall develop some tools:

Mid-Point Perpendicular

Given two points, a and b, we can construct the line passing through their mid-point that is perpendicular to the line passing through a and b. This is done as depicted here (the yellow dot is the constructed mid-point):

Point Reflection

Given a point a and a point b, we can create the point c (that is different from a) lying on the line through a and b and whose distance from b is the same as the distance from b to a. This can be done by using the straight-edge to create the line through a and b and then use the compass with center at b and leg at a. cis the intersection of this circle and line:

Creation of the Axis

The x-axis is easily constructable from the two initial points by using the straight-edge. The point (-1, 0) is constructable from the initial points by using Point Reflection. The y-axis is then constructable from (-1, 0) and (1, 0) by using Mid-Point Perpendicular.

Axis Flip

Given a point on the x-axis of the form (a, 0), create the point (0, a) on the y-axis, and vise versa. Given the Creation of the Axis, as above, performing an Axis Flip is very easy.

Coordinate Selection

Given a point (x, y) create the point (x, 0). By placing the compass’ center on (x, y) and its leg on the origin, its other intersection with the x-axis is the point (2x, 0). Using the Mid-Point Perpendicular we can construct (x, 0).

Now we shall note that the notion of constructable points in our new game can be changed a bit to the notion of constructable numbers. A number x is constructable if the point (x, 0) is constructable. Note that if a point (x, y) is constructable than both x and y are constructable (by using Axis-Flip). If on the other hand x and y are constructable numbers then again by using Axis Flip we get that (x, 0) and (0, y) are constructable points. By using a trick similar to what we did for creating the y-axis the point (x, y) is shown to be constructable. So we shall now only consider the simpler notion of constructable numbers instead of constructable points.

We have shown a relation between constructable points and constructable numbers. We can also consider the notion of constructable distances. A number d is a constructable distance, if it is the distance between to constructable points. It can be shown (I might do this in the future) that a number d is a constructable number i.f.f. (if and only if) d is a constructable distance. One direction is easy. Can you prove the other?

Lets continue to build our tools, this time for constructable numbers.

The Integers

All the integers are constructable numbers. 0 and 1 are constructable (as (0,0) and (1, 0) are in the initial set). Given the integers i and and i-1 integer i+1 can be constructed. Just place the compass’ center on the point (0, i) and its leg on (0, i-1) and the circle’s intersection with the x-axis yields i+1. Integer i-2 can be constructed in a similar fashion. By induction all integers (positive and negative) are constructable.

Negative

If x is constructable then -x is constructable. This is obvious (can you see why?).

Addition and Subtraction

Given constructable numbers a and b, a+b is a constructable number. We can construct -b, and so a+b is a constructable distance. Using the equivalence stated above (which I have not yet proved) between constructable distances and constructable numbers, a+b is constructable. Addition and Negative lead to Subtraction.

Multiplication and Division

 If a and b are constructable numbers, so are a×b and a/b. The construction for multiplication is depicted below (division is similar):

As you can see,  all the rational numbers are constructable.

Actually, we have reached a more important conclusion: the constructable numbers constitute an extention field of Q, the field of rational numbers!

We are getting closer to the answer we are looking for, as we already know quite a bit about the set P of constructable points.

To be continued…

This post is about a conversation I once held with a good friend of mine, Nadav Sherman. It is not a very serious topic, so take it lightly. We were wondering how to calculate the total amount of fun a person has during his life time. We reasoned as follows:

The absolute state score (a.s.s.) of a person is a number ranking the person’s current state and possessions (it is a function of time). For example, if you have 500,000$ and a girl-friend, then your a.s.s. is higher than that of someone identical to you without a girlfriend, but lower than that of someone identical to you with an additional 1,000,000$. Note that we do not specify exactly how to calculate the a.s.s., but we believe that it can be defined such that claim 1 below will be true. The actual value of the a.s.s. is not directly correlated to the fun a person has – a person with a million dollars and a beautiful girl-friend can be sadder than a poor lonely guy.

We define the effective fun of a person as a measurement of the instantaneous fun a person has in a given moment (again, it is a function of time). Our first claim is:

claim 1: The effective fun equals the derivative of the a.s.s..

Again, this obviously depends on the exact function used to calculate the a.s.s.. Instead of proving the claim above, I will give an intuitive reasoning as to why it makes sense. It is obvious that if your a.s.s. is going up right now, you are happy, regardless of the actual value of the a.s.s.. Conversely, if your a.s.s. goes down you are sad, regardless of the value of your a.s.s..

Lets give an example. If you get a new girlfriend, your a.s.s. goes up and so your effective fun (its derivative) is positive. If you lose 100$ your a.s.s. goes down and so your effective fun is negative. The actual value of the a.s.s. does not matter – only changes in the a.s.s. influence your effective fun.

Please make sure you understand claim 1 before continuing to read (see also the following figure).

Now, in order to calculate the total amount of fun a person has in a given period we obviously integrate the effective fun function over the given period. We use the fundamental theorem of calculus, stating that the integral of the derivative of a function equals the function itself (note that as this is not the true fundamental theorem of calculus, which speaks solely of continuous functions, but its more in the spirit of it) to get the following:

claim 2: The total fun a person has in a given period is the a.s.s. value at the end of the period minus the a.s.s. value at the beginning of the period.

This leads us to our final (morose) conclusion:

The total fun a person has in his lifetime equals his a.s.s. on the day he was born minus his a.s.s. on the day he dies (no matter how long he lived or what happened during his lifetime).

A few years ago a friend of mine asked me the following Perl riddle. Unfortunately, in order to solve it you must know Perl. As I like Python much better, I translated the riddle to Python. Attached are both versions.

I admit the Perl version is a bit more cryptic and if you know both Perl and Python you should try to solve the Perl version (but use Python for everything else in life ).

Oh, and try to solve the riddle without running it (run it only as a last resort).

perl -wle 'print "True" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number]

python -c "import sys, re; print None == re.match('^1?$|^(11+?)\\1+$','1'*int(sys.argv[1]))" [number]

To alleviate all doubt – [number] denotes a numeric command line argument (e.g. 17).

This topic is about defining a weird game and exploring its properties. When I first encountered it I could not help but wonder, why is it interesting?

Well, this game (as you shall soon find out for yourself) has barely any practical implications. But it is an interesting subject none the less. There are 2 main reasons for that:

1. This game was analysed (with limited success) by many important mathematicians, since the times of the Greeks.
2. Using the right tools, the complete answer to the questions relating this matter is achievable and it turns out to be beautiful.

Now lets dive in. We will begin with a simplified game I call ”Constructions with a Straight-Edge Only“. BTW, a straight-edge means a ruler without markings (the only thing you can do with a straight-edge is connect two points with an infinite line).

These are the rules of our simplified game: The board is the 2 dimensional euclidean plane. You start with an initial set of points and during the game you make it grow. Lets call this set of points P. On each turn you can connect two points in your set P by an infinite straight line. If two of these lines intersect at one point that is not already in P, the new point is added to your set.

A point of the euclidean plane is called constructable if it can be added to the set. Note that the notion of constructability depends on the initial set of points (i.e. some points may be constructable from one initial set of points but not from another).

Lets demonstrate the rules with some simple examples:

1. If the initial set of points consists of only a single point then this single point is also the only constructable point (as no lines can be drawn). The same applies for an initial set containing 2 points (as only one line can be drawn, and so there are no line intersections!).
2. If the initial set contains 3 points then 3 lines can be drawn (as shown here). But no new point is created.
   
3. If the initial set is a rectangle, one new point can be created.
   

A more complex example is depicted below. Well, as you can see, many new points can be created. I added to the illustration only the first few, but you get the point.

Let me raise an interesting question I have not yet had time to think about: what initial sets of points (if any) lead to an infinite set of constructable points?

Note that we have not specified that the initial set should be finite. For example, we can start out with all the points on the x-axis. It is clear that the set of points constructable from this set is equal to the x-axis (i.e. no new point can be constructed).

The above example suggests another interesting question – what initial sets of points are unexpandable? I.e. no new points can be constructed from them. The sets containing fewer than 4 points are obviously unexpandable, as are the sets contained in a line and the set consisting of the entire euclidean-plane. But are there others? 

Now lets assume our initial set contains only points with rational coordinates (lets call them rational points). What can be said about the set P of constructable points?

A nice observation is that P contains only rational points. To see this, observe that the line passing through points (x1, y1) and (x2, y2) satisfies the equation:

y = (y2 – y1) / (x2 – x1) × (x – x1) + y1

Opening all the parenthesis, and noting that the set of rational numbers constitutes a field, the line equation becomes: 

y = m × x + b

Where m and b are rational numbers.

Note that if the line is vertical it does not satisfy the equation but since it is clear how to handle this special-case I will not elaborate.

We need to show that the point of intersection of two lines of the form:

y = m × x + b

and

y = m’ × x + b’

is rational (i.e. it has rational coordinates). Since the point of intersection (x0, y0) satisfies both line equations, we get:

m × x0 + b = m’ × x0 + b’

or

x0 = (b’ – b) / (m – m’)

and so x0 is rational (again, I ignore the special case m = m’ in which the lines are parallel).

And then y0 = m × x0 + b is also rational. So indeed the intersection of two lines passing through two rational points is a rational point.

This concludes the first part of this topic.

To be continued…

I had a lot of thinking before deciding to include this riddle in my site. The argument for not including it, is that it is too complicated. I ended up deciding it deserves its place in my riddles section (which means I believe it is one of the most beautiful riddles ever) because, well, I think it is one of the most beautiful riddles ever. So enjoy! (but be ready for a hard one…):

There are 100 men, 100 boxes and 100 notes with the men’s names on them. The 100 boxes are arranged in a line in a room. Each of the notes with the names is put in a different box randomly. The men are put together and are allowed to decide upon a strategy. When they are done, they are taken, each in his turn, to the room with the boxes. Each one is allowed to open 50 of the boxes. No information whatsoever is shared between the men.

The goal of the men is that each of them finds his own name among the 50 boxes he opened. If but one of them fails to find his own name, they all get killed (why is it, that in so many riddles people end up dead?). You are required to find a method with which they are all saved with a probability of above 30%.

If you understood this riddle properly, it should seem impossible to you at first.

Because the riddle contains many details and to make sure I explained it properly, lets consider two bad strategies for the men:

1. All the men decide to open the same 50 boxes – this is probably the worst strategy for them, as all of them will die with probability 1. This is because 50 of them are sure not to find their names in the boxes they open.

2. Every man open 50 boxes randomly – although a better strategy than the former one, it is a very bad strategy. Each person is likely to find his own name with a probability of 1/2. As all the events of the men finding their names are independent, they will be saved with a probability of (1/2)^100.

As this number is smaller than 0.00000000000000000000000000000079 (which is obviously smaller than 30%) it is a very bad strategy indeed.

BTW - to calculate the above number I used the following python statement:
>>> '%1.32f'%0.5**100

Solution now available on next page!

Hello all!

I am very excited to announce that my site is up and I really hope you enjoy it. I will always appreciate your feedback (and especially now, that its all brand-new!). Do not hesitate to contact me at yaniv@leviathanonline.com and please register and post comments!

Yaniv

This is probably the best riddle I know of.

There are 1000 ants walking on a horizontal stick, 1m long.

Each ant is walking at a constant rate of 1m/hour.

The ants start out in random locations on the stick, some walking to the left and some to the right.

Whenever two ants meet they reverse their direction, as follows:

Whenever an ant reaches one of the ends of the stick, it falls off (eventually all ants will fall).

What is the longest time it will take the last ant to fall off the stick?

The Ants riddle is one of the best riddles ever. It requires an imaginative mind, but does not require any knowledge of mathematics. A talented 6 year old can solve it!That is not to say it is very easy, but you can solve it yourself. DO NOT DESPAIR!

If you already solved the riddle and want to see the solution – visit the second page below.