Skip to content

Latest commit

 

History

History
435 lines (358 loc) · 22.5 KB

Puzzles.page

File metadata and controls

435 lines (358 loc) · 22.5 KB
Raw

Riddles

  • 100 people in line looking forward. white/black hats placed on head. don't know own hat. each person guesses own hat from rear to front---person dies if wrong. strategy to maximize expected lives? e.g. all black yields 50.

    • extension: instead of white and black hats, you have n colors of hats
    • extension: instead of 100 people, you have a countable infinite nuber of people (there is a "first person" who can see down the whole line but not a "last person". Assume perfect eyesight). In this case, the victory condition is "can you save all except finitely many prisoners"?

  • in a room with a line of off lights, first person toggles every light, second person toggles every other light, 3rd person toggles every 3 lights, etc. which lights are on? (harder) how many lights will light $n$ be toggled?

  • given two ropes that burn in 60m (non-uniformly), measure 15m

  • with 2 eggs, what's min # steps to find the floor in a 100-fl bldg at which dropping eggs breaks the eggs?

  • what's smallest # yes/no questions to ask to determine a birthday if you have to prepare all the questions up-front (can't ask dynamically)? what are those questions?

  • min # weighings to find fake (lighter/heavier) coin out of 12

  • hat puzzle: $n$ prisoners given black/white hat. can't see own hat but can see others'. no communication. at least one must correctly say own hat color, else all executed. given prep planning time before test begins/hats given.

  • num points on earth where going 1mi south, east, north goes back to origin

  • (optimal stopping) given a sequence of $n$ ppl to date, where ppl are totally-ordered in how good a match they are for you, how many to reject/skip to maximize prob of accepting the best person?

  • 25 racehorses, 5 tracks, fewest # races to find top 3

  • num ways to climb $n$ steps if you take 1-2 steps at a time?

  • A king demands a tax of 1,000 gold sovereigns from each of 10 regions of his nation. The tax collectors for each region bring him the requested bag of gold coins at year end. An informant tells the king that one tax collector is cheating and giving coins that are consistently 10% lighter than they should be, but he does not know which collector is cheating. The king knows that each coin should weigh exactly one ounce. How can the king identify the cheat by using a weighing device exactly once?

  • min # balance weighings to find heavier ball of 8? of 13? of $n$?

  • 3 black hats, 2 white hats, 3 men in a line facing forward (can't see behind), each wearing a hat. they guess at their own hats. man in back says "i don't know," middle says "i don't know," front says "i know" - how does he know?

  • how many ways are there to walk up s steps if you can take 1 or 2 at a time?

  • A princess lives in a row of 17 rooms. Each day, she moves to adjacent room. Prince has 30 days to find her and can check one room per day. Does he have enough time?

  • create five rects out of lengths 1-10, eg 1x3, 2x4, 5x7, 6x8, 9x10. how many diff sets possible? what are max & min total areas? http://wordplay.blogs.nytimes.com/2014/04/14/rectangle/

  • four cards on corners of square lazy susan turntable in dark room. you don't know which are up/down. you want to get all to be up or down. each turn, you can flip any card(s) - if all up/down, game ends, else rotate random # 90-deg turns and next turn. can you end the game (how)? http://mindyourdecisions.com/blog/2014/04/14/monday-puzzle-cards-on-a-square/#.U3giG61dXSo

  • http://www.tanyakhovanova.com/Puzzles/

  • http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml

  • 2 people face to face. black/white hat placed on heads. can't see own but can see other's. both must guess own hat simultaneously. monster eats if both guess wrong. strat? http://wordplay.blogs.nytimes.com/2014/01/20/hats-2/

  • A pile of 1,000 coins is split into two piles x and y. Multiply those together to get a number x*y.

    Subdivide each of the two piles further and get a number for each pile. (Say you divide x to get the number x1x2, and y to get the number y1y2)

    Repeat the process until there are 1,000 piles, each with 1 coin.

    Add all of the numbers together. What is the sum??

    Does the answer change depending on how you split the pile?

    Bonus question: You have a line segment of length 1. You divide it into two pieces x and y to get the number xy. Divide each smaller piece and repeat the process. If you add up all the numbers, what is the limit?

  • Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

  • if prob of seeing car on highway in 30m is .95, prob of seeing car in 10m?

  • Fitch Cheney's 5-card trick:

    The question concerns a "magic trick" involving playing cards, a standard 52-card deck. There are two magicians, and they are working together.

    The first magician finds a member of the audience and asks them to pick out 5 cards from the deck and hand them back to him. The magician takes a look at the 5 cards, chooses one of them, and hands it back to the audience member, asking him to look at it and hold on to it. This is the secret card.

    The first magician then takes the remaining four cards, arranges them in some order and hands them to the second magician, who upon receiving the four cards is able to magically tell everyone what the secret card is! ** Tada! **

  • You have a lighter and two ropes. Each rope burns up in 1 hour from end to end, but the ropes do not burn evenly. How can you measure 45 minutes by burning the ropes? 50 minutes?

  • A robber broke into the belfry of a church, and though he had nothing to assist him but his pocket-knife, he contrived to steal nearly the two lengths of the two bell ropes, which passed through holes in the lofty boarded ceiling. How did he effect his purpose? Of course, there was no ladder or aught else to assist him. It is easy to understand that he might steal one rope and slide down the other, but how he cut the two, or any considerable portion of them, without a bad fall, is perplexing. (Puzzle by Henry Dudeney.)

Game theory

  • dividing pizza: I'll slice, and we'll take turns picking in a circle (only adj pieces), you pick first; better to have me odd or even num slices?

  • cannibals:

    A traveler gets lost on a deserted island and finds himself surrounded by a group of n cannibals.

    Each cannibal wants to eat the traveler but, as each knows, there is a risk. A cannibal that attacks and eats the traveler would become tired and defenseless. After he eats, he would become an easy target for another cannibal (who would also become tired and defenseless after eating).

    The cannibals are all hungry, but they cannot trust each other to cooperate. The cannibals happen to be well versed in game theory, so they will think before making a move.

    Does the nearest cannibal, or any cannibal in the group, devour the lost traveler?

Number theory

  • prove: for all ints $A,B$, there exist ints $C,D$ such that $2(A^2+B^2)=C^2+D^2$
    • eg, $2(4^2+7^2)=3^2+11^2$

Algorithms

  • how do you incrementally extend a hashtable?

  • how to reverse the words in a string?

  • binary search for circularly sorted array

  • $n$ary search in 2D matrix where rows/cols are ordered

  • given an array of $n$ positive numbers $A$, return array of $n$ numbers where element $i$ is the product of all numbers in $A$ except for element $A_i$. now do it when you have no division. now do it when you have no multiplication.

  • given a set of strings xs and a string y, return subset of xs that are substrings of y

  • come up with a $O(n \log n)$ algo for computing kendall-tau

  • distance-maximizing problem: given an array $A$ of integers, find the maximum $j-i$ where $A_i<A_j$ (harder: in $O(n)$!)

  • find max-sum sub-array

  • find the majority element in a stream

  • longest palindromic substring: brute force, then in $O(n^2)$ time/space, then in $O(1)$ space, then in $O(n)$ time/space (hard)

  • how to reverse bits in an int? (hint: use xor to swap pair of bits)

  • Out of a thousand identical buckets of water, exactly one contains a poison that will kill a pig in exactly 30 minutes. What's the minimum number of pigs you need to determine which bucket is poisoned in 30m? an hour?

  • how to sample non-uniform discrete dist in const time? (may need handholding)

  • find # pairs of isomorphic words given set of words

  • how to find sliding window max over list? (harder: in $O(n)$!)

  • with a dict, segment a string without spaces into words (http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/)

  • (similar to above) given a phone number, a function from digits to characters, and a function from dict words to scores, what's the max-score word it spells? what's the max-score phrase it spells?

  • shuffle an array

  • given axis-aligned rects, find overlapping pairs

  • given unsorted array of ints where each int appears twice, except for one int that appears once. find this int. O(n) time & O(1) space!

  • given unsorted array of ints where each int appears thrice, except for one int that appears once. find this int. O(n) time & O(1) space!

  • how many ints in $[x,y]$ are palindrome & square of palindrome? (up to 10^100)

  • given array of length $n$ containing ints in $[1,n-1]$, find the duplicate in $O(n)$ time and $O(\log n)$ space

  • given $k$ sorted arrays, find smallest value range s.t. each array has 1+ element in that range ($O(k n \log n)$)

  • given array of 0/1, find longest subarray with same # of 0 & 1

  • given an array of integers, concatenate all numbers in some order so that the combined string is lexicological smallest. e.g., {3,32,321}, solution is 321323.

  • how many times does $x$ appear in sorted array?

  • given set of ints, find longest sequence of consecutive ints

  • how many out-of-order pairs in a totally orderable list?

  • given 2 ints a,b, return a/b in decimal, with repeating decimals in parens, e.g.:

    • 1/2 = 0.5
    • 4/3 = 1.(3)
    • 1/7 = 0.(142857)
    • 1/30 = 0.0(3)

    extension: generalize it to take in a and b in an arbitrary base N

Evil Gambling Monster (Gamblor)

Originally from http://www.facebook.com/jobs_puzzles/?puzzle_id=1&ref=nf

There are 9 casinos, laid out in the following configuration, with the lines between them representing overnight travel routes:

1 ---- 2 ---- 3
|      |      |
|      |      |
4 ---- 5 ---- 6
|      |      |
|      |      |
7 ---- 8 ---- 9

On an otherwise uneventful visit to one of these casinos, your dear mother has had the misfortune to be enslaved by an evil gambling monster. I call him Gamblor, and it is time to snatch her away from his neon claws.[1]

Unfortunately, Gamblor demands the payment of a great deal of money in return for releasing his hostage.

Luckily, you are a psychic computer scientist. With your powers, you can predict in advance over the next 30 days how much you would win (or lose) if you played at a particular casino on that day. This schedule of winnings is represented by the following nine 30-element arrays:

wins1 = [ 53,-84, 50,-73, 54, 60, 74, 22,-63,-78, 75, 72,
        -46, 99,-33, 24,  6,-66, 77,-61,-60,-46,-52, 84,
          91,-21,-52,-72,-39,-41]
wins2 = [ 77,-86,-25, 27,-59,-71,-13,-85, 50, 24,-63, 26,
          -4,-10, 25, 62,-85,-68, 96, 92,-29,-64,-54, 18,
        -79,-62, 97,-32,-35,-42]
wins3 = [ 27,-57,-28,-98, 69, 12,-70,-43, 27, 80, 80, 64,
          6,-23,-45,-68,-60,-31,-36,-63,-39, 34,-27,  7,
        -47, -7, 44,-50, 60,-90]
wins4 = [  7,-12,-48, 79,-11,-78, -8, 19,-21,-81, -1,-40,
          83,-95, 36,-62,-63, 76,  6,  0,-87, 67,-66,-15,
        -26,-14, 78,-81, 36, 38]
wins5 = [-71,-56,-73,-20,-77, 15,  2, 14,-66, 81, 33, 33,
        -59, 16, 37, 77, 53, 73, 53,-40,-26, 66,-73,  7,
        -48,  1, 93,-70, 19, 30]
wins6 = [ 68, 47, 73, 94,-72, 96, 10, 30, 11, 44, 11,-56,
        -23, 51, 60,-86, 29, 13, 87,-17, 73,-39,-51,-99,
          68,  1,  1, 62, 30,-79]
wins7 = [ -8, -1, 68,-34, -7, 96,-37,-96, 26, 73, 47,-62,
        -83,-76, 89, 77,-62, 18, -9,-75,-99,-36,-14,-50,
        -36,-45, 50, 64,-83,-19]
wins8 = [ 85,  9, 79, 53, 75,-28, 49,-62,-25,-24,-89,-77,
          13,-72,-54,  2,-95,-17,-80, -5,  8,-79, 59, 93,
        -30,-77,-51,-79, 87,-35]
wins9 = [  1, 72, 74,-20, 26, 49, 52,-25, 86,-72, 50, 97,
        -50,-36,-74, -4, 65,-70, 78, 85, 25,-14,-93,-16,
        -20,-24,  7, 28, -3, -5]

Travel routes between the casinos are represented by the following adjoinment matrix:

adj = [[1, 1, 0, 1, 0, 0, 0, 0, 0],
      [1, 1, 1, 0, 1, 0, 0, 0, 0],
      [0, 1, 1, 0, 0, 1, 0, 0, 0],
      [1, 0, 0, 1, 1, 0, 1, 0, 0],
      [0, 1, 0, 1, 1, 1, 0, 1, 0],
      [0, 0, 1, 0, 1, 1, 0, 0, 1],
      [0, 0, 0, 1, 0, 0, 1, 1, 0],
      [0, 0, 0, 0, 1, 0, 1, 1, 1],
      [0, 0, 0, 0, 0, 1, 0, 1, 1]]

You begin on the first day at the location of casino 1.

For example, if you were at casino #1 on day 1, you would win $53 if you decided to play. Later, if you were at casino #3 on day 4, you would lose $98 if you decided to play. Since you can only travel the distance of one route every night, you cannot reach all the casinos right away - e.g. you would not be able to play at casino #6 on the first day to win $68.

The casino owners don't like your special abilities, but they have agreed to let you play subject to the following conditions:

  • At the beginning of the 30 days, you may either begin playing at your current casino immediately or decide to wait until the next day.
  • Once you begin playing, you must play each consecutive day until you stop.
  • Once you stop playing, you may not play again.

Each night after playing or not playing, you may either stay at your current location or travel to an immediately adjoining casino. You may travel overnight between casinos regardless of whether or not you have played that day.

You cannot play a fraction of a day; if a particular day is one where you have chosen to play, you will earn the predicted win or loss for that day.

You wish to determine how many N >= 0 days to not play, how many subsequent M >= 0 consecutive days to play (and how many remaining K >= 0 days you also don't play), and the path to travel between casinos during this 30-day time period such that you maximize your total winnings.

Probability

  • toss $m$ balls into $n$ bins; how many bins will be non-empty?

  • $m$ bins; how many balls to toss so that $k$ of them are non-empty?

  • Say companies have to give a holiday to everyone whenever one employee has a birthday. Other than those holidays, employees work every day. If a company wants to maximize the expected total number of man-hours worked per year, how many employees should it hire?

  • birthday problem: computable

  • hat problem/matching problem

    • setup: 1000 ppl pile their hats, then each takes one.
    • how many ppl get their hat back on avg?
    • prob $k$ ppl get hat back?
    • harder versions: no two people get each other's hats either

  • poisson approximation can solve the above and others (prob of drunken walker ending at start location): http://heroofourtime.blogspot.com/2010/11/birthday-problem.html

  • 5 men form a circle; prob that they're youngest-to-oldest (either dir)?

  • prob of not rolling a 2 in 55 tosses of a 20-sided die is $.95^55$. prob of this for any of the 20 numbers?

  • russian roulette: load 2 adjacent chambers. spin barrel. click. before pulling again, want to spin?

  • newsvendor model: if goods are $3 to buy and $4 to sell, and you have uniform prob of selling any number $0 \le n \le 100$, how many should you buy?

  • holding second-price auction. a bidder costs $10 to find. bids uniform in $500-$1K. how many bidders to find?

  • newton-peppys: which is more likely, at least one 6 in 6 rolls, at least two 6s in 12 rolls, or at least three 6s in 18 rolls?

  • what is the avg # local maxima of a permutation of ${1, \dots, n}$, over all perms? maxima at ends also count. (putnam problem) http://ubpdqnmathematica.wordpress.com/2012/02/26/how-many-bumps/

  • One hundred people board a 100-seat airplane. The first one has lost his boarding pass, so he sits in a random seat. Each subsequent passenger sits in his own seat if it’s available or takes a random unoccupied seat if it’s not.

    What’s the probability that the 100th passenger finds his seat occupied?

    http://www.futilitycloset.com/2012/02/29/all-aboard-5/

  • If a particle starts at position $n$ and at each time $t=0,1,2,\dots$ it moves up/down with prob .5 then what's prob of reaching 0 before $t=1000$?

  • drawing 2 cards at a time from deck. if both red, you keep pair; if both black, i keep pair. if mixed, discard. you win $10 if you end w more pairs. what's a fair game entry price? http://mindyourdecisions.com/blog/2012/04/23/monday-puzzle-pairs-of-cards/

  • How does 3-coin swindle work? http://wordplay.blogs.nytimes.com/2014/10/13/mg100-1/

  • prob of A&B meeting in an elimination tournament tree of $2^n$ players?

  • roll die 1-100. either cash out current roll in $ or pay $1 to re-roll. optimal strat?

  • $n$ people, prob disease $p$. can test each person's blood but costly. instead, pool blood of every $k$ ppl. best $k$ to minimize expected # tests?

Geometry

Practical

General math

  • in evenland, only even numbers exist. primes are numbers that cannot be represented as a product of two smaller numbers. in our world, numbers have a unique prime factorization; in evenland, numbers can have multiple prime factorizations. what's the smallest such number?

  • find $x$ if $x^{x^{x^\dots}} = 2$

  • find all real/complex roots of $x^6 = 64$

  • hour/minute hands of clock meet at 12:00; when will they first meet again?

  • 3 points randomly drawn on circle; prob of them being on same semi-circle?

  • unit length broken off into 3 pieces; prob of forming triangle?

  • $\sqrt{2 + \sqrt{2 + \sqrt{2 + \dots}}}$

  • You have 5 unknown numbers. There are 10 options in selecting two out of these five. Sum each of those two together, thus you have 10 numbers. You're given these, find the original 5 numbers.

  • Given two vectors $x,y$ of $N$ elements where first $M$ are numbers and remaining are letters from an alphabet, want to find:

    distance(x,y) = l1_distance(x[1..M], y[1..M]) + hamming_distance(x[M+1..N], y[M+1..N])

    E.g., hamming_distance([a,b,c], [a,a,c]) = 1

    What $f$ will let us compute this using just L1 distance?

    distance(x,y) = l1_distance(f(x), f(y))

  • how many 0s are there in 100!?

  • (hard) what's the longest sequence of numbers where any 7 consecutive numbers have a positive sum and any 11 consecutive numbers have a negative sum?

  • airport conveyer belt: takes 172s to walk to other side WITH belt and 5x that to AGAINST. how long if standing still? if walking without belt?