Paul Hsieh's real puzzle hints


Logical

- Can you produce the function x => (x xor 128)? Can you produce x => (x xor (1 shl n))?

- Can you create a permutation function which just swaps two values?

- Consider the functions: x => rol1(inc1(rol1(inc1(x)255))2)7 and x => inc1(rol1(inc1(rol1(x)))7)128. Can these functions be composed to create generators for all other permutations?

- For those interested in a paper and pencil proof: Consider the following statement: "Either two or three inputs are high". Can the truth value of such a logical statement be made from and's and or's of the inputs? What similar statements can be made and what are the implications of inverting them?

- For those who want to generate a computer solution: If we take the values 0xAA, 0xCC, 0xF0 and consider the nth bit of each, we see that all 8 combinations of 3 binary inputs are represented. That is to say, these numbers are independent representations of the three inputs. Now 0xAA & 0xCC = 0x88, which is a correct represenation of (a and b) if a is represented by 0xAA and b is represented by 0xCC. By starting with 0xAA, 0xCC, and 0xFF compute the space of values that can be obtained by ands, and ors. Then arbitrarily invert one of them and compute the new (possibly bigger) space that is obtained by ands and ors. Repeat the process again and see if the values 0x33, 0x55 and 0x0F are simultaneously in the space.

- Solution:

t3   = A and B and C
t23  = (A and B) or (B and C) or (A and C)
t123 = A or B or C

Then:

t01  = not t23
t1   = t123 and t01
t31  = t3 or t1
t02  = not t31
t0   = t01 and t02

We then compute:

A' = (t1 and (B or C)) or (t02 and B and C) or t0
B' = (t1 and (A or C)) or (t02 and A and C) or t0
C' = (t1 and (B or A)) or (t02 and B and A) or t0

- From your solution of the previous problem create a computer program that performs inv3(inout: a, b, c) using only two NOT operations. From here try to create an inv4(inout: a, b, c, d) using only AND, OR, copying and the inv3 function.

- Is it possible to work around the feedback problem?

- Think of the pariticipants, as slicers, and complainers. The object is to reduce the complainers.

- Arrange the people in a line. Have the first person cut off a "fair" slice of the pie, then proceed down the line giving each person the option of judging the slice to be a fair portion for someone else to have or not. As soon as one person says its unfair (because they think its too big), have them slice that slice of pie smaller so that it is "fair", and continue down the line with the same judging and iterative slicing until the end of the line has been reached. The last person that does slicing is stuck with that piece. Proceed by induction.

- How much information can you get in the first question? Can you determine with one question at least one person that is either the truth teller or liar?

- Is it sufficient to have only determined one person's identity after two questions?

- If you burn a string at both ends, it will completely burn in 15 minutes.

- 30 + 15 = 45. So burn one string completely, and when its done burn both ends of the other. Since you have only one match, and the only flame available at the end of the first half hour will be on the end of the first string we must therefore light the two ends of the second string with the final flame of the first string. So form a ring with the second string, attach it to the end of the first, and light the other end of the first. The whole thing will completely burn in 45 minutes.

- How does turning either B or 2 card help test the hypothesis?

- Is the original $30 price even a factor in the problem?

- The original $30 is first partially reimbursed ($3 dollars is given back) and the remaining balance of $27 is paid by the men, and received by the waiter ($2) and the restaurant ($25). I.e., $27 = $2 + $25. Adding $27 and $2 is incorrect since its at best counting the waiter's tip twice and ignoring the payment to the restaurant (and thus is not actually measure of anything sensible.)

- How many red cards total are there in the deck? Black? So how many red cards in total are there in any two split piles of the complete deck? How does that relate to the number of black cards among the split pile?

- For two piles of cards of size (a) and (52-a) what are the possible values for the difference in the number of red cards in one pile versus the number of black cards in the other?

- geostationary orbits are only stable around the equator.

- One rotation around the sun must be subtracted every year (imagine that the earth did not rotate at all -- then moving it in an orbit around the sun will still cause a single relative rotation.)

- Numerous classical time travel paradoxes come to mind.

  1. Why not wait until the time traveller decides to give you the payout *before* you contribute to the fund, so as to reduce the investment risk to exactly 0, rather than just $10?
  2. In what currency (in 500 years) would you expect to be paid in? What bank today would accept that currency? Of course you'd have to transfer it to something like gold. But you would have to *BUY* that gold in the future *BEFORE* travelling back in time. So the question is, taking inflation into account, how much more buying power will $100,000,000.00 have the versus $10 today? If you still think it will be ahead, go look at the greek currency versus what it was worth 500 years ago.
  3. What business (let alone bank) would survive for 500 years without having fallen into receivership (thus triggering a degraded payout of accounts, where "dead accounts" would be deprioritized and likely never paid out)? Recessions and depressions happen, and corporations and banks are victims of them.
  4. Opportunity payouts are far better than just compound interest. I.e., why not just come back with a list of winning lottery numbers, or las vegas wagering outcomes or just a chart for some volatile stock? Who cares about an initial $10 investment?
  5. The net result of this is supposedly to make "free money" on top of your $10 investment. Could not a similar technique be used to arbitrarily increase the supply of any particular thing (such as oil -- i.e., just bring back a future supply to increase our current stock pile, and repeat the process as desired)? Wouldn't our very notions of our economic system be completely turned upside down by such an ability -- I mean to the point of rendering the very concept of money useless?
Its a scam boys and girls. They just want your $10. They have no intention of following through with any escrow, trust account or whatever.

Mathematical

Set #6

- Consider the labeled balls, in which only the even numbers are thrown out.

- Consider the labeled balls, in which only the even numbers are thrown out until some fixed index k is reached, then the balls labeled k or greater are removed in their numerical order.

- After n steps (i.e., at 1+2-n seconds), let f(n) be the minimum label of the set of the balls in the bag. Let g(n) be the number of balls in the bag. g(n) = n, however does f(n) converge in any sensible sense?

- Prove that W(x) and W-1(x) are monotonically increasing and unbounded for x > 0.

- What is W-1(ln(x)-ln(ln(x)))?

- If the elevator started, say, half a story (or shorter distance) from the bottom would there by a serious risk of dying from the impact? What is the fundamental difference that falling from 20 stories makes?

- How does one measure the energy of the impact that is transfered to the elevator and ultimately you the occupant?

- What is the maximum speed that a person can travel at as a result of jumping? Compare this to an accumulated speed of free falling for 20 floors.

- Imagine the wrench were an extremely small (like the size of a pebble), but nevertheless fairly heavy because it was made of a substance like Plutonium.

- If an object sinks, then what is its density compared with water?

- In the selfish situation, obviously, they should just pick black. They have a better chance of being correct. So the real question is how to the try to increase the odds of as many following them as possible to survive.

- If a prisoner were being selfless for the benefit of others, he/she could use their guess as a binary communications mechanism instead of a genuine guessing mechanism.

- If each guess only told exactly enough information for the next person to know their hat color, then this strategy could only be used once (one person projects the information forward, and one person receives the information).

- Some set of prisoners must give information about all the prisoners.

- What is exactly the difference in knowledge about all the prisoners between the first and second prisoner to have to guess? What is the most minimum way of encoding this difference in knowledge, in a way that the *difference* between these two sets of knowledge is known to all the prisoners who hear guesses?

- Suppose the first prisoner asked simply gives information whether or not a count of the number of white hats he/she sees is even or odd? Note that this strategy is independent of the actual number of prisoners.

- This second strategy will save everyone deterministically except possibly the first person, who basically has a 50% chance of guessing wrong and dying; so a 99.5% success rate. The greedy strategy basically has a 66.6% success rate. The optimal strategy (from either the selfless or selfish point of view) is to be part of the second strategy, if possible, though it might be out of your control. So lets consider the third case where some prisoners might be selfless, and some selfish.

- As soon as a prisoner can established that some deterministic previous prisoner has given the parity of the number of white hats he/she sees ahead, they can assume they the other prisoners before him/her knows at least as much, and have switched to the selfless strategy thus guaranteeing their own survival.

- How would any given prisoner interpret the possibility that a previous prisoner guessed their color as white and survived? Does a sequence of black guessers and surivivors tell them anything? What if someone prior to them has guessed white but guessed wrong?

Set #5

- For fixed integers x and y, the submarine is at position x*t+y at time t.

- Create a well defined infinite list L of integers pairs (x, y) that are an exhaustive list of all integer pairs.

- At time t launch a missile at the position x(t)*t+y(t), where (x(t),y(t)) is the entry of the list at position t.

- The "proposal" is a way for the pirate to make a claim for his own gold, however, it is also a way to buy the votes of the other pirates. Presumably, give enough gold to the other pirates and the proposing pirate will get enough votes for his proposal to be adopted.

- Suppose there were only two pirates, what would the first pirate to speak propose?

- Suppose there were three pirates, what would the first pirate to speak propose (in lieu of the above)? I.e., if his proposal was defeated what would it mean for the last pirate to speak?

- Suppose there were 200 pirates? Write down the proposal as determined by the pattern established in the above two scenarios. Now is there anything special about the case of 201 pirates (how much does the proposing pirate suggest taking for himself)? Is 202 pirates different? Now suppose there are 203 pirates. Is it possible for the proposing pirate to get 102 votes? How much does it cost to get the vote of someone who will next speak if he knows for sure his proposal will be voted against?

- Now do the cases of 203, 204, and 205 pirates. Now be careful, 206 and 207 pirates does not follow the expected pattern -- a new pattern emerges. 208 pirates is different.

- What happens in the case of 216, 232, 264, and 328 pirates which does not happen in the other cases above 208?

- Suppose there was 1 coin and between 2 and 18 pirates. The following table shows the outcomes:

\Pirate #
123456789101112131415161718
201
3100
40100
5*****
61/301/31/300
7*******
8********
9*********
1001/3001/31/30000
11***********
12************
13*************
14**************
15***************
16****************
17*****************
181/701/71/7001/71/71/71/700000000

Each row shows essentially the best proposal for each pirate for the given number of pirates (shown in the leftmost column). The proposing pirate is the right-most entry. Green boxes show pirates that vote for the proposal. Light red boxes are votes against the proposal. Yellow boxes are possible votes, conditional on some probability. If the count box is white, then the proposal is accepted, and all pirates survive. If the count box is red, the proposal fails and the proposing pirate is killed. In the main box, a value of 0 means that in the proposal no gold is given to the pirate that corresponds to his rank (which corrsponds to the column index.) A value of 1 in the main box means that the 1 gold coin is proposed to go to that pirate. A fractional value means that the gold piece will be proposed to go to that pirate with that given probability. A * in the main box means that it does not matter what proposal is made.

Each row of the table is created inductively. That is to say, the prior rows are considered to show the best outcome, and the proposal and votes of each generated row takes the 3 rules into account as well as the prior rows to maximize each pirate's outcome. So for example, the first interesting case is row 6. Here pirate #6 (the proposing pirate) votes for his own proposal because of rule 1, pirate #5 also votes for the proposal because of rule 1, because he sees that he will die for sure if he is forced to propose (see row 5, where it shows that all proposals will fail) and then the proposal will give the gold coin to one of pirates 1, 3 or 4 corresponding to the pirate who will also vote for the proposal giving the required 3 votes for the proposal to pass. The reason why this proposal is optimal is because it is the only and cheapest way to obtain 3 votes -- he (the proposing pirate #6) buys one vote, and relies on his vote and the vote of pirate #5. Note that if his proposal had been to pirate #2, it would fail because pirate #2 would use criteria #3 to vote against the proposal knowing that the next proposal will also fail and that he will obtain the gold coin on the proposal by pirate #4 (thus increasing the number of killed pirates by two without risking his own life or decreasing his share.)

When there are between 7 and 9 pirate inclusive, its possible for the proposing pirate to try to bribe one of the pirates between #1 and #6 inclusive, however it will not change the outcome since at least 5 of those pirates will vote against the proposal. Pirates #7 through #9 inclusive basically are facing certain execution in these situations, and so are eager to vote for any proposal that will stop the executions (assuming some sort of futile desperation on the part of the pirate). But when there are 10 pirates, there are only 5 who are certain to vote against the proposal. The 10th pirate can count on his own vote, the three votes of pirate #7, #8 and #9 (who would otherwise face certain death) as well as one vote from one of the pirates #2, #5 or #6 who can be bribed with the coin. Note that if pirate #10 tries to bribe one of pirate #1, #3 or #4 they actually might still vote against the proposal because they might have a collusive relationship with pirate #6 which ensures them the gold coin anyways (so choosing #2, #5, or #6 is the only way to be sure to get their extra vote.)

- Under what conditions for a and b can we apply the arithmetic rule (√a)(√b) = √(ab)? - Recall Cantor's diagonalization.

- ~((a0 & 1) | (a1 & 2) | ... | (an-1 & 2n-1)), that is to say the nth bit of this expression is the logical not of the nth bit of an.

- Search for functions of the form h(x)g(x). What is required to keep the function below exponential, or above polynomial?

- In the above construction try O(g(x)) > constant and h(x) a polynomial.

- Try f(x) = xln(x)

Set #4

- Is 19 minutes a particularly difficult or unique answer to arrive at? How many ways are there of acheiving 19 minutes?

- There is no escaping the fact that Adam will require 10 minutes to get across and therefore it must be assumed that at least 10 minutes will be taken just geting him across. Is the same true, therefore, of Larry?

- Suppose the distribution was the normal (or guassian, as some universities call it) distribution with mean m, and standard deviation s, and was known to you before hand. How would you try to exploit this information? What about any other continuous, and known distribution?

- If the numbers are completely random from your point of view, then you too can chose undisclosed random numbers which may have certain statistical properties with respect to the gambler's chosen numbers.

- Before the gambler shows the first number, randomly choose a secret random continuous monotonic distribution of the real numbers (so that the probability of chosing any particular number is 0, but the probability that a chosen random number is in any particular range is always greater than 0). Then chose a secret random number with that secret random distribution. Then look at the number he exposes (chosing your secret random distribution and secret random number from that distribution before you look at the exposed number is kind of important from a bias point of view) and chose it if it is larger than the secretly chosen number, and switch to the other hand if it is smaller. Does such an algorithm improve your odds?

- The algorithm above does improve your probability of winning because the probability that the two numbers surround the secret number you chose is non-zero.

- Suppose the duck swims in concentric circles about the center. What is the maximum radius circle that it can swim about in while being able to dictate the angular difference (relative to the center) between the fox and itself?

- Is the diagonal perfectly straight?

- If we were to flatten and stretch a 1x1 (platecine) rectangle into parallelogram of base √29 and height 1/√29 (about 0.185695...) with the top shifted over by √73 (so the thin angle is about 1.245... degrees) and you placed it along the diagonal, of the triangle without the hole, would it fit? Would it be easily visible?

bizarre triangles

solution

Set #3

- The answer is not 1/32 or 1/31 (as a ratio)

- The typical incorrect answer of 1/32 is usually arrived at under an incorrect assumption of independence. Stay away from this style/line of reasoning altogether. Remember that uniformly random choices are essentially ratios of the size of a sets. Look at the size of sets, and generate the probabilities afterwards as a side effect.

- Consider an infinitely long stream of uniformly random 1's and 0's (our input) and break it at some point. What are the odds that up to that point the sequence was 0... ? What are the odds that up to that point the sequence was 10... ? 110... ? 1110... ? and so on? Which of these sequences causes the additions of a single extra bit in the output corresponding to the breakage point?

- Remember that if -1<a<1 then 1 + a + a2 + a3 + a4 + ... = 1/(1-a).

- Take a look at experimental results.

- The volume of the pyramid for any particular positioning of the lines can be expressed as the difference in volume of two pyramids who's volume is easy to calculate.

- Think of the volume as being proportional to certain lengths, vector dot products and so on.

- Forget the first pass, and consider the subsequent passes.

- For each locker, which passes will actually intersect with that locker?

- Which numbers have an odd number of factors, and which have an even number?

Hint 1: Let the starting number of coconuts be p0. After the ith primitive has taken his share and given one to the monkey let the number of remaining coconuts be pi. Each pi must be a positive integer. For i=0,...,4 then we have the following relation:
  4 * (pi - 1) / 5 = pi+1

Hint 2: 4 * (pi - 1) / 5 = pi+1 is equivalent to saying:
  4 * (pi + 4) = 5 * (pi+1 + 4)

Hint 3: Let qi = pi+4. Then qi+1/qi = 4/5. This solves to qi = k * (4/5)i, for some value k.

Hint 4: So pi = k * (4/5)i - 4. But each pi is an integer, so k * (4/5)i is an integer for i=0,...,5. This means k, 4*k/5, 16*k/25, 64*k/125, 256*k/625 and 1024*k/3125 are all integers.

Hint 5: If k is an integer and 4*k/5 is an integer, then k is divisible by 5. Furthermore, if 16*k/25 is an integer, then k is divisible by 25. Continuing this reasoning we can conclude than k may be any multiple of 3125 to satisfy the requirement that each pi is an integer.

Solution: Let k = 3125*t. Then pi = 3125 * t * (4/5)i - 4. If t <= 0 then pi < 0, but pi are all positive, so t must be positive. If t is positive, then p0 is minimized at 3121 by t = 1. Checking the rest of the sequence of pi we see: p1=2496, p2=1996, p3=1596, p4=1276, p5=1020 which are positive integers. So the answer is 3121.

- There is a little bit of psychology going on in this question.

- Take the point of view of finding an algorithm which maximizes the number of saved lives that will be saved and assume that you could have pre-emptively communicated this to the other 19 civilians.

- How many possible subsets of 10 distinct integers are there?

- What are the minimum an maximum possible sums for the 10 integers?

- If two of the subsets s and t are overlapping sets then (s-(s&t)) and (t-(s&t)) are disjoint sets with the property that s and t have the same sum if and only if (s-(s&t)) and (t-(s&t)) do.

Set #2

- Hint not yet available.

- What 2 dimensional geometric shape is alway formed by the coordinates of the four bugs taken in a consistent order?

- At what speed is each target bug travelling away from the bug that is chasing them?

- Consider an approximation of an initial part of the path taken as depicted by the stright line between the two blue dots in the diagram below.

Notice that the four bugs are still at the 4 corners of a (smaller) square after each takes the same analogous symmetric step.

- From the diagram above, assume that these partial paths are taken recursively in proportion to the size of the square that the 4 bugs outline. If the total path length is T, then

    T = sin(θ) + (cos(θ)-sin(θ))*T

Which solves to

    T = sin(θ)/(1-cos(θ)+sin(θ))

Now argue that as θ -> 0, the initial path step will more closely approximate the real initial displacement for that same length. Then compute lim θ -> 0 T.

- Add the cards to the bottom of the stack instead of the top.

- What is the taylor expantion of ln(1+x)? What is ln(0)?

- Hint not yet available.

- Hint not yet available.

- The "mixing" is a red herring. Pretend the substances don't mix, since mixing doesn't affect the volume. Then there are 4 "portions". What are the constraints on these four portions?

Set #1

- What are the features of a circle and how does this dictate your first move?

- Clearly any strategy is HIGHLY dependent on how I respond to your moves.

- Just how effective is Waldo?

- What are the chances they all agree and are wrong? What are the chances they all agree and they are right?

- There's no reason not to do this with brute force (especially if you use a spread sheet program, such as Open Office's Calc program):

 Spike  Molly  Waldo  Coin ProbabilityWinning strategy
HHHH.7*.8*.1*.5 =  2.8%  if all equal, go with consensus 
HHHT.3*.2*.9*.5 =  2.7% 
HHTH.7*.8*.9*.5 = 25.2%  if not all equal invert waldo
HHTT.3*.2*.1*.5 =  0.3% 
HTHH.7*.2*.1*.5 =  0.7% 
HTHT .3*.8*.9*.5 = 10.8%  if not all equal invert waldo
HTTH.7*.2*.9*.5 =  6.3%  if not all equal invert waldo
HTTT.3*.8*.1*.5 =  1.2% 
THHH.3*.8*.1*.5 =  1.2% 
THHT.7*.2*.9*.5 =  6.3%  if not all equal invert waldo
THTH.3*.8*.9*.5 = 10.8%  if not all equal invert waldo
THTT.7*.2*.1*.5 =  0.7% 
TTHH.3*.2*.1*.5 =  0.3% 
TTHT.7*.8*.9*.5 = 25.2%  if not all equal invert waldo
TTTH.3*.2*.9*.5 =  2.7% 
TTTT.7*.8*.1*.5 =  2.8%  if all equal, go with consensus 
Totals:100.0%90.2%

- Suppose there were 100 doors with 1 prize and Monty opened 98 of them to reveal nothing after you picked your door ...

- Draw a tree diagram of all the possible events that can occur. Realize that there are only three decisions that are made (two of the decisions are the same from a certain point of view) and assign probabilities to the possible choices.

- For a fixed p,q, how does one maximize the expression (1 + r*(2*p-q))/3? How does it depend on that values of p and q?

- If tic-tac-toe 8 in a row is a draw, what about 9 is a row?

- Do question 1 first.

- If the second player had a winning strategy, how should the first player try to play?

- Although a single question and answer cannot precisely determine the identity of a single person, the right question can eliminate a possible identity.

- If you dragged the table around on 3 legs (with the 4th up in the air) all over the place it would seem that nothing could be done if the 4th leg always stayed in the air.


Back to the puzzles

Valid HTML 4.0!