North->South->East->North

After traveling from a point X on earth 10 km South, 10 km East and 10 km North you arrive at the same location X.  Where is X situated?  How many such points X exist?

The obvious solution is X being the North Pole. But there are other positions on earth that respect the conditions.

Consider for example going on a meridian toward the South Pole until the length of the parallel you are situated on is exactly the same as the distance traveled. Moving to East in this case would mean making a complete rotation on that parallel, and moving to North is then performed in the reverse direction on the first segment of the trajectory.

More concrete, from any point situated 10 km North from the parallel having the length of 10 km ($\frac{10}{\pi}$ diameter) we can travel as described above so there are infinite points X.

Even more, from a point situated at 10 km from the parallel of length 5km (that would be quite close to the South Pole), you can go to South until reaching the parallel, make two complete rotations then back in North direction.

Or more generally, move 10 km to South until reaching the parallel of length $\frac {10}{n}$, make $n$ rotations, and then move back 10 Km North.

Source:  Martin Gardner, “The Colossal Book of Short Puzzles and Problems”  http://www.amazon.com/Colossal-Book-Short-Puzzles-Problems/dp/0393061140

Staircase climbing

Question:

You are climbing a stair case. Each time you can either climb 1 stair or 2 stairs. The staircase has n stairs. In how many distinct ways can you climb the staircase ?

There are two possibilities for the last performed step: one stair or two stairs.

Thus, the number of possibilities for $n$ stairs will be the number of possibilities to climb $n-1$ stairs (in case the last step is one stair long) plus the number of possibilities to climb  $n-2$ stairs (in case the last step is two stairs long).
Looks like the answer is related to Fibonacci numbers:
$S(n)=S(n-1)+S(n-2)$ with $S(1)=1$ and $S(2)=2$

6 persons inside an elevator – the math

Prove that if 6 persons are inside an elevator then there is a subgroup of 3 persons that know each other or a subgroup of 3 persons that don’t know each other. Note: for this problem if A  knows B then B also knows A (symmetric relation).

In the previous post I presented an algorithm that check the above statement. Here I will show the mathematical proof. Thanks to J who actually found this nice proof ;).

Consider one person $p_1$. There are other 5 persons that he can know or not. If $p_1$ dont’t know at least 3 of them  (case 1 is $p_1$ knows 3 of them)  then it means that there are 3 persons that $p_1$ don’t know (case 2).

Consider $A= {p_2, p_3, p_4}$ the persons $p_1$ know (case 1) or that $p_1$ don’t know (case 2).

For case 1, if there are to persons $p_i$ and $p_j$ in A that know each other it means that ${p_1, p_i, p_j}$  is a group of 3 persons that know each other. Otherwise, if any two persons from A don’t know each other it means that A is a subgroup of 3 persons that don’t know each other.

Case 2 is similar to case 1, just replace ‘don’t know’ with ‘know’ and  ‘know’ with ‘don’t know’.

6 persons inside an elevator – algorithm

Prove that if 6 persons are inside  an elevator then there is a subgroup of 3 persons that know each other or a subgroup of 3 persons that don’t know each other. Note: if A  knows B then B also knows A (symmetric relation).

This is a math problem, but I don’t have yet a mathematical solution for it. Thus I wrote an algorithm to show that the above statement indeed holds. The idea is to generate all the possible variants based on the fact that two persons can know each other or not. Then for each variant I check if there is a subgroup of 3 persons that know each other or a subgroup of 3 persons that don’t know each other.

Let’s analyze some numbers before to write the code. There are $\binom {6}{2}=15$ different pairs of persons which can know each other or not. It follows that there are $2^{15}$ variants to analyze. For each variant I want to check if any of the subgroups of 3 persons respect one of the conditions: know each other or don’t know each other. For this check I’ll need to generate all the combinations of 3 persons. Their number is: $\binom {6}{3}=20$.

The code to generate the combinations is called once, at the beginning of the main program, because same combinations can ve reused for each variant:

//store all the combinations
int combinations[20][3];
//curent combination generated by the algorithm
int curentCombination[3];
int curentCombinationNumber=0;
//generate combinations
void comb(int pos, const int& n, const int& k)
{
if (pos >= k)
{
memcpy(combinations[curentCombinationNumber],
curentCombination, k*sizeof(int));
curentCombinationNumber++;
return;
}
int start = 1;
if (pos > 0) start = curentCombination[pos-1]+1;
for (int v = start; v<= n; v++)
{
curentCombination[pos] = v;
comb(pos+1, n, k);
}
}

Each variant can be represented as a number from $0$ to $2^{15}-1$. Digits 1 will correspond to people knowing each other and digits 0 will correspond to people not knowing each other according to the following algorithm (note that <<  is a left shift operation):

//edge[i][j] is the number used for AND bitwise in order
//to check if person i knows person j
int edge[6][6];
int shift = 0;
for (int i = 0; i<6; i++)
for (int j = i+1; j<6; j++)
{
edge[i][j] = (1 << shift);
shift++;
}

Based on the combinations and the rule established for “i knows j” the rest of the algorithm is:

//A possibility is represented using the digits in the base 2 of a number
for (int variant = 0; variant < (1<<15); variant++)
{
bool found = false;
//search a subgroup that know each other or don;t know each other
for (int combCount = 0; combCount<20; combCount++)
{
//get the persons for this combination
int a = combinations[combCount][0];
int b = combinations[combCount][1];
int c = combinations[combCount][2];
bool ab = (edge[a][b] & variant) > 0;
bool bc = (edge[b][c] & variant) > 0;
bool ac = (edge[a][c] & variant) > 0;
if ((ab && bc && ac) || (!ab && !bc && !ac)) { found = true; break;}
}
if (!found)
{
printf("Warning....something is wrong with the algorithm!!");
}
}

Of course, it never displays: “Warning….something is wrong with the algorithm!!”

Posted in Math | 1 Comment

Bowls with candys problem

As you’ll see, this post is somehow similar to boxes and coins problem.

Given 7 bowls, each with at least 80 candies. All the candies from some bowls weigh 10 grams, and all the candies from other bowls weigh 11 grams. Find what are the bowls that contain candies weighting 11 grams with one single weighting.

Solution (it is better to think a bit before to read the solution, you may have a better one):

To recap, we have 7 bowls and all the candies from each bowl weigh 10 grams or 11 grams.  So all the candies from some bowls weigh 11 grams, and we need to find exactly what are those bowls.

One solution is to take $1=2^0$ candy from the first bowl, $2^1$ candies from the second bowl, $2^2$ candies from the third bowl , …. , $32=2^5$ candies from the 6-th bowl , and $64=2^6$ from the 7-th bowl. Let’s weigh all the candies taken above. The weight will be:

$w = a_1 \cdot 2^0 + a_2 \cdot 2^1 + a_3 \cdot 2^2 + \cdots + a_7 \cdot 2^6$ where $a_i$ is the weight of the candies from the $i-th$ bowl.

If all the selected candies would weigh 10 grams then their weight would be:

$w = 10 \cdot 2^0 + 10 \cdot 2^1 + 10 \cdot 2^2 + \cdots + 10 \cdot 2^6$

But some of them weigh 11 grams. The difference $w'-w$ is:

$w'' = d_1 \cdot 2^0 + d_2 \cdot 2^1 + d_3 \cdot 2^2 + \cdots + d_7 \cdot 2^6$ where $d_i$ is $0$ if the corresponding candies weigh 10 grams or  $1$ if the corresponding candy weigh 11 grams.

But wait! This representation should be familiar to you :). It seems that $d_i$ are the binary digits (base 2) of some number. That means that if we subtract w’ (which we can simply compute) from the weight of the selected candies we get a number and the base 2 representation of this number indicates what are the bowls having 11 grams coins.

Probability that the second child is a girl?

Two parents have two children. One of the children (first or second) is a girl. What is the probability that the second child is a girl?

There are 4 possibilities:

1. First boy, second boy.

2. First boy, second girl.

3. First girl, second boy.

4. First girl, second girl.

We know that one of the children is a girl, so the possibilities are 2, 3 and 4. Possibility one is excluded because both are boys. From those three , for 2 and 4 second child is a girl. It means that the probability is: 2/3.

Posted in Math | 1 Comment

Air distance

In the last post a proof of the spherical law of cosines was made.

For the figure below, following equality holds:

$cos(a)cos(b) + sin(a)sin(b)cos(u) = cos(c)$   (***)

The earth is more like an ellipsoid but for computing the air distance with enough accuracy it is fine to consider it a sphere. Imagine that the earth is the sphere from the figure, $A'$ has the GPS coordinates $(x_A, y_A)$ and $B'$ has GPS coordinates $(x_B, y_B)$. All the coordinate are expressed in radians. Note that the angle $u$ is the difference between longitudes because $NA''$ and $NB''$ are meridians: $u=y_B-y_A$

The longitude of $A'$ will be $x_A=\frac{\pi}{2}-a$ and the $B'$ will be $x_B=\frac{\pi}{2}-b$.

It follows that we can substitute those values in (***) to find $c$:

$cos(c)=cos(a) \cdot cos(b) + sin(a) \cdot sin(b) \cdot cos(u)$ = $cos\left(\frac{\pi}{2}-x_A\right) \cdot cos\left(\frac{\pi}{2}-x_B\right) + sin\left(\frac{\pi}{2}-x_A\right) \cdot sin\left(\frac{\pi}{2}-x_B\right) \cdot cos(y_B-y_A)$ = $sin(x_A) \cdot sin(x_B) + cos(x_A) \cdot cos(x_B) \cdot cos(y_B-y_A)$

Having the $c$ angle, the length of the arc $A'B'$ can be computed by multiplying with the earth radius.

$s=R \cdot arccos(sin(x_A) \cdot sin(x_B) + cos(x_A) \cdot cos(x_B) \cdot cos(y_B-y_A))$

Note that this formula holds for sure if both $A'$ and $B'$ are in the north hemisphere and if the difference between longitudes is smaller than $\pi$. For other situations it may need some $\pm$ adjustments.