## Wednesday, January 04, 2017

### Six deceptive problems that no one can solve

This is the title of the article which appeared here

The problems are
1. Twin Prime Conjecture
2. The Moving Sofa Problem
3. The Collatz Conjecture
4. The Beal Conjecture
5. The Inscribed Square Problem
6. Goldbach Conjecture

I am aware of the problems number 1,3 and 6. So I need to investigate the other 3. Which are Moving Sofa, Beal Conjecture and the Inscribed Square Problem.

Labels:

### How many triangular numbers are also Fibonacci Numbers

I heard this from Bruce Edwards that they are only 5 and these are 1,1,3,21, and 55. I wrote a program in Sagemath to verify that. Here it is Here is the program with its output

def fibo(n):
fib_1 = 1
fib_2 = 1
if n == 1 or n== 2:
return 1
fib_n=0

for i in range(3,n+1):
fib_n = fib_1+fib_2
fib_1 = fib_2
fib_2 = fib_n
return fib_n
def triNumList(n):
a=[]
for i in range(1,n):
b=i*(i+1)/2
a.append(b)
return a

def fiboList(n):
a=[]
for i in range(1,n):
a.append(fibo(i))
return a

def TriFiboCompare(n):
f = fiboList(n)
t = triNumList(n)
print(f)
print(t)
for i in f:
if i in t:
print("Match",i)

TriFiboCompare(100)

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026] [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, 1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, 2628, 2701, 2775, 2850, 2926, 3003, 3081, 3160, 3240, 3321, 3403, 3486, 3570, 3655, 3741, 3828, 3916, 4005, 4095, 4186, 4278, 4371, 4465, 4560, 4656, 4753, 4851, 4950] ('Match', 1) ('Match', 1) ('Match', 3) ('Match', 21) ('Match', 55)

Labels: , ,

## Tuesday, January 03, 2017

### Tiling a deleted 64 grid using dominos

This is a classic problem that can be found in most books on problem solving and I re-encountered on my reading of Mathematics a Very Short Introduction by Timothy Gower. The problem is if you delete the two diagonal squares of a 64 grid squares like a chess board and then you have to tile it using dominos. The way to do is to think of is to realize that each domino occupies a black and white square. Assuming that the two black squares were deleted. There are now 62 squares in total out of which 32 are white and 30 are black. So no matter how we tile. We will be left with 2 white squares and since a domino tiles only black and white those two will remain untiled.

Labels: ,

## Friday, December 23, 2016

### Trials until first success

This is a famous problem in 50 challenging problems in probability. The question is On the average, how many times must a die be thrown until one gets a 6 ? Let p be the probability of getting a 6. Now we can get this at first trial with probability $p$, on 2nd trial with probability $(1-p)p$, or on 3 trial with $(1-p)^2p$ and so on. The expected value is $N= 1p+2(1-p)p+3(1-p)^2p+4(1-p)^3p+\cdots$ $\Rightarrow N(1-p)=1(1-p)p+2(1-p)^2p+3(1-p)^3p+4(1-p)^4p+\cdots$ Subtracting we get $\Rightarrow N(1-1+p)=p+(1-p)p+(1-p)^2p+(1-p)^3p+\cdots$ $\Rightarrow Np= p((1-p)+(1-p)^2+(1-p)^3+(1-p)^4+\cdots$ $\Rightarrow N= \frac{1}{1-(1-p)}$ $\Rightarrow N= \frac{1}{p}$ Thus if the probability of success is $p$. On an average it will take $\frac{1}{p}$ number of trials for the first success.

Labels: ,

## Saturday, December 10, 2016

### Factitious, Facetious and Circumspect

Made up in the sense of contrived; a sham, fake or phony
The CIA agent hid his message inside the hollow factitious rock by the bridge; his handler would pick up the message a few hours later.
My dad's factitious smile didn't fool anyone; he was definitely not happy to see our cousins show up once again unannounced.

Facetious

Cautious, Prudent
Circumspect is a combination of circum ("around") and spect ("look"). To remember this word, think of a cautious person "looking around" before he or she acts.

### Factotum and Procrustean

Two new words Factotum: A factotum is someone hired to do a variety of jobs, someone who has many responsibilities, a jack of all trade.
Example: Tessa, the office factotum, does the billing, answers the phones, helps out in the PR department, and even knows how to cook a mean blueberry scone- she's indispensable. Andrea in my school is a factotum. "fac" is a latin word for facio, meaning to make or do. "totum" means all. Therefore factotum is someone who does all. Other example: The intendant became the king's factotum. Gallop off to Texas, he said to the factotum who appeared at his call.

Procrustean: Procustes was a mythical bandit of Attica who would waylay hapless travelers and attempt to fit them to his iron bed. If travelers were too long for the bed, he'd cut off their feet. If they were too short, he'd stretch them out. A procrustean bed has come to mean an arbitrary standard to which something is forced to confirm.

Even though student's poem unanimously won all county writing contest, the procrustean English teacher gave her an F for failing to do the i in her name.
I was shocked by their procrustean attitude towards completing the syllabus. I think a teacher is a best judge of determining the pace of the class.

## Sunday, December 04, 2016

### Locks in a grid problem

This is a simulation to an interesting problem about a lock. Which has n key slots. These slots are either vertical or horizontal. To open the lock these slots have to be in a particular configuration. If we put the key in one slot and turn its orientation all the other slots in that particular row and column change their configuration. Is it possible to open this lock for a particular configuration of 16 slots ? If yes then how ?
       

"""The purpose of this is to simulate the problem of locks
where when you turn on the key in the grid all the other
keys in the same row and column also turn. I represent this
by 0 and 1
One can experiment and learn that if the grid is even by even
then we can change any particular bit by"""
n = 4
a=[]
sum = 0
# It prints the whole Grid of Locks
def printMatrix(val):
for i in range(n):
print(val[i])

# It flips the entries from 0 to 1 and 1 to 0
def flip(val):
if val == 0:
return 1
return 0

# It changes the entries in a given row and column
def ChangeRowChangeColumn(a,i,j):
a[i][j]=flip(a[i][j])
for k in range(n):
a[i][k]=flip(a[i][k])
for k in range(n):
a[k][j]=flip(a[k][j])

for i in range(1,n+1):
b=[]
for j in range(1,n+1):
b.append(1)
c = b[:]
sum= sum+n
a.append(c)
del b[:]
printMatrix(a)
flag=1
while(flag == 1):
row=int(input("Enter what row you want to change ?"))
col=int(input("Enter what column you want to change?"))
ChangeRowChangeColumn(a,row,col)
printMatrix(a)
flag = int(input("Enter 0 or 1 to continue"))




Labels: ,

## Friday, December 02, 2016

### Bonferroni Inequality and how to think about it

Bonferroni Inequality provides a lower bound for intersection of sets in terms of the individual probability of sets.
It says that $P(A_1 \cap A_2) \ge P(A_1)+P(A_2)-1$ for two sets.

$P(A_1 \cap A_2 \cdots \cap A_n) \ge P(A_1)+P(A_2)+\cdots+P(A_n)-1+n$ for n sets.

Main Idea: The union of sets is always smaller than the sum of the individual sets. You can basically take this as an axiom.
We start with $P(A \cup B)= P(A)+P(B)-P(A \cap B)$ as $1 \ge P(A \cup B)$

$\Rightarrow 1 \ge P(A)+P(B)-P(A \cap B)$

$\Rightarrow P(A \cap B) \ge P(A)+P(B)-1$.

Let's generalize it for $n$ sets.

Notice that $P(A_1 \cap A_2 \cap \ldots \cap A_n)=P((A_1^c \cup A_2^c \cup\ldots \cup A_n^c)^c) = 1-P(A_1^c \cup A_2^c \cup \cdots \cup A_n^c)$

$\Rightarrow 1-P(A_1^c \cup A_2^c \cup \cdots \cup A_n^c) =P(A_1 \cap A_2 \cap \ldots \cap A_n)$

$\Rightarrow P(A_1^c \cup A_2^c \cup \cdots \cup A_n^c) =1-P(A_1 \cap A_2 \cap \ldots \cap A_n)$

Lets start with the idea that probability of union of sets is always smaller than the sum of probabilities of individual sets.
$\Rightarrow P(A_1^c \cup A_2^c \cup \ldots \cup A_n^c) \le P(A_1^c)+P(A_2^c)+\ldots+P(A_n^c)$

$\Rightarrow 1-P(A_1 \cap A_2 \ldots \cap A_n) \le 1-P(A_1)+1-P(A_2)+\ldots+1-P(A_n)$

$\Rightarrow 1-P(A_1 \cap A_2 \ldots \cap A_n) \le n-P(A_1)-P(A_2)-\ldots -P(A_n)$

$\Rightarrow P(A_1)+P(A_2)+\ldots+P(A_n)\le P(A_1 \cap A_2 \ldots \cap A_n)-1+n$

Labels: ,

## Wednesday, November 30, 2016

### Coupon Collector Problem and Python

Collecting Coupons: This is a famous problem in Mosteller's book.
Coupons in cereal boxes are numbered 1 to 5, and a set of one of each is required for a prize. With one coupon per box, how many boxes on the average are required to make a complete set?

Here is a python program to simulate it

"""We store the outputs in a list a until we get all the coupons
The coupons are generated from the randint function which generates
both the end values
The sum variable keep tracks of number of boxes we have been counting
"""
import random
flag = 1
a=[]
sum = 0
n = 1000 # number of times you want to run the experiment
coupNum = 30 # number of different coupons
for i in range(n):
count = 0
a=[]
flag =1
while flag:
x=random.randint(1,coupNum)
#generates random number between 1 and coupNum inclusive
count += 1
#        print(x)
if x not in a:
a.append(x)
flag = 1
elif len(a)==coupNum:
flag=0
#    print(count)
sum = sum+count
#    print(a,count,sum)
del a[:] #delete the list
print(sum/n)

Labels: , ,

### Odds of Craps

Craps

The game of craps, played with two dice, is one of America's fastest and most popular gambling games. Calculating the odds associated with it is an instructive exercise. The rules are these. Only totals for the two dice count. The player throws the dice and wins at once if the total for the first throw is 7 or 11, loses at once if it is 2, 3 or 12. Any other throw is called his "point". If the first throw is a point, the player throws the dice repeatedly until he either wins by throwing his point again or loses by throwing 7. What is the player's chance to win.

Python Program to find the final probability
sum = 8/36
a = {4:3/36,5:4/36,6:5/36,8:5/36,9:4/36,10:3/36}
for i in a:
sum = sum+6*(a[i])**2/(6*a[i]+1)
print(sum)

Labels: , ,