CSE Blog - quant, math, computer science puzzles

Source:   The Math Factor  (contains spoilers) - also tweeted on What Would Martin Gardner Tweet Problem: The number of 1′s in this paragraph is ___; the number of 2′s is ___; the number of 3′s is ____; and the number of 4′s is ___. Bonus Research Follow-up Problem: The number of 1′s in this paragraph is ___; the number of 2′s is ___; …..(and so on) and the number of N’s is ___. For N=2 or 3, there are no solutions (Asking that all the numbers we fill in are between 1 and N); for N=4 there are two. For N=5 there is just one, for N=6 there are none and beyond that there is just one. Prove it. claimtoken-51f4577649b8d Solution: Highlight the part between the * symbols for the answer. * For N = 4 there are exactly two fillings: (2, 3, 2, 1) and (3, 1, 3, 1). Check (2,3,2,1): the paragraph's digits are the four fixed labels 1,2,3,4 plus the blanks 2,3,2,1 - total: two 1s (label + one blank), three 2s, two 3s, one 4. Checks out. Same for (3,1,3,1). Why only these: eve...

Source: http://people.csail.mit.edu/bdean/6.046/dp/ Problem:  Given two text strings A of length n and B of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B. Given two strings A and B, what is the path from A to B with minimum edit distance? Solution: Highlight the part between the * symbols for the answer. * This is the classic Levenshtein DP. Let D(i, j) = edit distance between the first i characters of A and the first j characters of B. Then: D(0, j) = j, D(i, 0) = i, and D(i, j) = min of: D(i-1, j-1) + (0 if A[i] = B[j] else 1) (match or substitute) D(i-1, j) + 1 (delete A[i]) D(i, j-1) + 1 (insert B[j]) Fill the (n+1) x (m+1) table row ...

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? Solution: Highlight the part between the * symbols for the answer. * Yes - you can always force termination. Proof by induction on the number of bits n. Base: n = 1 is trivial (flip a 1; if it is 0, the adversary must flip it or lose, and you flip it next scan). Step: assume you can force a win on any string of n - 1 bits. For n bits, ignore the leftmost bit entirely and play your winning (n-1)-bit strategy on the rightmost n-1 ...

List of 25 movies - where Mathematics was a core part of the Movie Shared as an IMDB List  http://www.imdb.com/list/zyWjUfnfwdY Taken from  http://www.math.harvard.edu/~knill/mathmovies/ Math in Movies (IMDB List) Good Will Hunting (1997) Twelve Monkeys (1995) A Beautiful Mind (2001) Equilibrium (2002) Moneyball (2011) Pi (1998) Die Hard: With a Vengeance (1995) Cube (1997) Rites of Love and Math (2010) 23 (1998) Colossus: The Forbin Project (1970) Breaking the Code (1996) Sneakers (1992) Pay It Forward (2000) Real Genius (1985) The Code Conspiracy (2002) 21 (2008) Fermat's Room (2007) The Bank (2001) Enigma (2001) The Number 23 (2007) Hackers (1995) Infinity (1996) The Time Machine (2002) Cube²: Hypercube (2002)