Posts

Showing posts with the label Number-Theory

Gold Links Puzzle

Source: Alok Goyal (Stellaris VP) puzzle blog Problem: This is another famous puzzle in the Martin Gardner collection, and variations of this puzzle exist in different “sizes”. This particular one has been picked up from The Colossal Book of Short Puzzles and Problems, Puzzle 9.18. Replicating the puzzle as is. Lenox R. Lohr, president of the Museum of Science and Industry in Chicago, was kind enough to pass along the following deceptively simple version of a type of combinatorial problem that turns up in many fields of applied mathematics. A traveler finds himself in a strange town without funds; he expects a large check to arrive in a few weeks. His most valuable posession is a gold watch chain of 23 links. To pay for a room he arranges with a landlady to give her as collateral one link a day for 23 days. Naturally, the traveler wants to damage his watch chain as little as possible. Instead of giving the landlady a separate link each day he can give her one link the first...

Mathematics of SET game

Source: Sent to me by Pritish Kamath ( http://www.mit.edu/~pritish/ ) Problem: Have you ever played "SET"? You have to play it. http://www.setgame.com/learn_play http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf Even if you have not played the game, the game can be stated in a more abstract way as follows: There are 12 points presented in  F 3 4  and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added. Problem 1: How many points in  F 3 4  are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in  F 3 4 , what is the probability that there exists a line among them? Disclaimer: We have not solved the problem yet. It can be very difficult or very easy. Update (22/12/14): It turns out to be a very very difficult problem. Paper: http://www.math.rutgers.edu/~maclag...

Prime Power Math Puzzle

Source: IBM Ponder This - June 2012 - Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: Two players starts with the number N and play in turns. In each turn the player chooses a prime power p^m > 1, which divides N and updates N to be N/(p^m). The player who sets N to be 1 - wins. What are all the winning moves from the initial state of N=1,506,009,006,001,500,000,000 ? We are looking for all the moves the first player can make which, assuming he plays correctly, can guarantee him winning the game. Update (24 June 2014): Solution:  Posted by Gowtham Kumar (PhD Student, Stanford, IITM Alumnus) and me in comments!

Divisibility Problem

Source: Posted by JDGM (James Miles) in comments on http://www.puzzletweeter.com ( A fanstastic blog by Gowtham Kumar , PhD Student, Stanford, IITM Alumnus) Problem: Prove that from the numbers 1 to 200 we cannot pick 101 of them such that none divide any other. Update (24 June 2014): Solution: Posted by Suman Datta, Stainless (Ameya Ranade, CSE IITB 2009 Alumnus, Microsoft, Google, Facebook Engineer) and Wei Chen in comments!

Math Game of Zero String

Source: Quantnet Problem: You have a string of bits. You scan from right to left. If you encounter a '1', you have the option to flip it to a 0 or keep it as is. If you encounter a '0', your adversary has the option to flip it to a 1 or keep it as is. Your goal is to zero all the bits once you reach the end of a scan (i.e. at the left most bit), whilst you adversary wishes to prolong the game indefinitely. We continually re-scan until we reach the aforementioned goal state. Can you prove that the game will eventually terminate?

Nine Digit Number - Math Puzzle

Source: Sent to me by Sudeep Kamath via  http://puzzletweeter.com/2013/06/21/884/ Problem:  Find a nine digit number abcdefghi that uses all the digits 1,2,3,...9 exactly once and satisfies: a is divisible by 1 ab (2 digit number with digits a and b) is divisible by 2 abc (3 digit number with digits a, b and c) is divisible by 3 ....... ....... abcdefghi is divisible by 9. Update (29/06/2013): Solution: Posted by JDGM, Anti, Meghana Kolan, Shwetabh Sameer and Unknown in comments! A more detailed solution provided by me in comments!

Equations Puzzle

Source: Interview Street Problem:   Find the number of positive integral solutions for the equations  (1/x) + (1/y) = 1/N!  (read 1 by x plus 1 by y is equal to 1 by n factorial)  Print a single integer which is the no of positive integral solutions modulo 1000007. Update (24 June 2014): Solution: Posted by JDGM (James D G Miles) in comments!

Integer Points

Source:  Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) - He found it at  http://puzzletweeter.com/ Problem: An integer point in a plane is a point whose coordinates are integers. Suppose we arbitrarily choose 5 integer points in a plane. Show that we can always find 2 among these 5 integer points such that the line segment joining the 2 points contains at least 1 more integer point.

Broken Clock Puzzle

Source:   http://www.ocf.berkeley.edu/~wwu/riddles/medium.shtml Problem: My fancy new digital alarm clock is broken! The time 'jumps' around. When I reset it, it reads 12:00:00. Then it runs as it should, but after 12:04:15 it resets back to 12:00:00. It counts up to 12:04:15 again and then it jumps to ... 12:08:32 ! Weird stuff. Do you know what's wrong with my alarm clock? Update (12/02/2013) Solution posted by Saumya Gupta, Abhimanyu Dhamija (CSE IITB 2011 Alumnus, Citibank Analyst) and Naga Vamsi Krishna in comments!

Determinant of Binary Matrix

Source: Introduced to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) Problem: An N by N matrix M has entries in {0,1} such that all the 1's in a row appear consecutively. Show that determinant of M is -1 or 0 or 1. Disclaimer: I could not solve it but I have an awesome solution sent by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012) Update (2/4/2013): Solution posted by Amol Sahasrabudhe (IITB 2004 Alumnus, Ex-Morgan Stanley Quant Associate, Deutsche Bank Quant Associate) and Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) in comments! Thanks a ton. I have posted the solution provided by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012). All three solutions are essentially the same.

Fermat Theorem Puzzle

Source: Andrej Cherkaev's List of Puzzles Problem: A computer scientist claims that he proved somehow that the Fermat theorem is correct for the following 3 numbers: x=2233445566, y=7788990011, z=9988776655 He announces these 3 numbers and calls for a press conference where he is going to present the value of N (to show that x^N + y^N = z^N and that the guy from Princeton was wrong). As the press conference starts, a 10-years old boy raises his hand and says that the respectable scientist has made a mistake and the Fermat theorem cannot hold for those 3 numbers. The scientist checks his computer calculations and finds a bug. How did the boy figure out that the scientist was wrong? Update (06/01/2012): Solution posted by a lot of people in comments!

Number of 1s in 2's complement representation

Source: Interview Street CodeSprint (slightly modified) Problem: One of the basics of Computer Science is knowing how numbers are represented in 2's complement. Imagine that you write down all numbers between A and B inclusive in 2's complement representation using 32 bits. How many 1's will you write down in all ? Input: Two integers A and B Output: The number of 1s Constraints: -2^31 <= A <= B <= 2^31 - 1 Find the asymptotically optimal algorithm.

USA Maths Olympiad Problem - 200th Puzzle

200th Puzzle of the CSE Blog Source: I got hold of the super awesome book I read 6 years back: "A Path to Combinatorics for Undergraduates: Counting Strategies" . A must have for any math/olympiad enthusiast (Flipkart link to Imported Edition and Indian Edition ) - Example 5.8 - USAMO 1990 Problem: Let n be a positive integer. Find the number of positive integers whose base n representation consists of distinct digits with the property that except for the leftmost digit, every digit differs by +1 or -1 from some digit further to the left. Update (26/12/2012): No correct solution provided. Solution posted by me in comments!

Pairwise Product Set Cardinality

Source: Nick's Mathematical Puzzles Problem: Let n be a positive integer, and let S n  = {n 2  + 1, n 2  + 2, ... , (n + 1) 2 }.  Find, in terms of n, the cardinality of the set of pairwise products of distinct elements of S n . For example, S 2  = {5, 6, 7, 8, 9}, 5 × 6 = 6 × 5 = 30, 5 × 7 = 7 × 5 = 35, 5 × 8 = 8 × 5 = 40, 5 × 9 = 9 × 5 = 45, 6 × 7 = 7 × 6 = 42, 6 × 8 = 8 × 6 = 48, 6 × 9 = 9 × 6 = 54, 7 × 8 = 8 × 7 = 56, 7 × 9 = 9 × 7 = 63, 8 × 9 = 9 × 8 = 72, and the required cardinality is 10. Update (Sept 12, 2012): Solution posted by Parakram Majumdar (CSE IITB Alumnus, Morgan Stanley Strats and Modeling Analyst) - Detailed explanation of the solution by unknown in comments!

Digit Permutation Puzzle

Source: Taken from Thomer's Puzzle Website ( http://thomer.com/riddles/ ) Problem: You have a number that consists of 6 different digits. This number multiplied by 2, 3, 4, 5, and 6 yields, in all cases, a new 6-digit number, which, in all cases, is a permutation of the original 6 different digits. What's the number?

Number of digits in 125^100

Source: Asked to me by Suman Kalyan Bera (M.Tech  Student IIT Delhi) on contact page Problem: How many digits does the number 125^100 have? Very interesting problem and equally interesting solution :) Update (25 December 2011): You are not allowed to use your high school notes on values of log_10(2) or log_10(5) Solution: Posted by me in comments!

Numbers on a circle - Minimum sum of consecutive differences

Source: Asked to me by Anuj Jain (MFE Grad Student at Baruch College in New York, EE IITB 2010 Alumnus) Problem: Place the numbers 1, 2, ... 9 around a circle in the positions x_1, x_2, ..., x_9 so that the sum of difference between consecutive terms defined by Sum over | x_ { i+1 } - x_ { i } | for i = 1, 2, ..., 9 is minimized (Note: x_10 is x_1 ). Also count the number of such arrangements where the "sum of difference between consecutive terms" is minimum. Update (December 13, 2011): Solution : Partial Solution posted by Chiraag Juvekar (IITB EE Fifth year undergraduate, To be McKinsey Business Analyst) in comments! Complete solution posted by Rudradev Basak (IITD CSE Senior Undergraduate) and  Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service)  in comments! Update (June 22, 2014): Very generic solution posted by Aashay Harlalka (IITB EE 2014, Two Roads Quantitative Analyst) in comments!

Divisibility of 111...1111

Source : Asked to Russian 7th Graders - Taken from Wild For Math Blog Problem : Is it true that among the numbers consisting of only "1"s (1; 11; 111; 1111; etc.) there is a number (maybe many) that is divisible by 572,003? Here 572,003 is taken arbitrarily. Is it true for all numbers? Update (November 02, 2011): Solution posted in comments by NG a.k.a Nikhil Garg (IITD CSE Senior Undergraduate), Rudradev Basak (IITD CSE Senior Undergraduate, IMO Bronze Medalist), Yashoteja Prabhu (RA at Microsoft Research, IITB CSE 2011 Alumnus), Siva, Garvit Juniwal (IITB CSE Senior Undergraduate)! Thanks