Adventures of BruteForce

Here's a logic puzzle that my boss gave me to think about. I thought about it on and off for a few days before arriving at a correct solution. I feel I should have figured it out sooner, but I ended up going down a dead-end path and wasting time stuck in that rut.

Anyway, here's the problem. I personally find it to be a really nice puzzle with a nice clean solution.

There is a bag with 52 balls numbered 1 through 52. First, you choose 5 of them randomly, and second, you pick one of them out (non-randomly... you get a choice) and put it in your pocket. Now, there are 4 balls remaining from your initial 5. Your goal is to order the 4 balls however you want in order to convey what the pocketed ball is to someone that understands your strategy/algorithm/rules.

Note that by ordering the 4 balls, I am not saying that you're allowed to do weird things with how the balls are placed. This problem involves no such trickery. The strategy that you come up with should work just as well if you wrote down the values in the order of your choice and some random person on the street were asked to read them out in order. The mere reading of these numbers in order should be enough information to determine the value of the hidden ball.

As you would guess, the question is simply this: What strategy/algorithm/rules can you use to accomplish this information transmission feat?

Enjoy.

Additional Clarification Notes (as some appear to be confused by the questions):

Understand that you only have 4 values to work with. The pocketed ball's value never comes into play as far as transmitting information. All the information must be conveyed with 4 ordered values. Nothing more. To further clarify, the final list of 4 values can be read out loud by anyone (including those without knowledge of the algorithm), and anyone that listens to the sequence of 4 values and also understands the strategy/algorithm/rules should be able to ascertain the hidden ball's value.

I'm a big nerd. Here's a problem for all you other nerds out there.

We have 25 balls of different weights. We would like to find out which are the 5 heaviest in order. In other words, we would like to know which ball is the heaviest, 2nd heaviest, 3rd heaviest, 4th heaviest, and 5th heaviest. The only tool we have available to conduct any measurements on these balls is what I'm calling a Relative Weighing device.

This device allows up to 5 balls to be loaded into it one at a time. Once all the balls are inserted, you press a button and the device prints out the ball order that corresponds to heaviest to lightest. As soon as the button is pushed, the device's memory is cleared and all you have is the printout.

For example: Say that you put in Balls 1 through 5 into the machine in that order. The Relative Weighing device might return 3, 4, 2, 1, 5 to indicate that Ball 3 is heavier than Ball 4 is heavier than Ball 2, and so on.

Now, for the question: What is the fewest weigh-ins using our special device to determine the 5 heaviest balls in order?

I found this problem to be both interesting and sort of cute. So, I'm sharing here. There are at least two solutions that I know of (ignoring isomorphisms). I didn't find it too difficult, but who knows what everyone else thinks of it.

You have 10 visually indistinguishable balls lined up in front of you. Let's mark then ball #1 through #10. Two adjacent balls have been deemed special. Your job is to determine which balls are the special ones.

You are given a single consultation with an oracle to help you out. The oracle accepts a specific type of query, which is of the form: How many of the balls in this list { ... } are special? You are allowed to submit two questions at once, and you will receive two answers at once.

For example, if the special balls are #1 and #2, a valid consultation with the oracle would be:

1) How many of the balls in {#1, #2, #3, #9} are special?
2) How many of the balls in {#1, #5, #6} are special?

The oracle's response in this case will be Question #1 = 2, Question #2 = 1.

Notice that you are not allowed to formulate Question #2 based on the response of Question #1. Both questions must be submitted simultaneously.

Enjoy!

Recently, I have become aware that some restaurant employees pad their tips by adjusting upward the value on the tip line and total (even at some nice places!). For the most part, the increases are for 1ドル or 2ドル. I don't go back and match every single credit card receipt to the credit card statement line items, so it would be nearly impossible for me to notice this.

Starting today, I am going to try something new. And, depending on whether or not it inconveniences me or not, I may make it a permanent practice.

I will tip in such a way that the sum of the digits in the final total will be 9 (mod 10) -- basically the last digit of the sum will be a 9.

Quick examples...

Example 1

Pre-Tip Total = 49ドル.74
Round Tipping (my current practice) = 8ドル.00
Total = 57ドル.74, which has a sum of 5+7+7+4 = 23. [3 (mod 10)]

So, I will want to subtract 4 cents.

New Tipping = 7ドル.96
New Total = 57ドル.70, which has my desired sum that is 9 (mod 10)

Example 2

Pre-Tip Total = 79ドル.16
Round Tipping (my current practice) = 12ドル.00
Total = 91ドル.16, which has a sum of 9+1+1+6 = 17. [7 (mod 10)]

So, I will want to add 2 cents.

New Tipping = 12ドル.02
New Total = 91ドル.18, which has my desired sum that is 9 (mod 10)

Of course, roughly 10% of the time I will not need to adjust my round tip. And, that's completely fine, as any future adjustment to the value will likely break my checksum constraint.

Once I begin this practice, it should be relatively easy to look at credit card line items for restaurant charges (excluding fast food). Also, since I normally tip on take-out orders, I won't need to differentiate between dine-in and take-out line items.

In any case, I guess I'll have to wait and see if this is going to be annoying to keep up or not.

So, I've written some simple simulation code for the 1-4-24 game. If you're not familiar with it, see this old post: 1-4-24 Dice Game.

Edit: I found a bug in my code, so I've updated the simulation results.
Edit #2: I found another bug in my code, and so I've updated the results again. And, added ran a couple other strategies just to see results.

I ran an initial simulation with a simple default strategy as follows:

1) Always keep 1 and 4 if you don't already have them.
2) Always keep 6 if you already have both a 1 and a 4.
3) If you didn't keep anything in the current roll (1/4/6 as per Rules #1 and #2) , then keep a single die (the highest valued one).


Here are results for a different strategy. Based on these results, it seems superior in most cases -- one case where it would not be superior is if you need only to score 15 to win (the following strategy hits 15+ 85% of the time while the previously described default strategy gets you there 91% of the time).

Evaluate the dice in the following sorted order: (1+4), 6, 5, 3, 2

1) Always keep 1 and 4 if you don't already have them.
2) Always keep 6 if you already have both a 1 and a 4.
3) If you have 2 or fewer dice left to consider, then keep a 5.
4) If you have only one die left to consider, then keep a 4. (Basically, expected value of a single roll is 3.5. You are 50% to do worse than a 4, and only 33% to do better. So, keeping the 4 is best.)
5) If you didn't keep anything in the current roll (as per above rules) , then keep a single die (the highest valued one).



Here's the 'go for broke' strategy, where you are going for 24 only. This means that you are going to keep all 6's (up to 4) and keep 1 and 4 as they present themselves. This strategy is forced if someone before you had gotten 24, and so you need specifically 24 to tie.

This is a continuation from: Combinatorial Madness - Follow Up.

So, a colleague of mine was able to solve the original potions problem such that the solution was the double factorial and not the summation. Thus, he was able to kill two birds with one stone. His way of looking at the problem shows both that the solution of the problem is, in fact, the double factorial and that by doing so, produces a proof by combinatorial argument of the double factorial identity.

For those unfamiliar, a proof by combinatorial argument is basically where you show two different ways to count the same thing, each having its own expression. Thus, both expressions must be equal, since they both count the same thing.

I take no credit for the following... it was solely the work of my colleague. If I mangle his argument, I apologize. I'm sure that I could be clearer about some parts, but I do think that the reasoning is solid. Anyway, this is basically how it goes.

Say that we want to know the solution to the N potions problem. Suppose that the solution of the k potions problem is A(k). With (N-1) potions, the total number of final potion products is A(N-1). Now, in producing a single final product with (N-1) initial potions, we would have gone through (N-2) iterations where some potion was combined with another potion in each iteration.

So, we can view these (N-2) combination actions as C_1, C_2, C_3, ..., C_(N-2). Any one of these combinations can be expressed as X+Y, X and Y being available potions at that junction. In order to tackle the N potion problem, we would like to add a new potion (the Nth potion -- call it Z) to the total mix. The question now is how can we add it such that we don't end up with any overcounting, etc?

For any combination action, we can inject the newly introduced Nth potion (Z) into that particular iteration -- however, notice that there are two ways in which this injection can happen. We can replace the combination that we're focused on with one where we've injected Z as ((X + Z)+Y) or as (X + (Y+Z)). Since there are (N-2) combination actions where we can perform this injection, we have 2(N-2) possible injection points.

We're missing one more injection point. That is the case where we simply combine the newly introduced Nth potion at the very end after C_(N-2) has produced some final product. There is exactly one injection point at the very end of our chain of C_k's. That adds one, so that gives us (2(N-2) + 1) injection points, and it's clear that adding Z to each of these injection points creates a completely new final product given this particular chain of combination actions (C_k's).

Now, we also know that there are A(N-1) different chains of combination actions that produce unique final products. Thus, we have (2(N-2)+1) * A(N-1) total final products for the N potions case. This simplifies to (2N-3) * A(N-1), which is clearly equivalent to (2N-3)!!, especially given that we know A(2) = 1 (the trivial 2-potion problem) .

So, this is a direct explanation of why the N-potion problem solution is (2N-3)!!, and it gives us the combinatorial proof that (2N-3)!! is equal to our other expression (from the previous post):

I know the above wasn't explained previously. That was me being lazy. Anyway, the explanation of why the above summation counts the final products in the N-potion problem is as follows (this one I actually helped come up with).

We are essentially enumerating all possible 2-partitions of the N potions being combined. A(i) represents the total final product count of the first of two partitions where the Nth potion is not a member. The A(N-i) represents the total final product count of the second of the two partitions and it is where the Nth potion is a member. The product of the two final product counts (i.e. A(i) * A(N-i) will result in the total number of final products when all N potions (both partitions) are considered). We are allowed to do this since our construction ensures no overcounting.

To further clarify, our loop going from i=1 to (N-1) gives us all the possible cardinalities of our partitions. We must multiply by ((N-1) Choose i) in order to produce all the combinations possible that make up the partitions with those cardinalities. Again, since we cannot overcount due to our construction, we can now sum the final product counts for all the possible partitions, giving us A(N).

Hope that was clear enough. And, in a way it was nice that we did not initially come up with the solution that leads directly to the double factorial. Because of this, we now have a pretty nifty combinatorial identity relating the recursive summation described above to the double factorial.

So, here's a follow-up to my previous post: Combinatorial Madness.
A follow-up to this follow-up post can be found here: Combinatorial Madness - Final Post.

After a fair bit more work at this and thinking about it (with a good deal of help from a few colleagues), here's where we have arrived. We basically have a good explanation of how we can formulate a recursive solution to the problem. And, it now comes to the point where we have to verify the following conjecture. We believe it holds true, but haven't yet proven it nor tried to prove it.

Assuming it's true, it is a pretty cool double factorial identity.

Here it is.

Note that A(k) is the solution for the potion problem where N=k.

So, any takers? We haven't tried to prove the above, but basically, if you can prove that then that basically proves that the solution to the original potions problem follows the double factorial.

A Follow-Up Post can be found here: Combinatorial Madness Follow-Up.

I've gone mad. Here I am on a Friday night, absolutely consumed by a combinatorial problem that I came up with to challenge myself a while back. Only tonight have I begun thinking about it more seriously. And, either it's quite difficult or I'm just not getting it. If anyone wants to give it a go, please do, then teach me how you were able solve it if you figure it out. Because, I think I'm kind of stuck.

This is long, but if you like numbers, you may enjoy this.

Here's the problem.

There are N potions. Combining any two potions will form a completely new potion. Thus, (A+B)+C does not equal A+(B+C), as A+B forms something completely new, call it E, and B+C forms something completely new, call it F. So the former is E+C which is completely different than A+F.

In a single iteration, two potions are combined. After N-1 iterations, there is a single final potion. The question is, how many different final products can be created starting with the N potions?

This is much more difficult than the trivial question, which is how many possible paths are there from N potions down to a final product. The total number of possible paths is clearly (N choose 2)*(N-1 choose 2)*(N-2 choose 2)*...*(2 choose 2). The total possible paths will overcount the total number of possible final products, as some paths will lead to the exact same potion.

Here's what my friend Duke and I have come up with...

N=2, clearly it's 1 possible final product.
N=3, clearly there are 3 possible final products.

For N=4, it starts getting a bit more interesting. Here's a way I came up with that helps us count the number of final products possible. If you think about it some, you will realize that with N=4, there are only 2 possible forms in which a final product can be created.

Here they are:

Form 1 = ((A+B)+C)+D
Form 2 = (A+B)+(C+D)

It should be clear that (A+(B+C))+D is an isomorphism, and doesn't give us a new final product.

Now, there are 4! ways in which we can arrange A, B, C, and D. But, we also notice that the order of A and B does not matter. Thus, we overcount by a factor of two. So, there are actually 4!/2 = 12 final products of Form 1.

For Form 2, we notice that we overcount by a factor of 2 three times (once for A/B, once for C/D, and once for AB/CD). So, we have 4!/(2^3) = 3 final products of Form 2.

So, for N=4, we have a total of 12+3 = 15 possible final products.

Following the same counting strategy for N=5, here are the possible forms.

Form 1: (((A+B)+C)+D)+E
Form 2: ((A+B)+C)+(D+E)
Form 3: ((A+B)+(C+D))+E

For Form 1, again we have overcounting by a factor of 2, so we get 5!/2 = 60 for N=5.
For Form 2, we overcount by a factor of 2 twice (2^2). So, this gives us 5!/4 = 30. Note that the order of (A+B) and (D+E) does matter, which is why we only overcount for (A,B) and (D,E) and not for (AB,DE).
For Form 3, we notice that (A+B) and (C+D) order does not matter, so we have an additional factor of 2 overcounting compared with Form 2. This gives us 5!/8 = 15.

So, for N=5, there are a total of 105 possible final products.

Since, I'm a real glutton for punishment, here's my attempt at N=6. I came up with 6 possible forms, hopefully I'm not missing any.

Here are the six forms I came up with for N=6:

(((A+B)+(C+D))+(E+F)) – I think this overcounts by factor of 2^3 (A/B, C/D, AB/CD) [Note: This is incorrect -- see the Edit at bottom.]
(((((A+B)+C)+D)+E)+F) – overcounts by factor of 2 (A/B)
((((A+B)+C)+(D+E))+F) – overcounts by factor of 2^2 (A/B, D/E)
((((A+B)+C)+D)+(E+F)) – overcounts by factor of 2^2 (A/B, E/F)
((((A+B)+(C+D))+E)+F) – overcounts by factor of 2^3 (A/B, C/D, AB/CD)
(((A+B)+C)+((D+E)+F)) – overcounts by factor of 2^3 (A/B, D/E, ABC/DEF)

This gives us 6!/2 = 360, 6!/4 = 180 (twice), 6!/8 = 90 (three times), which is 990 total possible final products.

I was really hoping that I would have come up with 945 total possible final products, but I just don't see where I've gone wrong above. Maybe I did, so if you spot a mistake, please let me know.

If it had been 945, then we have a double factorial pattern for odd values... 1*3*5*7*...*(2n-1). 1, 3, 15, 105, 945, 10395, etc.

But, since I can't convince myself that it's 945, I am officially stuck.

Anyone?


Edit:

(((A+B)+(C+D))+(E+F)) – I think this overcounts by factor of 2^3 (A/B, C/D, AB/CD) -- I neglected the E/F. This makes the overcounting factor 2^4, and that brings us to 945 possible final products for N=6. So, the solution is pretty much double factorial, but I do not have an actual proof. Will think about it, but maybe leave it to others, hehe.

Okay, so I was chatting with a friend over lunch recently about generating permutations that could be used, say, as test inputs. If we have a known number of sets of elements, then simple nested loops would work just fine. However, if we don't know ahead of time how many sets we'd like to produce permutations for, then it becomes a bit more challenging to produce permutations. You could write some code to do this recursively, but who really wants to do that.

Coming to the rescue is the Unix Shell (works fine with Cygwin Bash Shell also). Check this out.

echo {a,b,c}{11,22,33}{zyx,wvut,srq}
a11zyx a11wvut a11srq a22zyx a22wvut a22srq a33zyx a33wvut a33srq b11zyx b11wvut b11srq b22zyx b22wvut b22srq b33zyx b33wvut b33srq c11zyx c11wvut c11srq c22zyx c22wvut c22srq c33zyx c33wvut c33srq
Altering the output format to suit your needs is simple as well.

echo \({a,b,c},{1,2,3}\) | sed 's/ /\n/g'

(a,1)
(a,2)
(a,3)
(b,1)
(b,2)
(b,3)
(c,1)
(c,2)
(c,3)
How cool is that? I wish I knew about this handy trick before today.

I saw this math joke on someone's Facebook, and I thought it was pretty good. Here it is. Enjoy!

A bunch of functions are hanging out at a bar. There are trigonometric functions, logarithmic functions, polynomials, all different kinds of functions just hanging out and drinking. Suddenly the door flies open and a differential walks in. The functions are all terrified. Some dive behind the bar, some jump out of the windows, and others hide under their tables. Everybody is generally trying to get the hell away from this differential.

Floating point computations are imperfect in the computing world. Often times we overlook this fact, so it's good to refresh our memories every now and then.

A simple summation loop such as this one can produce results with large errors.

int i;
float fSumFloat = 0.0f;
double fSumDouble = 0.0;
const float fIncrementFloat = 0.0001f;
const double fIncrementDouble = 0.0001;
const int nIterations = 25000000;

for( i = 0; i < nIterations; i++ )
{
fSumFloat += fIncrementFloat;
fSumDouble += fIncrementDouble;
}

You would expect that summing 25 million 0.0001's would result in 2500, but depending on your machine the results will vary. Here are results of running the above on my PC (with all optimizations turned off). You'll see that there is some error even when using double precision floating point.

Sum (float) = 2048.0000000000
Sum (double) = 2500.0000004718
Expected Sum = 2500.0000000000

Now that I have your attention, there are ways to combat the roundoff errors that ultimately kill us. One popular method is the Kahan Summation method. Another method is known as pairwise summation, where you continually sum pairs of terms until all you have left is the final sum. For example, start with 1 + 2 + 3 + 4. The first pass yields you (1+2) = 3 and (3+4) = 7. The second pass gives you your desired sum of (3+7) = 10.

Both of these summation methods are slower than naive summation, but they are available if needed.

One thing that I found a bit interesting is that the results of these two methods were different on my PC as compared to a Linux box. I'm pretty sure that it has nothing to do with the OS, instead it's probably due to CPU and compiler differences.

On my computer at home:
Sum (float) = 2048.0000000000
Sum (double) = 2500.0000004718
Actual Kahan Sum (float) = 2048.0000000000
Pairwise Sum (float) = 2499.9998779297
Expected Sum = 2500.0000000000

On a Linux box:
Actual Sum (float) = 2048.0000000000
Actual Sum (double) = 2500.0000004718
Actual Kahan Sum (float) = 2500.0000000000
Pairwise Sum (float) = 2500.0000000000

I also noticed that when I had compiler optimizations turned on, the results coming from my PC were definitely better.

Actual Sum (float) = 2499.9999368447 [Compiler Optimizations Turned On]

Anyway, the bottom line is if you're going to be dealing with floating point calculations (and, summations in particular), be careful and run lots of experiments. Even when the code you've written is highly portable, you will want to make sure that results will be as you expect on your target environments.

For you mathy types, you might find this interesting: Number Spiral. I've never seen the site before, but I guess it's been there for years. Anyway, I thought it was cool on a first quick read. I'll probably go back and check it out some more when I have time.

Last week, I worked on one of the problems from this year's Mexican Math Olympiad (a math competition for really bright high school students in Mexico). In the actual competition, you get 9 hours to complete six problems (broken up over two 4-1/2 hour days). The problem I worked on was probably one of the easier ones, but I really don't know.

In any case, it took me a number of hours working on it in pieces before I came up with a solution. My solution was actually quite inelegant, but it was verified to be correct. So, I'm pleased with that. I haven't really tried any of the other problems, but I'm guessing that I couldn't solve most of them anyway (they're quite tough).

So, for those of you that enjoy a mathematical challenge from time to time, here's the problem.

There are N knights seated at a round table. Call the knights K_1, K_2, K_3, ..., K_N. The king decides to play a game to reward one of his knights. Beginning with K_1 and going clockwise, the knights will say the numbers 1, 2, 3, 1, 2, 3, 1, 2, 3, and so on. Note that each knight says only one number, before moving on to the next knight who will say the next number.

If a knight says 2 or 3 on his turn, then he immediately gets up and leaves the table. This little game continues until there is only one knight left at the table, and that knight is declared the winner.

For example, if N=7, then knights will say 1, 2, 3, 1, 2, 3, 1 in the first round. This leaves behind only K_1, K_4, K_7 for the second round. At this point, K_1 will say 2 (since, that's where we left off after Round 1), K_4 will say 3, and the winner will be K_7, as all the other knights are gone.

Now, here's the actual question: Find all the values of N such that the winner will be K_2008.

For anyone interested in image processing, this post on the Wolfram blog might be interesting. I think it's pretty neat, and it surely could simplify rapid testing of custom filters and image processing functions. It's often a pain to spend a lot of time coding up what you thought might be interesting only to learn that it wasn't so useful. And, I agree with what they say about Photoshop scripts... it's just not as nice as interfacing with a real API.

Of course, everything shown in that post can be done with your own image processing libraries and your own front-end, but if it's easy to do with what they've got, why not use it. I'd like to play with the new Mathematica some time, but unfortunately, that time isn't available now.

So, I was asked recently if I could help solve a simple exponential equation. And, while I was able to get an answer, I was only able to do so by inspection. I'm not sure how to go about solving a more general equation without using numerical methods.

Anyway, here's the equation:

SQRT( (3 + SQRT(8))^x ) + SQRT( (3 - SQRT(8))^x ) = 6

When I took a look at this, I was able to solve it by inspection readily...

The equation can be rewritten as:

(3 + SQRT(8))^(x/2) + (3 - SQRT(8))^(x/2) = 6

Clearly, if we had (3 + SQRT(8)) + (3 - SQRT(8)), we would get 6. So, we just want the exponents to be equal to 1, and thus, x = 2.

That's all fine and dandy, but that doesn't really sit well with me.

What if we had the following instead:

SQRT( (3 + SQRT(8))^x ) + SQRT( (3 - SQRT(8))^x ) = C

Now what? How would we be able to solve this in terms of C? Now, is there some sort of identity or trick that we can take advantage of to help us solve this... maybe something related to the conjugate?

I thought about this more, but I got nowhere. In terms of a quick and dirty approximation, we could simply drop the 2nd term knowing that as C tends to infinity, the (3 - SQRT(8))^(x/2) would approach zero.

So, for large C we could get an accurate approximation by simply solving the simpler equation:

(3 - SQRT(8))^(x/2) = C

And, x = (2 ln C) / (ln (3 + SQRT(8)). The value of C doesn't even have to get all that big for that approximation to be accurate. At C = 6, we have 1.65% error. At C = 34, we are down to a tiny 0.0246% error. And, by the time C reaches 198, we have a near negligible 0.000482% error.

Okay, but it's still not that useful. And, for small values of C, we are certainly going to be way off the mark.

Continuing with all of this... what do you do with another simple exponential equation like:

2^x + 3^x = C

I could get nowhere in trying to break this down. Is the only way to get a value for x is by solving for it numerically using known methods?

I've either forgotten a lot of simple math or there's just no clean way to solve exponential equations that contain different bases. Anyway, I'm done thinking about this for now. So, does anyone want to help me out with this?

So, my buddy Dan brought something to my attention that was of numerically quirky interest. It turns out that for some people this year, February is a 3-paycheck month. This would happen if you're paid every other Friday, and your company's rotation is such that you were paid on the first Friday of the year. For those who were paid on the 2nd Friday of the year, you won't get to see your 3-paycheck February until 2036, a good 28 years from now.

This is an event that happens once every 56 years. Not quite a Halley's comet, but it is rarer than seeing a Blue Moon twice in a single year (approximately once every 19 years according to this site).

A friend of mine recently had an interview for a software position, and was given the following problem...

There is a bar with 25 equally spaced stools. The patrons are anti-social and will always choose the stool that maximizes the minimum distance to other patrons. And, no patron will choose to sit next to another. If there isn't any spot that is insulated from others, then no more patrons can be seated. As the owner, you get to seat the first patron, but after that initial placement, the new patrons will seat themselves according to the aforementioned rules. Where do you seat the first person to maximize the number of customers?

So, I thought about this a little bit, and decided that the more general related problem was maybe a bit more interesting. Here's a slightly different question that is a bit more general. Given a bar with N stools, is it possible to seat (N + 1)/2 patrons? I came up with a solution, but it's not really all that elegant, but I do believe it works.

I'm going to skip a ton of the details, but what I came up with is the following. Let's start with what I am going to call a safe interior median partition (SIMP). These are interior stool groupings where splitting down the middle creates two SIMPs. Safe, meaning odd numbered. This is because as soon as we see even numbers, we know we can't fill it up to full capacity.

Not all interior median partitions are safe. Say we had the following: O O O O O O O. We care about the interior, so let's put patrons on the edges. Now, we have: X O O O O O X. Now, we have an IMP of size 5 (there are 5 stools on the interior). This is not safe since it leads to even-numbered IMPs. If we put a patron in the center, we'd have X O O X O O X, and that's clearly not what we want. We can't achieve full capacity using a 'sit in the middle' strategy. So, we know that IMP-5 is not a SIMP.

Now, if we had O O O O O O O O O. We block the edges, giving us: X O O O O O O O X, and we see that this gives us an IMP of size 7. But, look at what happens when we put a person in the middle. We then have X O O O X O O O X. And, we now have two new IMPs, each of size 3. Notice that the IMP of size 3 allows us futher partitioning with a central-seating. Giving us X O X O X O X O X. So, we know that IMP-3 is a SIMP, and IMP-7 is a SIMP, as it produces two IMP-3's.

We have a SIMP, if we have an IMP-X where X is of the form (2^N - 1). So, we can generate our list of SIMPs: 1, 3, 7, 15, 31, 63, etc.

Now, how does this help us? Basically, here's the deal. If we have N barstools, then I contend that we can fill it to capacity, which means (N + 1)/2 patrons seated according to the rules, if and only if we are able to find two SIMPs that sum to (N-3). Once we find our two SIMPs, then simply take one of them and add 2 to find the initial seating. Since we are choosing a first seat to give us two SIMPs, we are guaranteed to fill to capacity, because each median seating produces new SIMPs.

Here are a few examples with illustrative seatings:

N = 25. (N-3) = 22. Our two SIMPs are 7 and 15, which sum to 22. So, we choose initial seat 9.

N = 19. (N-3) = 16. Our two SIMPs are 1 and 15. We choose initial seat 3.

N = 13. (N-3) = 10. Our two SIMPs are 3 and 7. We choose initial seat 5.

N = 15. (N-3) = 12. There aren't two SIMPs that sum to 12. So, there does not exist an initial seating that gives us full capacity. You can see this is the case below, as I've exhausted the possibilities (ignoring symmetric cases).

Tonight, QB went out to her co-worker's going-away bash. I was just too tired to go out with her after a long, long day at work. So, here I am being bored and more or less unproductive.

To keep me busy, I have decided to share something I thought was pretty neat when I learned about it. I know that some of you out there have seen it before, but I still think it's pretty cool. Cool, until you see why it works, anyway.

So, start with any two whole numbers. Now, for the first number keep halving it until you end up with a value of 1. Note that you will always round down. For the second number, double it as often as the first number was halved.

As an example, say our numbers are 49 and 116.


The next step now is to cross out the values in the right column if the value in the left column is even. Continuing with our example, here's what we get.


Now, sum the values that remain in the right column. We have 116 +たす 1856 +たす 3712 =わ 5684, which is equivalent to the product of our two initial numbers (49 * 116 = 5684).

The reason the math works out this way is related to the binary number system (Decimal 49 = Binary 110001 = 2^5 + 2^4 + 2^0). Should be pretty obvious from here. Anyway, when I first saw this 'trick' I thought it was really neat. But, maybe it's because I'm easily amused. Ha ha.

Well, I'm about to head to a holiday party. But, before I do that I just wanted to share a quick story with all of you.

So, our company promoted a holiday gift exchange recently, and a total of 19 people participated. Anyway, each person brought a gift and then each person was given one of the gifts randomly. There was nothing in place to ensure that people wouldn't be given their own gifts, and what happened was 4 of the 19 participants got their own gifts back. Pretty strange, and so I got a bit curious about the probability of such an occurrence.

I had to go back to some old math books that I haven't touched in a while and read up a bit on the inclusion-exclusion principle, but after some time, I was able to get the answer I sought. Just to double-check, I programmed up a quick Monte Carlo simulation, which pretty much corroborated the answer. After more digging, I learned that there's something interesting about this problem, which turns out to be a classic one. It seems that this problem is closely tied to the natural number, e, which I thought was really neat.

Anyway, the chance that exactly 4 of 19 people receive their own gifts is 1.53%. The chance that 4 or more people receive their own gifts is 1.90%.

Not long ago, a colleague of mine asked me a bit about some financial stuff. I'm not really qualified to give out any advice, but I could always tell him what I thought about saving and investing for the long-term and how one should probably go about it. Anyway, in our discussion, we hit upon the subject of compounding, and at one point it was clear that while he understood how powerful it was, he clearly didn't give it enough credit. So, I bring to your attention the non-intuitive nature of compounding, especially at high rates of return.

Let me describe 3 scenarios, and without too much dwelling on the matter, tell me which of them you think is best for you. To simplify things a bit for this exercise, assume that you will pay all of the debt at the very end of the 25-year period, and not periodically. Also, for simplicity's sake, assume no external factors like tax, fees, etc.

Scenario A: You are given 10,000ドル by an anonymous benefactor. You are allowed to put the money into a special risk-free investment that returns 6% a year for 25 years, compounded annually.

Scenario B: A rich guy lends you 10,000ドル at the rate of 7.5%, compounding annually. After 25 years, you will have to pay him back the entire amount you owe him (10,000ドル + all the compounded interest at the 7.5% rate). With that borrowed money (10,000ドル), you can invest it in a risk-free vehicle that returns 10%, again compounded annually.

Scenario C: Same as Scenario B, except that instead of 10,000ドル at the rate of 7.5%, you get 5,000ドル at the usurious rate of 16%. But, in this situation, you are allowed to invest risk-free at 17.5%. You still pay your debt at the very end of the 25 year period, and everything compounds annually.

So, of these 3 scenarios, which one is the best? Which one of these will net you the most at the end? This means you pay off all the debt in Scenario B and C (you have no debt to repay in Scenario A).

My colleague is not unintelligent; he's a very solid engineer. But, when he was given these three choices he chose poorly. It wasn't so much that he didn't make the best choice, but that he was surprised by the result, which convinced me that the math of compounding is clearly not intuitive. I suspect that the vast majority of people will also choose poorly, and it says a lot about how underappreciated the power of compounding is, especially when you are talking about relatively high rates of return.

Well, I guess this is where I give you the end results for each of the three scenarios presented above.

Scenario A: You were given 10,000ドル and owe nothing. Free money, yay! So, right from the get-go, you're better off than the other two, since you've got 10,000ドル net, and the others have 0ドル. After 25 years, your money grew to 42,918ドル at the 6% rate. Not bad considering it was free money.

Scenario B: You borrowed 10,000ドル at 7.5%. After 25 years, you owe the lender 60,983ドル. This is due to the 7.5% interest rate he was charging you. But, you were able to grow the 10,000ドル you had borrowed at 10%. So, at the time you paid your debt, you had grown the initial money to a nice 108,347ドル. After paying off the debt, you are left with 47,364ドル.

Scenario C: You borrowed 5,000ドル at a ridiculous 16% rate. After the 25 years is up, you owe a whopping 204,371ドル. But, you were blessed with a beautiful return rate of 17.5%. You grew the 5,000ドル to a staggering 281,784ドル after 25 years of annual compounding. After your debt repayment, you're much better off than the other two people with a tidy sum of 77,413ドル.

To be fair, I should note that after 10 years, the person in Scenario A is doing the best, followed by the one in Scenario B. The one in Scenario C is probably kicking himself at this point having only a net just over 3,000ドル vs. the one in Scenario A with nearly 18,000ドル. It is in year 21 that the person from Scenario C overtakes them both and never looks back. Also, I should note that it is not until after the 24th year that Scenario B outpaces Scenario A.

So, the above scenarios are far from reality, because debt repayment doesn't work as above and also there's no risk-free investments yielding such high returns. But, the math is what it is. And, the fact that most people would not have chosen the best option says a lot about how little the public truly understands the powers of compounding.

Also, the above implies that if companies are able to achieve consistent high rates of return on investment, then it's not necessarily bad that they are taking on debt at fairly high rates. In fact, if they are able to keep their ROI at a high level over long periods of time, then taking on debt even at rates that aren't great would be hugely profitable.