tag:blogger.com,1999:blog-38443311647147014312017-02-05T21:13:41.087+05:30Puzzles for humansCollection of Math, CS and general puzzles.pathankhan salmannoreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3844331164714701431.post-78355804902229981862012-11-27T08:48:00.002+05:302012-11-27T08:48:37.149+05:30SubsetsLet [n] = {1,2,3,....,n}. We divide [n] into m subsets A<span style="font-size: x-small;">1</span>,A<span style="font-size: x-small;">2</span>.....Am, such that they satisfy the properties:<br />1). For all i, <b>|</b>Ai<b>|</b> is odd.<br />2). For all distinct i and j, <b>|</b>Ai <span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19.200000762939453px;">∩ Aj</span><b>|</b> is even.<br />Prove that m<=n, where for a set X, <b>|</b>X<b>|</b> denotes number of elements in X.<br /><br />Courtesy : Prof. <a href="http://www.cse.iitb.ac.in/~sundar/">Sundar Vishwanathan</a>, <a href="http://www.iitb.ac.in/">IIT Bombay</a>pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com0tag:blogger.com,1999:blog-3844331164714701431.post-28912892377371353312012-11-19T00:14:00.001+05:302012-11-19T00:14:18.329+05:30Squared squares<div>There is a square S of unit side. There are n disjoint smaller squares inside S, with sides parallel to the sides of S, where n is a perfect square. Prove that one can always draw a line parallel to some side of S, which passes through S and at most <span style="background-color: white;"><span style="font-family: inherit;">√n smaller squares.</span></span></div><div><span style="background-color: white;"><span style="font-family: inherit;"><br /></span></span></div><div><span style="background-color: white;"><span style="font-family: inherit;">Source : <a href="http://www.algomuse.appspot.com/">Algo Muse</a></span></span></div>pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com0tag:blogger.com,1999:blog-3844331164714701431.post-48236105600575673902012-11-15T00:07:00.000+05:302012-11-21T00:29:45.355+05:30FootballersThere are 23 football players, with some strength associated with each player. To conduct a football match among them, you select a referee and divide the remaining 22 players into two groups with 11 players each and with total strength of one group(sum of strengths of all players) equal to total strength of the other(If possible).<br /><br />The given set of strengths is in a way that it is possible to start a game with any player as referee. Prove that all players have equal strengths.<br /><br />Courtesy : <a href="https://www.facebook.com/vinodreddy.gandra?fref=ts">Vinod Kumar Reddy</a>pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com0tag:blogger.com,1999:blog-3844331164714701431.post-10509439668270674202012-10-05T02:33:00.001+05:302012-10-05T02:33:23.716+05:30Complete this sequenceFind the next term in the sequence 1, 11, 21, 1211. 111221. 312211, 13112221 ?(Not using the polynomial method).<br /><br />Courtesy : Quora.pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com4tag:blogger.com,1999:blog-3844331164714701431.post-89709290130327871172012-09-25T18:14:00.002+05:302012-09-25T18:14:22.825+05:30NecklacesWe say that two necklaces are different if one cant be obtained from another by rotating it (by whatever angle). Calculate the total number of different necklaces possible with N beads of R(<N) different colors.<br /><br />Courtesy : Prof. Sharad Sane - IIT Bombaypathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com2tag:blogger.com,1999:blog-3844331164714701431.post-78331842174803258392012-08-28T19:54:00.002+05:302012-08-28T19:54:58.013+05:30Picking hatsN people come to a room to attend a conference. They leave their hats outside the room. When the conference ended, the people were in a hurry, so they picked one hat each at random, one after another. Given N is considerably large, find the probability that no one gets his/her own hat.<br /><br />Courtesy : Prof. Sharad Sane, IIT Bombay.pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com3tag:blogger.com,1999:blog-3844331164714701431.post-90642736604831791522012-08-24T23:01:00.001+05:302012-08-24T23:01:50.611+05:30The "ballot" problemThere are two candidates contesting for a post, A and B. Elections have ended and A got total a votes and B got total b votes, with a > b. Every person voted must vote for either A or B. They shuffled the ballot box and started counting. A is declared winner only if he leads at every point of counting. What is the probability that A will win the elections?<br /><br />Courtesy : Prof. S.B. Pillaipathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com2tag:blogger.com,1999:blog-3844331164714701431.post-53174913602194320442012-08-20T18:09:00.000+05:302012-08-20T18:12:14.394+05:30Connect the pyramidsWe have two pyramids, a square-base right pyramid and a triangle-base right pyramid. All the edges of both the pyramids are of equal length. We joined both the pyramids with one of the triangle-faces of one pyramid coinciding with one of the triangle-faces of another. What are the total number of faces of the new solid figure obtained?<br /><br />Source : Winkler - Mathematical puzzles (Please go through this book. It is really good)pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com3tag:blogger.com,1999:blog-3844331164714701431.post-90307124827351324512012-08-16T15:19:00.002+05:302012-08-16T15:19:24.250+05:30The "Mailbox" problemWe have n mailboxes, which each have a key and all keys are distinct. There is a master key which works for every mailbox.<br /><br />Now, each key is put in one mailbox, and all mailboxes are locked using the master key.<br /><br />So, what we have here is n locked mailboxes, which each has a key to one of those n mailboxes.<br /><br />You want to open all the boxes. To start with, you have to break one box, take key from that, and open its corresponding box. When you find key to first box, you have to break another box and so on.<br /><br />So, given you can break k boxes, what is the probability that you will be able to open all the mailboxes?<br /><br /><span style="background-color: white; color: #444444; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">Courtesy: Prof. Sharad S. Sane, IIT Bombay.</span>pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com2tag:blogger.com,1999:blog-3844331164714701431.post-61309305018643850212012-08-08T02:13:00.003+05:302012-08-08T02:13:39.302+05:30Sequence of non-powers of primesGiven a natural number n, prove that we can always find out n consecutive natural numbers such that none of them is a perfect power of any prime.<br /><br />Courtesy: Vinod reddypathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com2tag:blogger.com,1999:blog-3844331164714701431.post-58828884158498280982012-08-01T13:12:00.001+05:302012-08-01T13:12:31.728+05:30Factorial-base representationShow that every non-negative integer n can be uniquely represented as<br /><br />n = a1*(1!) + a2*(2!) + a3*(3!) ...........<br /><br />where all ai are integers and 0 <= ai <= i for all i.<br /><br />Courtesy: Prof. Sharad S. Sane, IIT Bombay.pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com0tag:blogger.com,1999:blog-3844331164714701431.post-76160024623540735932012-07-26T14:14:00.000+05:302012-07-26T14:14:27.083+05:30City-roadsThere is a country consisting of N cities, just built. So, now you must build roads for the cities. Each road is a two-way path joining two cities. The way it works is, in one turn, you must choose two cities, and if there is no road between them, build a road, else, leave it as it is. What is the estimated number of turns required to build the roads such that there is a way from every city to every other city?<div><br /></div><div>Courtesy : Aakash rao NS</div>pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com2tag:blogger.com,1999:blog-3844331164714701431.post-34357555091271437382012-07-22T20:36:00.003+05:302012-07-22T20:36:39.013+05:30Divisor - NimAlice and Bob are back in gaming. This time it is with numbers. They take a jar containing all the numbers from 1 to n. The game goes on like this. Alice starts the game, she picks a number x from numbers in the jar. Then, she removes all the divisors of x (including x). Alice and Bob repeat the steps without replacement. The player to draw the last number wins. Who will win the game (in terms of n if it depends on n) ?<br /><br />Courtesy : Vinodpathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com2tag:blogger.com,1999:blog-3844331164714701431.post-91745547036600217272012-06-22T10:08:00.001+05:302012-06-29T01:00:41.524+05:30Complete the sequenceFind the next element in the sequence:<br />10 11 12 13 14 20 22 ... (Without using the polynomial-method)<br /><br />Courtesy: QED 2012pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com0tag:blogger.com,1999:blog-3844331164714701431.post-83249318164440468882012-06-21T00:53:00.000+05:302012-06-21T00:53:22.227+05:30The even fibonacciProve that F[2n] cannot be of the form 4k+2, where F[i] is ith Fibonacci number. (F[0] = 0, F[1] = 1 etc...)pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com5tag:blogger.com,1999:blog-3844331164714701431.post-559257731343973482012-06-20T01:03:00.000+05:302012-07-04T02:45:33.350+05:30Value of selectionThere is a 2 dimensional matrix M ( mxn ) of non-negative integers. A "selection" is defined as set of elements, satisfying the following condition:<br />If m>n then there is exactly one element from each column. Else, there is exactly one element from each row.<br />And sum of all elements of a selection is called its "value".<br />Find the selection with maximum "value" in O(m*n).pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com0tag:blogger.com,1999:blog-3844331164714701431.post-52099311271615275132012-06-11T16:29:00.002+05:302012-06-11T16:29:16.328+05:30Second largest element in an arrayGiven an unsorted array of size n, find the second largest element of the array in "n + log(n)" steps.<br />( Its not O(n+log(n)), its "n + log(n)" ).<br /><br />Courtesy : Career cup.pathankhan salmanhttps://plus.google.com/114990135922909741333noreply@blogger.com5