Home » Posts tagged 'Puzzles' (Page 2)

# Tag Archives: Puzzles

## Problem1: Smallest Autobiographical Number:

A number with ten digits or less is called autobiographical if its first digit (from the left) indicates the number of zeros it contains,the second digit the number of ones, third digit number of twos and so on.

For example: 42101000 is autobiographical.

Find, with explanation, the smallest autobiographical number.

Solution of Problem 1

## Problem 2: Fit Rectangle:

A rectangle has dimensions $39.375$ cm $\times 136.5$ cm.

• Find the least number of squares that will fill the rectangle.
• Find the least number of squares that will fill the rectangle, if every square must be the same size and Find the largest square that can be tiled to completely fill the rectangle.

Solution of Problem 2

## Solutions of Problem 1:

The restrictions which define an autobiographical number make it straightforward to find the lowest one. It cannot be 0, since by
definition the first digit must indicate the number of zeros in the number. Presumably then, the smallest possible autobiographical number will contain only one 0.If this is the case, then the first digit must be 1. 10 is not a candidate because the second digit must indicate the number of 1s in the number–in this case, 1. So If the
number contains only one zero, it must contain more than one 1.
(If it contained one 1 and one 0, then the first two digits
would be 11, which would be contradictory since it actually contains two 1s).
Again, presumably the lowest possible such number will contain the lowest
possible number of 1s, so we try a number with one 0 and two 1s. It will be of the form: 12-0–..
Now, there is one 2 in this number, so the first three digits must be 121. To meet all the conditions discussed above, we can simply take a 0 onto the end of this to obtain 1210, which is
the smallest auto-biographical number.

## Solution of Problem 2:

We solve the second and third parts of the question
first:

We convert each number to a fraction and get a common denominator, then find the gcd (greatest common divisor) of the numerators.

That is, with side lengths $39.375$ cm and $136.5$ cm , we convert those numbers to fractions (with a common
denominator):
$39.375 = \dfrac{315}{8}$.

$136.5 = \dfrac{273}{2} = \dfrac{1092}{8}$.

Now we need to find the largest common factor of 315 and 1092.
Which is 21. So $\dfrac{21}{8}=2.625$ is the largest number that divides evenly into the two numbers $39.375$ and $136.5$.
There will be $\dfrac{1092}{21} \times \dfrac{315}{21} = 52 \times 15 = 780$ squares, each one a $2.625$ cm $\times 2.625$ cm square needed to fill the rectangle (52 in each row,with 15 rows).

Now we shall solve the first part.
Number of squares lengthwise is 52 and breadthwise is 15. Now we will combine these squares in order to find least number of squares to fill the rectangle. First three squares would be of
dimension 15 by 15. In this way length of 45 units is utilized. Now the rectangle which is left with us excluding three squares is 7 by 15. Again in the same way we can make two squares of dimension 7 by 7. In this way breadth of 14 units is utilized.
Now we are left with the rectangle of dimension 7 by 1.
These can further be subdivided into seven squares each of
dimension 1 by 1. In this way the least number of squares to fill the
rectangle is 3 + 2+ 7 = 12. The required answer is 12.
Note that the three numbers 3, 2, and 7 are involved in the Euclidean Algorithm for finding the g.c.d.!

Source: Internet

## Chess Problems

1. In how many ways can two queens, two rooks, one white bishop, one black bishop, and a knight be placed on a standard $8 \times 8$ chessboard so that every position on the board is under attack by at least one piece?
Note: The color of a bishop refers to the color of the square on which it sits, not to the color of the piece.
2. Can you attack every position on the board with fewer than seven pieces?

## How many apples did each automattician eat?

Image via Wikipedia

Four friends Matt, James, Ian and Barry, who all knew each other from being members of the Automattic, called Automatticians, sat around a table that had a dish with 11 apples in it. The chat was intense, and they ended up eating all the apples. Everybody had at least one apple, and everyone know that fact, and each automattician knew the number of apples he ate. They didn’t know how many apples each of the others ate, though. They agreed to ask only questions that they didn’t know the answers to:

Matt asked: Did you eat more apples than I did, James?

James: I don’t know. Did you, Ian, eat more apples than I did?

Ian: I don’t know.

Barry: Aha!! I figured out..

So, Barry figured out how many apples each person ate. Can you do the same?

Matt: 1 Apple

James: 2 Apples

Ian: 3 Apples

Barry: 5 Apples

## The Logic

Matt could not have eaten 5 or more. James could not have eaten only one or he would have known that he hadn’t eaten more than Ian. Neither could he have eaten 5 or more. He could have eaten 2 or 3 or 4 apples. Ian figures this out, although he still doesn’t know if he ate more than James. This mean that Ian must have eaten 3 or 4 apples. Barry can only deduce the other amounts if he ate 5 apples. And the rest, in order to add up to 11 , must have eaten 1, 2 and 3.

Inspired from a childhood heard puzzle.

Related Articles Found on this Blog:

## Fox – Rabbit Chase Problems

##### Part I:

A fox chases a rabbit. Both run at the same speed $v$. At all times, the fox runs directly toward the instantaneous position of the rabbit , and the rabbit runs at an angle $\alpha$ relative to the direction directly away from the fox. The initial separation between the fox and the rabbit is $l$.

When and where does the fox catch the rabbit (if it does)? If it never does, what is their eventual separation?

##### Part II:

Similarly think about the same situation, except now let the rabbit always move in the straight line of its initial direction in above part of the question.

When and where does the fox catch the rabbit (if it does)? If it never does, what is their eventual separation?

## Solutions

#### Part I

The relative speed of the fox and the rabbit, along the line connecting them, is always $v_{\text{rel}}= v- v \cos \alpha$. Therefore, the total time needed to decrease their separation from $l$ to zero is $T=\dfrac{l}{v-v \cos \alpha} =\dfrac{l}{v(1-\cos \alpha)} \ \ldots (1)$ which is valid unless $\alpha=0$, in which case the fox never catches the rabbit.
The location of their meeting is a little trickier to obtain. We have two methods to do :

##### SLICK METHOD

Imagine that the rabbit chases another rabbit, which chases another rabbit, etc. Each animal runs at an angle $\alpha$ relative to the direction directly away from the animal chasing it. The initial positions of all the animals lie on a circle, which is easily seen to have radius $R=\dfrac{l/2}{\sin (\alpha/2)} \ \ldots (2)$.
The center of the circle is the point, O, which is the vertex of the isosceles triangle with vertex angle $\alpha$, and with the initial fox and rabbit positions as the othe two vertices. By symmetry, the positions of the animals at all times must lie on a circle with center O. Therefore, O, is the desired point where they meet. The animals simply spiral into O.

#### Remark

An equivalent solution is the the following:

At all times, the rabbit’s velocity vector is obtained by rotating the fox’s velocity vector by angle $\alpha$. The meeting point O, is therefore the vertex of the above mentioned isosceles triangle,

##### MESSIER METHOD

The speed of the rabbit in the direction orthogonal to the line connecting the two animals in $v \sin \alpha$. Therefore, during a time $dt$, the direction of the fox’s motion changes by an angle $d\theta =\dfrac {v \sin \alpha}{l_t} dt$ , where $l_t$ is the separation at time $t$. Hence the change in the fox’s velocity has magnitude $|d\overrightarrow{v}|=v d\theta =v (v \sin \alpha dt/l_t)$. The vector $d\overrightarrow{v}$ is orthogonal to $\overrightarrow{v}$, therefore, to get the $x$-component of $d\overrightarrow{v}$, we need to multiply $|d\overrightarrow{v}|$ by $v_y/v$. Similar reasoning holds for $y$-component of $d\overrightarrow{v}$, so we arrive at the two equations $\dot{v_x}= \frac{vv_y \sin \alpha}{l_t} \ \ldots (3)$ $\dot{v_y}=- \frac{vv_x \sin \alpha}{l_t} \ \ldots (4)$
Now, we know that $l_t =\{ l-v(1-\cos \alpha) t \}$. Multiplying the above equations (3) and (4) by $l_t$ , and integrating from the initial to final times, yields $v_{x,0}l+v(1-\cos \alpha)X=v \sin \alpha \, Y \ \ldots (5)$ $v_{y,0}l+v(1-\cos \alpha)Y=-v \sin \alpha \, X \ \ldots (6)$
where (X,Y) is the total displacement vector and $(v_{x,0},v_{y,0})$ is the initial velocity vector. Putting all the X and Y terms on the right sides, and squaring and adding the equations, we get $l^2v^2=(X^2+Y^2)(v^2 \sin^2 \alpha +v^2{(1-\cos \alpha)}^2). \ \ldots (7)$ Therefore , the net displacement is
$R=\sqrt{X^2+Y^2}=\dfrac{l}{\sqrt{2(1-\cos \alpha)}}=\dfrac{l/2}{\sin (\alpha/2)} \ \ldots (8)$
To find the exact location, we can, without loss of generality, set $v_{x,0} =0$, in which case we find $Y/X=(1-\cos \alpha)/\sin \alpha =\tan \alpha/2$. This agrees with the result of the first solution. $\Box$

#### Part II:

##### SLICK METHOD

Let $A(t)$ and $B(t)$ be the positions of the fox and the rabbit respectively. Let $C(t)$ be the foot of the perpendicular dropped from $A$ to the line of the rabbit’s path. Let $\alpha_t$ be the angle, dependent to the time, at which the rabbit moves relative to the direction directly away from the fox (so at $t=0, \ \alpha_0=\alpha$ and at $t=\infty , \ \alpha_{\infty}=0$).

The speed at which the distance AB decreases is equal to $v-v \cos \alpha_t$. Therefore, the sum of the distances AB and CB doesn’t change. Initially, the sum is $l+l \cos \alpha$ and in the end , it is $2d$ where $d$ is desired eventual separation. Therefore, the desired eventual separation
$d=\dfrac{l(1+\cos \alpha)}{2} \ \ldots (9)$

##### STRAIGHT FORWARD METHOD

Let $\alpha_t$ be defined as in the first solution, and let $l_t$ be the separation at time $t$. The speed of the rabbit in the direction orthogonal to the line connecting the two animals is $v \sin \alpha_t$. The separation is $l_t$ , so the angle $\alpha_t$ changes at a rate $\dot{\alpha_{t}}= - \dfrac{v \sin \alpha_t}{l_t} \ \ldots (10)$. And $l_t$ changes at a rate $\dot{l_t}=-v(1-\cos \alpha_t) \ \ldots (11)$.
Taking the quotient of the above two equations, separating variables, gives a differential equation $\dfrac{\dot{l_t}}{l_t} = \dfrac {\dot{\alpha_t}(1-\cos \alpha_t)}{\sin \alpha_t} \ \ldots (12)$ which on solving gives $\ln (l_t) = -\ln {(1+\cos \alpha_t)} + \ln (k) \ \ldots (13)$. Where $k$ is the constant of integration. Which gives $k=l_t (1+\cos \alpha_t) \ \ldots (14)$. Applying initial conditions $k_0 = l_0 (1+\cos \alpha_0)= l(1+\cos \alpha) \ \ldots (15)$. Therefore from (14), we get $l(1+\cos \alpha) = l_t(1+\cos \alpha_t)$, or $l_t= \dfrac{l(1+\cos \alpha)}{1+\cos \alpha_t}$.
Setting $t= \infty$ and using $\alpha_{\infty} =0$, gives the final result $l_{\infty} = \dfrac{l(1+\cos \alpha)}{2}$. $\Box$.

#### Remark:

The solution of Part II is valid for all $\alpha$ except $\alpha= \pi$. If $\alpha = \pi$, the rabbit run directly towards the fox and they will meet halfway in time $l/2v$.

## Bicycle Thieves – A puzzle

One day a man, who looked like a tourist, came to a bicycle shop and bought a bicycle from a shop for $70. The cost price of the bicycle was$60. So the shopkeeper was happy that he had made a profit of $10 on the sale. However, at the time of setting the bill, the tourist offered to pay in travellers cheques as he had no cash money with him. The shopkeeper hesitated. He had no arrangement with the banks to encash travellers cheques. But he remembered that his friend, the shopkeeper next door, has such a provision, and so he took the cheques to his friend next door and got cash from him. The travellers cheques were all of$20 each and so he had taken four cheques from the tourist totalling to $80. On encashing them the shopkeeper paid back the tourist the balance of$10.
The tourist happily climbed the bicycle and pedaled away whistling a tune.
However, the next morning shopkeeper’s friend who had taken the travellers cheques to the bank called on him and returned the cheques which had proved valueless and demanded the refund of his money. The shopkeeper quietly refunded the money to his friend and tried to trace the tourist who had given him the worthless cheques and taken away his bicycle. But the tourist could not be found.

How much did the shopkeeper lose altogether in this unfortunate transaction?

One can think of different answers for this question, but yet the correct answer is very simple. All we have to consider is that the shop owner could not have possibly lost more than the tourist actually stole.
The tourist got away with the bicycle which cost the shop owner $60 and the$10 ‘change’ , and therefore, he made off with \$70. And this is the exact amount of the shopkeeper’s loss.

Source of The Puzzle:

Puzzle 7, Puzzles to Puzzle You
© Shakuntala Devi, 1976

This puzzle is l’ll modified than the original.

## An Elementary Problem on Egyptian Fractions

Few math problems, specially, problems on Numbers are very interesting. In this “Note”, I’ve added a classical problem, as follow:

Solve $\dfrac{1}{w} + \dfrac{1}{x}+ \dfrac{1}{y} + \dfrac{1}{z}=1$ for $w \le x \le y \le z$, all being positive integers.

– This problem is quit easy to solve but interesting to understand steps, how it is solved. One with regular math knowledge would know that there are fourteen (14) solutions for the problem. Some where this problem is also called Egyptian Fractions Problem.

## Problem

1. Prove that ${(x+y)}^n-x^n-y^n$ is divisible by $xy(x+y) \times (x^2+xy+y^2)$ if $n$ is an odd number not divisible by $3$.
2. Prove that ${(x+y)}^n-x^n-y^n$ is divisible by $xy(x+y) \times {(x^2+xy+y^2)}^2$ if $n \equiv \pmod{6}$

## Solution

1.Considering the given expression as a polynomial in $y$, let us put $y=0$. We see that at $y=0$ the polynomial vanishes (for any $x$). Therefore our polynomial is divisible by $y$. Similarly, it is divisible by $x$ as well. Thus the polynomial is divisible by $xy$.
To prove that it is divisible by $x+y$ , put $x+y=0 \ {or} \ y=-x$. It is evident that for odd n we have : ${(x+(-x)}^n-x^n-{(-x)}^n = 0$ for $y=-x$.
Consequently, our polynomial is divisible by $x+y$. It only remains to prove the divisibility of the polynomial by $x^2 +xy+y^2$ , which also be written as $(y-x\epsilon)(y-x{\epsilon}^2 )$ where $\epsilon^2+\epsilon+1=0$.
For this purpose it only remains to replace $y$ first by $x \epsilon$ and then by $x\epsilon^2$ to make sure that with these substitutions the polynomial vanishes. Since, by hypothesis, $n$ is not divisible by 3, it follows that $n=3l+1 \ or \ 3l+2$, for every $l \in \mathbb{Z}$, in which $3l+1$ is not acceptable since $n$ is odd from the problem. At $y=x\epsilon$ the polynomial attains the following value
${(x+x\epsilon)}^n-x^n-{(x\epsilon)}^n=x^n [{(1+\epsilon)}^n-1-\epsilon^n] \\ =x^n {(-\epsilon^2)}^n -1 -\epsilon^n ....$ since ($1+\epsilon + \epsilon^2=0$) substituting $n=3l+2$ we get
$1+\epsilon+\epsilon^2 =0$
Likewise we prove that at $y=x\epsilon^2$ the polynomial vanishes as well, and consequently, its by divisibility by $xy(x+y) \times (x^2+xy+y^2)$ is proved.
2.To prove the second statement, let us proceed as follows. Let the quantities ${-x, -y, \, and \, x+y}$ be the roots of a cubic equation $X^3-rX^2-pX-q=0$. Then by virtue of the known relations between the roots of an equation and its coefficients we have $r=-x-y-(x+y)=0 \\ -p=xy-x(x+y)-y(x+y)$ or $p=x^2+xy+y^2$ and $q=xy(x+y)$.
Thus, $-x, \, -y \, x+y$ are the roots of the equation $X^3-pX-q=0$ where $p=x^2+xy+y^2$ and $q=xy(x+y)$
Put ${(-x)}^n-{(-y)}^n+{(x+y)}^n=S_n$. Among successive values of $S_n$, there exist the relationship $S_{n+3}=pS_{n+1}+qS_n$,: $S_1$ being equal to zero.
Let us prove that $S_n$ is divisible by $p^2$ if $n \equiv 1 \pmod{6}$ using the method of mathematical induction. Suppose $S_n$ is divisible by $p^2$ and prove that then $S_{n+6}$ is also divisible by $p^2$.
So, using this relation we get that
$S_{n+6}=p(pS_{n+2} + qS_{n+1}) + q(pS_{n+1}+qS_n) \\ =p^2S_{n+2}+2pqS_{n+1}+q^2S_n$.
Since, by supposition, $S_n$ is divisible by $p^2$ , it suffices to prove that $S_{n+1}$ is divisible by $p$. Thus we only have to prove than $S_n={(x+y)}^n+(-x)^n+(-y)^n$ is divisible by $p=x^2+xy+y^2$ if $n \equiv 2 \pmod{6}$, we easily prove our assertion. And so, assuming that $S_n$ is divisible by $p^2$, we have proved that (from induction) $S_{n+6}$ is also divisible by $p^2$. Consequently $S_n ={(x+y)}^n+(-x)^n+(-y)^n={(x+y)}^n-x^n-y^n$ for any $n \equiv 1 \pmod{6}$ is divisible by $p^2={(x^2+xy+y^2)}^2$.
Now it only remains to prove its divisibility by $x+y$ and by $xy$ , which is quite elementary.