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
Source: Rishab Vaid
Friday, 24 October 2014
Thursday, 18 September 2014
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
Source: Shahbaz also CSE blog
Friday, 12 September 2014
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
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
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
Tuesday, 9 September 2014
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
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
Sunday, 24 August 2014
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.
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.
Monday, 28 July 2014
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
Add to commited changes by git commit --ammend -m "some message"
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
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.
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.
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 wiseyou 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
Subscribe to:
Posts (Atom)