Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This comes from a question on Arqade.

The background is, there's a mall level. Vlad the organized crime boss wants $50,000 worth of mall property destroyed. Your task is to shoot and blow stuff up until that happens.

There are 12 stores in the mall, and you have 3 grenades. After you blow up the first three stores, if you haven't ruined $50,000 worth of stuff in three explosions, you switch to your rifle and shatter store windows until you reach that limit. Then you leave.

Good wholesome fun.

The absolute value of the stores is unknown, but I'm interested in determining the relative value - obviously, I want to use my three grenades where they'll do the most good. As I see it, I have a set of 12 unknown variables, representing the value of each of the individual stores:

$ {O,P,Q,R,S,T,U,V,W,X,Y,Z} $

and one constant $C$, representing the value of windows.

I know which three stores I've destroyed and I can count how many windows I need to shoot to give me a Mission Accomplished.

Knowing only those two pieces of information, it should be possible through experimentation to order the unknown set. Let's say on trial #1 I destroy stores X,Y,Z and it takes me 4 windows to reach $50k. On trial #2, I destroy stores W,Y,Z and it takes 3 windows.

If $X + Y + Z + 4C = W + Y + Z + 3C$, then we can say that $W > X$.

What's the most efficient way to run this algorithm to conclusion for all 12 stores? Each trial takes about 6 minutes and I don't want to duplicate effort.

share|improve this question
add comment

1 Answer

Here's a good mathematical solution:

Run 12 trials, starting with $O+P+Q$, then $P+Q+R$, then $Q+R+S$, etc., and for each one record the number of windows as a negative integer. For example, $$\begin{align}O+P+Q&=-w_1\\ P+Q+R&=-w_2\\ Q+R+S&=-w_3\\ \vdots\\ X+Y+Z&=-w_{10}\\ Y+Z+O&=-w_{11}\\ Z+O+P&=-w_{12}\end{align}$$

This gives you an almost-tridiagonal matrix problem: $$\left[\begin{array}{cccccccccccc}1&1&1&0&0&0&0&0&0&0&0&0\\ 0&1&1&1&0&0&0&0&0&0&0&0\\ 0&0&1&1&1&0&0&0&0&0&0&0\\ &&&\ddots&\ddots&\ddots&\\ 0&0&0&0&0&0&0&0&0&1&1&1\\ 1&0&0&0&0&0&0&0&0&0&1&1\\ 1&1&0&0&0&0&0&0&0&0&0&1\\ \end{array}\right]\left[\begin{array}{c}O\\P\\Q\\R\\S\\T\\U\\V\\W\\X\\Y\\Z\end{array}\right]=\left[\begin{array}{c}-w_1\\-w_2\\-w_3\\\vdots\\-w_{10}\\-w_{11}\\-w_{12}\end{array}\right],$$ which you can either use your favorite package to solve, or calculate the actual inverse ahead of time if you'll be doing this a lot of times.

This will give you negative values for each store, and the largest (i.e., least negative) ones are the highest values.

I think it's not possible to know all the stores' values in fewer than 12 tests. It may be possible to determine the 3 largest values in fewer than 12 tests, but I don't have such an algorithm handy.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.