Tuesday, February 21, 2017

At least one of 3 consecutive odd numbers is a multiple of 3


The way to approach this problem is to show that there will always be a number among three consecutive odd numbers that is divisible by $3$. Let three consecutive odd numbers be $2n+1,2n+3,2n+5$. If $2n+1$ is a multiple of $3$ then we are done. Else the remainder when divided by $3$ is either $1$ or $2$. Suppose its $1$ then it means $2x$ is divisible by $3$ which means $2x+3$ is divisible by $3$. Or suppose the remainder is $2$, which means $2x-1$ is divisible by $3$ which means $2x+2$ and $2x+5$ are divisible by $3$. Hence proved.

Labels: , ,

Variance of Uniform Distribution


Let the corresponding probabilities are $\frac{1}{n+1}$ for all at the points $\{0,1,2,\cdots,n+1\}$ The general formula is $\sigma^2 = E[x^2]-(E[X])^2$ Let's first calculate $E[X]=0\cdot \frac{1}{n+1}+1\cdot \frac{1}{n+1}+\cdots+n\cdot \frac{1}{n+1}=\frac{0+1+2+\cdots+n}{n+1}=\frac{n(n+1)}{2(n+1)}=\frac{n}{2}$ Now lets calculate $E[X]=0^2\cdot \frac{1}{n+1}+1^2\cdot \frac{1}{n+1}+\cdots+n^2\cdot \frac{1}{n+1}=\frac{0^2+1^2+2^2+\cdots+n^2}{n+1}=\frac{n(n+1)(2n+1)}{6(n+1)}=\frac{n(2n+1)}{6}$ Therefore $\sigma^2 = \frac{n(2n+1)}{6}-\left ( \frac{n}{2}\right )^2 $ $\Rightarrow \frac{n(2n+1)}{6}-\frac{n^2}{4}$ $\Rightarrow \frac{2n(2n+1)-3n^2}{12}$ $\Rightarrow \frac{4n^2+2n-3n^2}{12}$ $\Rightarrow \frac{n^2+2n}{12}=\frac{n(n+2)}{12}$ Now suppose we have same $n+1$ terms shifted from $a$ to $b$ in that case the variance becomes $\frac{(b-a)(b-a+2)}{12}$

Labels: ,

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

Factitious (adjective):
Made or manufactured; not natural
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





































Circumspect (adjective)
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. For $2$ 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)-n+1$ 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)$ $\Rightarrow P(A \cap B)= P(A)+P(B)-P(A \cup B)$ as $P(A \cup B) \le 1$ $\Rightarrow P(A \cap B) \ge P(A)+P(B)-1$ This can also be written as $P(A \cap B) \ge P(A)+P(B)-2+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$ $\Rightarrow P(A_1)+P(A_2)+\ldots+P(A_n)-n+1\le P(A_1 \cap A_2 \ldots \cap A_n)$ $\Rightarrow P(A_1 \cap A_2 \ldots \cap A_n)\ge P(A_1)+P(A_2)+\ldots+P(A_n)-n+1$

Labels: ,

Site Meter