2n points on circle

 Read this puzzle somewhere. 2n points are distributed along a circle in equidistant manner. 2 points are chosen at random and a line drawn between them. 2 points are chosen again randomly from the rest of 2n-2 points and line is drawn between them. What is the probability these lines intersect (inside the circle).

Another way to frame the same question is to randomly select 2 points on the circle draw a line and then randomly select another 2. find probability on intersection.

 

2nd part: Given n chords chosen at random on a circle. What is the expected number of chords that will intersect.

Petrol pump in a circle

There are n petrol pumps in a circle of circumference L, distributed in an arbitrary manner. Each petrol pump gives $a_i$ quantity of petrol s.t. $\sum_i a_i = L$. You have a car which consumes $x$ quantity for covering distance $x$. You start at an petrol pump with empty tank. Show that there exists an petrol pump starting at which you would be able to go round the circle. (Asked by Rustomji)

Some similar puzleson inclusion-exclusion

Inclusion exclusion is a common technique for lost of combinatorics puzzles. Here are two I recently encountered:

0. At the banquet of a large conference, n mathematicians hang their coats on the coat rack as they enter. At the end of the night they leave in a drunken stupor, each one randomly putting on a coat without checking that it’s their own. Show that in the limit as n → ∞, the probability that none of the mathematicians staggers home in their own coat approaches 1/e. 

1. 6 persons are standing in a line what is the probability that no three consecutive people are in increasing order of their heightsalso see: https://artofproblemsolving.com/wiki/index.php/Principle_of_Inclusion-Exclusion

2. 6 babies are born in a hospital on either monday, tue, wed, thu. What is the probability that there was no day when no baby was born?

3. 10 people numbered uniquely in 1-10 are uniformly randomly given 10 tickets uniquely numbered b/w [1,10]. What is the probability that none of them get the ticket with same number as the number assigned to them. 

Probability $n$ uniform random points lie on a semicircle

Nice puzzle I read on Saurabh Joshi's blog. What is the probability $n$ uniform random points will lie on a semicircle.

Some problems on sum of subarray that look similar

1) Given an array of non-negative integers and input $x$, find the subarray which sums exactly to $x$. Find $O(n)$ solution

2) No constraints on numbers on array, find the max sum subarray in $O(n)$ time.

3) Given an array of integers and an input $x$, find the subarray with sum closest to $x$ in $O(n\log n)$ time

Expected number of tosses for consecutive heads

Geometric distribution with parameter $p$ is the number of tosses of biased coint to get first head. The distributions is given by $P(X=k) = (1-p)^{k-1}p$. The expected number of tosses to get first head is $\frac{1}{p}$. Now, the question is to find the expected number of tosses to get the first HH pattern.

Testing latex support

I had tried adding latex support earlier, using this stack exchange link.  It didn't work, perhaps due to the 'Awesome inc' template I was using. I have now switched to 'simple' template. Let's see if it works  and drum rolls.....voila! $$\LaTeX$$ Easy to use and it is better than wordpress. Wordpress has annoying border around all the tex renderings which I couldn't get rid of.

More examples, inline fraction : $\frac{2}{3}$, $\mathcal{R},\mathbb{R}$ \(\begin{pmatrix} 1 &2 \\ 3 &4 \end{pmatrix}\)

Puzzle #8: Three dart puzzle

You are throwing darts at a dart board, aiming at the center. The second dart hit the board farther from the center than the first. What is the probability the third dart will also hit the board farther from the center than the first? Assume that all the throws are independent.

Puzzle #7: Card reversal

You have n cards, numbered 1 to n. Following operations are performed repeatitively:

1. Choose the top most card. Say it is numbered i
2. Reverse all the cards from 1 to i

This process stops when card #1 comes on the top. Prove that eventually the process stops

Source: CSE_blog

The Monty Hall puzzle

In a game show there are three doors. Behind two doors is a goat and behind the other door is a car. As a contestant, you want to win the car. Now, the hosts asks you to choose a door. Then the host goes ahead and opens one of the other two doors  which has a goat behind it. Now, he gives you an option to switch your choice. Should you switch?

It is important to mention that the host:  1) never opens the chosen door 2) always opens the door which has a goat behind it. 

Initially we have no information about the winning door. All the doors have equal 1/3 probability of being the winning door. Once, the host opens a door which has a goat behind we get more information. The inference we can draw based on the nature of the host is that the door which was left unopened is likely to have the car behind it, otherwise the host could have chosen that door instead. It is more clear from an extension of this question, where say there are 1000 doors with 999 having goat behind them. The host this time opens all except the chosen and one other door. Think, why would the host leave just this one door from the 999 possible doors. There are two possibilities 1) You chose the right door initially but chances of that are rather low .001, considering your choice is uniform random initially.  In this case the host could have chosen any door and switching will make you lose. 2) You chose the wrong door initially, the chances of which are 0 .999. In this case host has no choice but to leave the door with car behind untouched, In this case, switching will make you win. So, notice that if you do 1000 random runs, then in expectation 999 times you will make the wrong choice initially and switching will make you win, 999/1000 times. On the other hand, 1/1000 switching will make you lose. For three doors, it is the same argument for 3 doors: switching will make you win 2/3 times. 

We can make this analysis more rigorous, by defining some random variables. Let 1,2,3 denote the door numbers. Following are random variables for this process: Your initial choice (YC), host's choice (HC) and the door with car behind it (DC). Note, YC, HC and DC \in {1,2,3). Let's say that the car is deterministically behind door 1 i.e.

P(DC=1) = 1

 Considering the initial choice of player to be uniform random 

P(YC=1) = P(YC=2)=P(YC=3)= 1/3

As host's choice depends on player's choice HC is not independent of YC.  If you choose door 1 i.e. the winning door, host can choose any of  the other two doors with equal probability.

P(HC=2|YC=1) = P(HC=3|YC=1) = 1/2

Based on nature of the host we know:
1) The host will never choose the door with the car behind it:

P(HC=1|YC=*) = 0

2) The host will never choose the door that you have chosen:

                                                                  P(HC=x|YC=x) = 0

If you choose the wrong door, the host has no choice

P(HC=3|YC=2) = 1 and P(HC=2|YC=3) = 1

Let's calcualte, P(YC=DC|HC) which is the probability of your initial choice being the winner given the hosts choice. For our simplified case we have assumed DC=1 deterministically, hence we need to compute P(YC=1|HC). As these are not independent, P(YC=1|HC) \neq P(YC=1) staraight away. But by bayes rule, 

P(YC=1|HC) = P(HC|YC=1)P(YC=1)/(P(HC|YC=1)P(YC=1)+...+P(HC|YC=3)P(YC=3))

From previous computation of conditionals, P(YC=1|HC=1)  = 0.  

                                               P(YC=1|HC=2) = 1/2*1/3/(1/3*(1+1/2))  = 1/3 

This is the probability of winning without switching. You will win on switching if your initial choice was wrong i.e. P(YC\neqDC|HC) = P(YC=2|HC)+P(YC=3|HC). For HC = 2, this is just

                                               P(YC=3|HC=2) = 1*1/3/(1/3*3/2) = 2/3

For HC = 3,

                                              P(YC=2|HC=3) = 1*1/3/(1/3*3/2) = 2/3

Puzzle #6: Probability of centre of square inside circle

Select two points uniformly randomly inside a square. What is the probability that the center of the square will lie inside the circle drawn with these two points as ends of diameter?

Source: Rishab Vaid

Puzzle #5: Save the king

Problem: There are 500 barrels of wine and exactly one of them is poisoned. The king wants to identify the poisoned barrel but he is ready to sacrifice only 4 prisoners. They have 4 days to find the poisoned barrel. The poison has the property that after consuming it one can die anytime in the next 24hrs. Give the strategy to find the poisoned barrel.

Source: Shahbaz  also CSE blog

Puzzle #4: Stop the roll

Problem: You are in a dicey situation. You friend gave you a dice and asked you to keep rolling till you get a sum of 100 or more. Now,you have to tell the most probable number at which you are going to stop.

Solution: You will stop at or before 105. Now, trick is to think backwards. You can get 105, only if you ever reach 99. Similarly, you can get 104, only from 99 or 98. You can get to 100, from maximum previous sums i.e. 94, 95, 96, 97, 98 and 99. Therefore, 100 is the most probable stopping point.  P(105) = P(105|99).P(99) = P(99)/6 . Similiarly, P(104) = (P(99)+P(98))/6, ...P(100)  = (P(94)+...+P(99))/6

Source: Rishab

Maths puzzle #3- XOR magic

Problem: You are given a set of n numbers, C = { c_1, c_2, ..., c_n}and you have to find the minimum size of subset of C from which you can create the given n numbers by only doing xor operations on the elements of the subset.

Solution: One starts by thinking about the properties of XOR. There are only a few properties that I know, like x + y + x = y ( I'll represent XOR by + through out the post). So, I have to find a subset V = { v_1, v_2,...,v_k} such that a_i1*v_1+a_i2*v_2+...+a_ik*v_k = c_i, for all elements of C and a_ij are either 0 or 1. This looks similat to c_i being linear combination of V. So, we check if there is a vector space with XOR as the addition operation and voilà, if a euclidean vector space is over the field Z_2, then addition operation is x+y % 2 which is the definition of XOR. So, now all we need to find is the rank of matrix [c_1 c_2 ...c_n] . To find the rank reduced matrix by elementary operations (gauss elimination)

Source: Rishab Vaid  who read it perhaps on Topcoder

Maths puzzle #2 - Divisibility by 100

Given any 51 integers, prove that there exist two integers a, b such that a^2 - b^2  is divisible by 100

Solution: Start thinking by why only 51? If we divide any number by 50 it will give 50 possible remainders, which means there are two integers a, b which give the same remainder. So, a = 50q1+r and b = 50q2+r where 0<= r < 50.

a^2 - b^2 = (a-b)*(a+b) = 50(q1-q2) * 2(25(q1+q2)+r), hence divisibility by 100

Source: Manish asked me this problem, who was in turn asked by Rustam, who read it in Mathematical circles: the russian experience

Maths Puzzle #1

Source: CSE blog

Question: A random permutation of integers from 1 to N is arranged in a circle. Prove that there exist k consecutive integer with sum >= k(n+1)/2

Observation: In several puzzles where a comment has to be made about the sum, it is worthwhile to look at the average. Here we ask the question what is the average of each group of k-integers? We know the sum of 1 to n is  n(n+1)/2. But in our case every number is part of multiple groups, for ex: number at kth position from start is part of group number 1,2,....k. So every number appears k times, making total sum of all the k-integer groups to be k*n*(n+1)/2. As there are total of n such groups (again count!), average sum of these n groups is k*(n+1)/2, implying there exist a group with value greater than equal to k*(n+1)/2

A stronger statement can also be made if n/k is an integer. There are (n/k) disjoint groups of size at least k. These (n/k) groups can be identified by mentioning the start position. Example, if we start at element 1, the n/k groups will start from 1, k+1, 2k+1,... ((n/k)-1)*k+1. Total sum of these (n/k) groups is n(n+1)/2, thus average sum of each group is n(n+1)/(2*(n/k)) = k(n+1)/2, thus there is at least one group among these n/k groups with sum >= n(k+1)/2

If instead of starting at 1, we start at two, we will get a entirely different set of n/k groups of size k each. In this way we can continue till the start point is k. Thus there will be k different groups of size k each such that there is sum is >=k(n+1)/2

Average trick works in several other puzzles as well. Kaizad rustomji gave me some of those which I'll post later.

Github - basics

This is a basic step by step process to get started with github and git
1. install git and sign up on github
2. Start by creating a repository which is basically a project
3. on your local machine use git clone <repository_address>
4. Step 3 will download all the files from github in the current location on the local machine
5. Make changes to the file and use git add <filename> to add to local repository
6. Use git commit to commit to the repository
7. Finally use git push to push the current version to github

Use git pull to pull from a repository
Tutorial :http://gitimmersion.com/lab_13.html
Repository is a project
Commit is like a revision of a file. Git every time you save it creates a unique ID (a.k.a. the "SHA" or "hash") that allows you to keep record of what changes were made when and by who

Branch: Branch is a parallel version of repo. the "master" branch is the primary branch which has the live code. When you want to make some change, create a new branch, make changes and merge your branch back with master branch. Merging is done via "pull". which means pulling a branch in another I suppose. To merge your changes with master, you create a "pull request" which is accepted/rejected by repository collaborators.

A fork is a copy of a repository. Fork someonelse repository to for ex createing a patch and send a pull request. If you plan to send a pull request then you also need to keep uptodate with the changes in the original (and not forked) repository. You can setup this by specifiying upstream in your forked repository.
git remote -v gives you the current remote repo.
Add upstream by git remote add upstream https://original-repo-as-upstream

Once you have a fork you can do whatever you want without impacting the opriginal project. 
1. You can create a branch and add your changes
2. And send a pull request if you want to merge back.

#Get Add, commit 
Once you make changes to file, git knows that the file has changed. (do git status)
but it doesn't know if it should actually recreate hash (which commit does) . So the next step is to "stage" the file for commit by doing git add filename. To commit everything that is staged you do git commit -m "message". 

Git only save the changes you made not the entire file. There for if you make some changers to a file, do a git add fname.txt and git commit -m "change1". Followed by more changes., Now the latest (version) commit has only the initial change and not the latest change. You have to stage and commit the new changes. 

The commits pile up on the stack as you nake changes to your file, but you can go back anytime by using checkout command. git checkout <hash> takes you to the hash version. 

Revert unstaged changes by git checkout <filename>

Revert commited change git revert HEAD (to revert last commit) or git revert <hash> for some othere commit.


HEAD: the current commit your repo is on. Most of the time HEAD points to the latest commit in your branch, but that doesn't have to be the case. HEAD really just means "what is my repo currently pointing at". In the event that the commit HEAD refers to is not the tip of any branch, this is called a "detached head"

Add to commited changes by git commit --ammend -m "some message"

Branch:

git checkout -b <branchname> is a shortcut for git branch <branchname> followed by a git checkout <branchname>.

Merging:

Merging brings the changes in two branches together. Let’s go back to the greet branch and merge master onto greet. By merging master into your branch periodically, you can pick up any changes to master and keep your changes in greet compatible with changes in the mainline.

Get changes from remote:
git fetch will fetch the commit from remote branches but will not merge with local branch.
To merge to local git merge origin/master
You can combine these two together by doing git pull

// MEssed up your local dev branch

git fetch origin  (gets current changes...this is important other wise

you may miss changes)

git reset --hard origin/master

Deleting:
Locally: git branch -d branch_name 
This deletes local branch if it is fully merged with upstream.

git branch -D branch_name
This forcce deltes the branch irrespective of merging. 
Its shorthand for git branch --delete --force

To delete remote branch do 
git push origin --delete branchname
IF you say git checkout -b <branch> it takes you to the latest version of this branch. git branch --all gives a list of all branches. Current branch is shown with HEAD pointer. 

.

Master:  The name of the default branch that git creates for you when first creating a repo. In most cases, "master" means "the main branch".The default name that git gives to your main remote repo. Your box has its own repo, and you most likely push out to some remote repo that you and all your coworkers push to. That remote repo is almost always called origin, but it doesn't have to be.

git pull = git fetch+git merge  

Project Ideas

Very little guidance in my current project. It seems like I have been dropped into an ocean when I was still making myself comfortable in a swimming pool. I have a very large data set approximately 9x10^8 entries and as each of them is a 64 bit double it takes up a lot of space = 7.2 GB, it is impossible to fit into the memory given all the other variables that I want to store. I tried using float but that gave me strange results.

Another concern is that the data is very sparse. In a matrix of size 9million X 3 million, I have only 14 million non zero entries, now most of the rows have nearly one or 2 non zero entries.  On an average every row has less than 2 non zero entries. Need to think

Project Ideas : Old and new

1. Application to aggregate donations for humanitarian cause
2. Matter: Crowd sourced news platform
3. 

Another problem unsolved

Couldn't solve this problem...feeling disappointed :(

Some puzzles

Sometimes I feel I am so dumb that I should not be allowed to solve puzzles. I spent the complete day today to figure out my mistake in this simple problem on codechef june long contest. I figured out the solution in first 10 minutes but was handling a simple corner case in the wrong way. The worst part is I tested my code on the corner case multiple times and overlooked the error. What a dumbass I have turned out to be. Any way, I am still not able to figure out the solution to the next problem.

Dheeraj Baba also told me some puzzles today...I will mention them here and think about them.
1) One based on the famous handshaking lemma: In a party there are 5 couples including the host. Every person in the party shakes hand with every person he doesnt know. At the end of the party the male host announces that he asked every one the number of hands the shook and everyone gave a different answer. How many hands did the female host shook? The host mayn't know everyone they invited.

2) Given a tree, find the two vertex which are maximum distance apart?
3) What is the minimum number of coins of giver denomination required to make a sum of N? see this
4) Number of possible configurations of a rubic's cube?