# Combinatorial Puzzle

Standard

This is a continuation of previous post:

How many distinct numbers can be formed by using four 2s and the four arithmetic operations $+,-,\times, \div$.

For example:
$1 = \frac{2+2}{2+2}=\frac{2}{2}\times\frac{2}{2}$
$2 = 2+\frac{2-2}{2}=\frac{2}{2}+\frac{2}{2}$
$3 = 2+2 - \frac{2}{2}$
$4 = 2+2+2-2 = (2\times 2) + (2-2)$
(note that some binary operations do not make sense without parenthesis)

I have no idea about how to approach this problem (since I am not very comfortable with combinatorics). So any help will be appreciated.

# Arithmetic Puzzle

Standard

Following is a very common arithmetic puzzle that you may have encountered as a child:

Express any whole number $n$ using the number 2 precisely four times and using only well-known mathematical symbols.

This puzzle has been discussed on pp. 172 of Graham Farmelo’s “The Strangest Man“, and how Paul Dirac solved it by using his knowledge of “well-known mathematical symbols”:

$\displaystyle{n = -\log_{2}\left(\log_{2}\left(2^{2^{-n}}\right)\right) = -\log_{2}\left(\log_{2}\left(\underbrace{\sqrt{\sqrt{\ldots\sqrt{2}}}}_\text{n times}\right)\right)}$

This is an example of thinking out of the box, enabling you to write any number using only three/four 2s. Though, using a transcendental function to solve an elementary problem may appear like an overkill.  But, building upon such ideas we can try to tackle the general problem, like the “four fours puzzle“.

This post on Puzzling.SE describes usage of following formula consisting of  trigonometric operation $\cos(\arctan(x)) = \frac{1}{\sqrt{1+x^2}}$ and $\tan(\arcsin(x))=\frac{x}{\sqrt{1-x^2}}$ to obtain the square root of any rational number from 0:

$\displaystyle{\tan\left(\arcsin\left(\cos\left(\arctan\left(\cos\left(\arctan\left(\sqrt{n}\right)\right)\right)\right)\right)\right)=\sqrt{n+1}}$.

Using this we can write $n$ using two 2s:

$\displaystyle{n = (\underbrace{\tan\arcsin\cos\arctan\cos\arctan}_{n-4\text{ times}}\,2)^2}$

or even with only one 2:

$\displaystyle{n = \underbrace{\tan\arcsin\cos\arctan\cos\arctan}_{n^2-4\text{ times}}\,2}$

# Numbers and Logic

Standard

I am a big fan of number theory. I find the answer to Hilbert’s Tenth Problem fascinating. I was introduced to this problem, a couple of years ago, via the documentary titled : “Julia Robinson and Hilbert’s Tenth Problem“, here is the trailer:

You can read more about it here. Also for the sake of completeness, let me state Hilbert’s Tenth Problem:

Does there exist an algorithm to determine whether a given Diophantine equation has a solution in rational integers?

In 1970, Yuri Matiyasevich completed the solution of this problem by using the concept of Turing Machine. This short video provides a nice overview about Turing Machines in general

The answer to Hilbert’s Tenth Problem problem is

No such algorithm exists.

This interplay of number theory and logic is really interesting, isn’t it? But I can’t discuss solution of Hilbert’s Tenth Problem here, since I have never read it. But there is nice overview at Wikipedia.

I will rather discuss a puzzle from Boris A. Kordemsky’s book which illustrates the idea of this interplay.

Ask a friend to pick a number from 1 through 1000. After asking him/her ten questions that can be answered yes or no, you tell him/her the number. What kind of question?

The key to the solution is that 2 to the tenth power is 1024 (that is, over 1000). With each question you knock out half the remaining numbers, and after ten questions only the thought number is left.

I welcome you to think of a number and write the corresponding yes/no questions as a comment below.

# Little Things Matter

Standard

This is a very famous puzzle.  Here is motivation:

Infinite Chocolate (gif from 9gag.com)

Now consider following variation.

Where does the hole in second triangle come from? (image credit: Rookie1Ja , http://brainden.com/forum/index.php?/topic/139-64-65-geometry-paradox/)

The 64 = 65 paradox arises from the fact that the edges of the four pieces, which lie along the diagonal of the formed rectangle, do not coincide exactly in direction. This diagonal is not a straight segment line but a small lozenge (diamond-shaped figure), whose acute angle is

$\arctan(\frac{2}{3}) - \arctan( \frac{3}{8}) = \arctan (\frac{1}{46})$

which is less than 1 degree 15′ . Only a very precise drawing can enable us to distinguish such a small angle. Using analytic geometry or trigonometry, we can easily prove that the area of the “hidden” lozenge is equal to that of a small square of the chessboard.

It looks like a triangle, because a thick line was used. Hypotenuse of the composite triangle is actually not a straight line – it is made of two lines. Forth cusps are where the arrows point (c9, l6).

Also there is an interesting video illustrating this in real life:

# Solution : Free cab ride

Standard

It has been one month since I posted the puzzle. But since nobody solved it, here is my solution.

Let’s consider examples:

 Number of people Number of free rides 1 0 2 2 3 4 4 6

I can illustrate above counting with simple figure:

Each line segment represent two free rides for the group, since every time you refer someone, both referee and new customer get free ride.

From above observations we can conclude by Principle of Mathematical Induction, (try yourself!):

A group of $n$ people can enjoy at most $2(n-1)$ rides.

# Layman’s RSA algorithm

Standard

Why a layman should care about RSA: Your all “secure” online transactions are based on RSA encryption!

RSA stands for  the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm of one of the first practical public-key cryptosystems which is widely used for secure data transmission. In this blog post I will try to illustrate the RSA algorithm using a puzzle (that I came across during my summer internship in Delhi):

Suppose there are two scientists, G and S (assume G to be male and S to be female for ease of writing), collaborating on a classified research. Both live far apart and S want to send a chemical for testing to G. She designs a box with two latches for locking (see photo below), so that two different locks can be used to lock the box. [Assume that if any lock is tried to be broken, the chemical will spill and evaporate].

Two such latches are there

Now, S locks one of the latches and keeps the key with herself and sends the box to G. When G receives the box, he locks the other latch and keeps that key with himself.

G then returns the box to S. When S receives the box, she unlocks her lock and sends the box again to G. When G again receives the box, he unlocks his  lock.

Voilà! the chemical has been securely sent by S to G and that too without exchanging the keys.

If we make the above physical “lock” an abstract entity (i.e. numbers!),  and minimize the possibility of breaking lock (like in above illustration, breaking lock caused loss of chemical), what we get is the RSA encryption.

For Mathematics behind RSA encryption refer: http://blogs.ams.org/mathgradblog/2014/03/30/rsa/#sthash.ce5YIAO6.dpbs

# Two Gems

Standard

I would like to share following two mathematical problems which were brought to my knowledge by different people.

• Boy or Girl Paradox by Guru

Statement of the problem is:

X has two children.  Find the probability that:

•  Both children are girls, given that the older child is a girl.

• Both children are boys, given that at least one of them is a boy.

Some historical reference can be found at Wikipedia: http://en.wikipedia.org/wiki/Boy_or_Girl_paradox

Also you can refer to this interesting paper published on this problem by Peter Lynch : http://mathsci.ucd.ie/~plynch/Publications/BIMS-TwoChildParadox.pdf

• The twelve-coin problem by Sagar Shrivastava

Statement of the problem is:

There is a pile of twelve coins, all of equal size. Eleven are of equal weight. One is of a different weight. What are minimum number of times one need to weigh to find the faulty coin and determine if it is heavier or lighter?