Incidentally, my test (testAll in Test3x3.java) finished running; it took around 50 minutes but it found that the 3x3 special-case and my general algorithm had the same result for every single 3x3 case. The result was 14703496002, in keeping with what you said previously.
However, I can't be that confident without testing some cases with higher values of n; ultimately what's needed is an actual proof that that algorithm always finds the correct solution.
I've got one part of the proof down, but it's pretty obvious anyway: (1) The highest value in each row and column must be marked in an optimal solution. Proof: Assume that there is an optimal solution with a row/column in which the highest value isn't marked. Then one could move the marker of that row/column to that value, obtaining a solution with a higher total. By contradiction, the assumption is false, and so (1) is proven.
The hard part is proving that you can't find better positions for the doubled-up markers, though.
Here's another algorithm; it's faster than my previous one but again I'm not sure if it's correct. I have a feeling that it is, but I haven't come up with a proof or a counterexample as yet. It's essentially a generalisation of your case for n=3. (1) Indirectly sort the elements of the matrix. This gives you the indices of the elements in order from the lowest element to the highest element. (2) Label all the elements in the matrix as "unknown" - you don't know if they are present in the optimal solution or not. (3) Take the lowest unknown element in the matrix, and mark it as unchosen. If doing so leaves only one unmarked element in that row, mark that element as chosen; do the same for the column - if this in turn leaves only one unmarked element in the same column/row, mark it in turn, etc. (4) Repeat step (3) until you have marked n^2-2n elements as unchosen, or you've marked 2n elements as chosen (I feel this second condition could only happen if the first was true anyway, though). (5) Mark all remaining unknown elements as chosen. Now your final result is the sum of all the chosen elements.
As I figure it, I think this should actually be O(n^2 log(n)).
EDIT: Okay, I did some testing, and it appears that the solutions it comes up with can fail to meet the solution criteria. Basically, consider a situation where the last remaining values in two rows and two columns are precisely the four values that lie in the intersection of those rows and columns. Then you would need to mark all of those values in the final solution, but this algorithm doesn't recognise that fact - it could still remove one of the values in that intersection, leaving only 3 values to select in a region that requires 4 to be chosen. I guess this kind of approach is useless, as it turns out.
I added your brute force 4x4 to test against my previous solver; it passed 1000 randomly generated test cases. Also, as it turns out, my algorithm is actually O(n^3), not O(n^4). I'm still thinking about a proof of correctness and/or counterexample though.
I don't have any proof yet, but I think the optimal solution to the Kaiji problem is to bet the max safe bet in every Slave round (since it has a higher payout) and bet 1mm in every King round. Once you lose once during slave, you keep betting 1mm every King round but during Slave rounds, you bet 1mm + the number of rounds you won, because wins earn you a little more buffer. I'll try to work out an average winnings for this.
Alright, I tried a few variations on strategy and the best I've gotten so far is 64.9439925862 by starting with King and betting the max safe bet every round no matter what. I'll see if I can fine tune it a bit.
EDIT: I have a new theory. King round is actually better than Slave round. Previously I was thinking of mm as lost no matter what, so S=1 and K=4/5. However, mm are only lost when you lose, so Slave is worth 5/4 per mm and King is worth 4 per mm. A new strategy starting with Slave and betting max on King, 1 on Slave yields 71.3105664.
FIFTY MILLIMETERS ALL DAY ERRY DAY, PUSSIES. I HAVE TWO EARS.
And <= 1 brain, so you still lose.
Anyways, I got bored of guessing strategies and wrote a recursive program to test every possible betting strategy for every possible result and use the best one. It won't tell me the best strategy, but it will tell me the best result, assuming it ever finishes running.
Aw, c'mon Ikatono. The logic behind the optimal strategy is relatively simple, though calculating the EV is a little more annoying.
You've got two of the main aspects of the strategy down: (1) On each round you want to either make the minimum bet of 1, or the maximum safe bet. (2) Emperor round is, roughly speaking, worth more than slave round because you're much more likely to keep your millimeters for the next round.
You can prove (1) easily enough with an inductive argument, which boils down to the fact that at every step of the way the EV for the optimal strategy is linear in the number of millimeters you have available, and the maximum value for a linear function must occur on the boundary values.
The one thing you're missing is this - what would be the optimal strategy if you were using Emperor first (and therefore using Slave for the last 3 rounds)?
A mm bet in round 10 has more potential value than in round 12 (because it can be bet later if you win), so bet max in the last Slave set.
King set is significantly more efficient than Slave set, so bet max in R7-9.
The first Slave set (R 4-6) is a bit trickier. The value of 1mm in a round is worth (5 + value in the next round)/5. I know that I should make the same bet in each round of a set, because you should only bet max if 1 mm is worth more than in a later set, and value within a set only changes if you bet max multiple times (Mmm has the same payoff per mm as mmM, and if M is better than m then MMM is optimal). That means I can compare rounds 6 and 7 directly.
Let x = the value of 1mm in round 7 (and subsequent bets) Let y = the value of 1mm bet in round 6
y = 1 + x/5
If x>y, bet minimum.
To prove x>y, take the value of 1mm in only rounds 7-9 (assume it's lost if you win all 3 to simply the estimation). This is 4/5 + 4/5 * 4/5 + 4/5 * 4/5 * 4/5 = 1.664. 1.664 / 5 + 1 = 1.3328 < 1.664, so bet minimum in R6, so bet minimum in R4-6.
The first set of Kings is more valuable than the second set of Kings, so it must be MMM.
Thus, the optimal strategy for KKKSSSKKKSSS is MMMmmmMMMMMM.
Yes, the optimal strategy is correct, although your proof of x>y isn't entirely correct because you've ignored the effect of rounds 10-12 on the value of x.
You have yet to state what the EV is - I'd like it as an exact value.
I know that the value of x is >= my estimation, so if my estimation is greater than y then so is x.
And I'll drop a few problem to try to revamp this thread. All of these are taken from past AIMEs.
2011 AIME II P7: Ed has five identical green marbles, and a large supply of identical red marbles. He arranges the green marbles and some of the red ones in a row and finds that the number of marbles whose right hand neighbor is the same color as themselves is equal to the number of marbles whose right hand neighbor is the other color. An example of such an arrangement is GGRRRGGRG. Let m be the maximum number of red marbles for which such an arrangement is possible, and let N be the number of ways he can arrange the m+5 marbles to satisfy the requirement. Find the remainder when N is divided by 1000.
2007 AIME I P10: In a 6 x 4 grid (6 rows, 4 columns), 12 of the 24 squares are to be shaded so that there are two shaded squares in each row and three shaded squares in each column. Let N be the number of shadings with this property. Find the remainder when N is divided by 1000.
2012 AIME I P5: The complex numbers z and w satisfy z^13 = w, w^11 = z, and the imaginary part of z is sin(mπ/n), for relatively prime positive integers m and n with m<n. Find n.
Well, for P7 I have so far that m=16; hopefully that's correct. EDIT: OK, my answer to P7 is 3. I can show working later. EDIT2: I checked against the online problems and solutions; my working and solution were both correct.
Note that you got the number wrong for your third problem - it's 2012 AIME I P6, not P5; that one was quite easy as well, for anyone familiar with complex numbers (I got the correct answer of 71).
2007 AIME I P10 is slightly trickier, though. Also, the wording is slightly poor - I'm going to assume they mean *exactly* two shaded squares in each row and three in each column. EDIT: I got the right answer for it, but my solution definitely could've been much more elegant. However, I didn't want to spend too long thinking about how to make it elegant.
Two players play a game which consists of two stages, A and B: A. Each player independently (without any knowledge of the opponent's choice), selects one of these swords: 1) Can only attack on odd-numbered rounds but hits every time it attacks. 2) Attacks every round but has an independent 50% chance to hit every round.
B. Repeated rounds (numbered 0, 1, 2, ...) occur during which their weapons are used on the other player. Each player dies when they take exactly n hits; if they both die in the same round, they both die. The game ends when one or both of the players die.
Questions: What are the probabilities of the three possible outcomes (player 1 survives, player 2 survives, both players die) for the various combinations (sword 1 vs sword 1, sword 1 vs sword 2, sword 2 vs sword 2), as a function of n?
Assuming that the players only care about their own survival and not the death of the other player, what's the optimal strategy for this game?
Alternatively, if you treat it as a zero-sum game, with 1 point for winning, 1/2 points for a draw, and 0 points for losing, what's the optimal strategy?
How would these results change if sword 1 attacked on even-numbered rounds instead of odd-numbered rounds?
reading this thread forces me to recall things i haven't done for 7 years, and which art school has systematically erased. that said, i loves math puzzle. going to think about this over food.
I find it interesting that you have it take 0.25 seconds or 0.5 seconds to hit, rather than hitting/missing immediately and then having a 0.25/0.5 second delay. That's the more typical instance in most video games I've seen... I think...
I find it interesting that you have it take 0.25 seconds or 0.5 seconds to hit, rather than hitting/missing immediately and then having a 0.25/0.5 second delay. That's the more typical instance in most video games I've seen... I think...
Both are worth considering; that's what the last question in my post is for.
In fact, I suspect the second version is the more interesting problem, with respect to the game theory - I expect there will be a mixed equilibrium.
I was just pointing out that the default assumption was different from mine. Obviously it would slightly favor the (1) with a little more front-loaded damage which is advantageous some of the time. It also means that any combat that wasn't chained back to back (there was more than 0.5 seconds between them, I guess any more than 0.25 seconds slightly favors), then the (1) starts to come out slightly ahead.
I was just pointing out that the default assumption was different from mine. Obviously it would slightly favor the (1) with a little more front-loaded damage which is advantageous some of the time.
I was just pointing out that the default assumption was different from mine. Obviously it would slightly favor the (1) with a little more front-loaded damage which is advantageous some of the time.
Nope.
What are you "Nope" ing? I'm right on what I was saying. Let's say that you have a situation where 1 opponent with 100 health joins the fight every second. The 1, because it would (in the front-loaded case) hit twice in 0.5 seconds, then cool down to swing twice on the next guy and so on, would never ever possibly fall behind.
Edit: I think you're Noping my comment in an assessment within the context of your question, which I'm not addressing. Correct? I'm still just talking general-isms about the differences.
Sorry, I think I misunderstood you there. Still, you weren't actually talking about the question posed in this thread...
Yes, if sword 1 gets to do damage in round 0 it has a definite advantage; especially in the limiting case where you can only survive 1 hit - in that case the player with sword 2 cannot win, though it's possible that both players will die.
However, if sword 1 beats sword 2 it makes things interesting here, because sword 1 vs sword 1 means mutually assured destruction.
1v1 is both sides tie always no matter the health. 2v2 is effectively random no matter the health. 1v2 is the only interesting situation here. To redo the cheese prompt a little: we have 2 swords, sword ! takes 2 sec to hit does 1 damage always, sword 2 takes 1 sec to hit does 1 damage but only hits 50% of the time. We can represent this as a series of rounds 0,1,2,3...n where B hits every round after 0 and A hits on even rounds after 0. In every case A will win if the game goes to 2n rounds, so we can find to probability of B winning as the odds that B does n damage in less than 2n rounds. Now since the odds of a hit are 50% this makes our probability pretty easy as the odds of any given set of hits in n rounds is (.5)^n. We then need to find every possible permutation of hits that will win so we have the sum of n<=m<=2n-1 m!/(2n-1-m) for m hits. so the odds of winning in less moves than sword 1 is .5^(2n-1)*sum(n<=m<=2n-1, m!/(2n-1-m)) or something like that, little rusty at this. Thinking about this there's a more accurate solution that doesn't assume you always go to 2n rounds, but i'm lazy.
1v1 is both sides tie always no matter the health. 2v2 is effectively random no matter the health.
While your winning and the other player winning are equiprobable, the chance of a tie is still relevant.
We then need to find every possible permutation of hits that will win so we have the sum of n<=m<=2n-1 m!/(2n-1-m) for m hits. so the odds of winning in less moves than sword 1 is .5^(2n-1)*sum(n<=m<=2n-1, m!/(2n-1-m)) or something like that, little rusty at this. Thinking about this there's a more accurate solution that doesn't assume you always go to 2n rounds, but i'm lazy.</p>
It isn't more accurate - the math is correct (I think). However, your expression can be simplified quite a bit.
The chance of both players dying is also relevant.
There's a one in infinity chance that two players both using the 50% chance to-hit swords will survive an infinite amount of turns. This is obviously the most desirable result, therefore a true Scottish gentleman would pick that sword and have some teahaggis.
1v1 is both sides tie always no matter the health. 2v2 is effectively random no matter the health.
While your winning and the other player winning are equiprobable, the chance of a tie is still relevant.
We then need to find every possible permutation of hits that will win so we have the sum of n<=m<=2n-1 m!/(2n-1-m)! for m hits. so the odds of winning in less moves than sword 1 is .5^(2n-1)*sum(n<=m<=2n-1, m!/(2n-1-m)!) or something like that, little rusty at this. Thinking about this there's a more accurate solution that doesn't assume you always go to 2n rounds, but i'm lazy.</p>
It isn't more accurate - the math is correct (I think). However, your expression can be simplified quite a bit.
The chance of both players dying is also relevant.
For both dieing the math is pretty simple: .5^(2n)*1/n (after simplifying the permutation eqn (n-1)!/((2n-1) - (n-1))!) as there's a more limited set of permutations. Assuming the maths part of my stuff above is right.
Edits: Bad math woo! Still not quite sure I did that right.
Comments
However, I can't be that confident without testing some cases with higher values of n; ultimately what's needed is an actual proof that that algorithm always finds the correct solution.
I've got one part of the proof down, but it's pretty obvious anyway:
(1) The highest value in each row and column must be marked in an optimal solution.
Proof: Assume that there is an optimal solution with a row/column in which the highest value isn't marked. Then one could move the marker of that row/column to that value, obtaining a solution with a higher total. By contradiction, the assumption is false, and so (1) is proven.
The hard part is proving that you can't find better positions for the doubled-up markers, though.
(1) Indirectly sort the elements of the matrix. This gives you the indices of the elements in order from the lowest element to the highest element.
(2) Label all the elements in the matrix as "unknown" - you don't know if they are present in the optimal solution or not.
(3) Take the lowest unknown element in the matrix, and mark it as unchosen. If doing so leaves only one unmarked element in that row, mark that element as chosen; do the same for the column - if this in turn leaves only one unmarked element in the same column/row, mark it in turn, etc.
(4) Repeat step (3) until you have marked n^2-2n elements as unchosen, or you've marked 2n elements as chosen (I feel this second condition could only happen if the first was true anyway, though).
(5) Mark all remaining unknown elements as chosen. Now your final result is the sum of all the chosen elements.
As I figure it, I think this should actually be O(n^2 log(n)).
EDIT: Okay, I did some testing, and it appears that the solutions it comes up with can fail to meet the solution criteria. Basically, consider a situation where the last remaining values in two rows and two columns are precisely the four values that lie in the intersection of those rows and columns. Then you would need to mark all of those values in the final solution, but this algorithm doesn't recognise that fact - it could still remove one of the values in that intersection, leaving only 3 values to select in a region that requires 4 to be chosen. I guess this kind of approach is useless, as it turns out.
EDIT: I have a new theory. King round is actually better than Slave round. Previously I was thinking of mm as lost no matter what, so S=1 and K=4/5. However, mm are only lost when you lose, so Slave is worth 5/4 per mm and King is worth 4 per mm. A new strategy starting with Slave and betting max on King, 1 on Slave yields 71.3105664.
Anyways, I got bored of guessing strategies and wrote a recursive program to test every possible betting strategy for every possible result and use the best one. It won't tell me the best strategy, but it will tell me the best result, assuming it ever finishes running.
You've got two of the main aspects of the strategy down:
(1) On each round you want to either make the minimum bet of 1, or the maximum safe bet.
(2) Emperor round is, roughly speaking, worth more than slave round because you're much more likely to keep your millimeters for the next round.
You can prove (1) easily enough with an inductive argument, which boils down to the fact that at every step of the way the EV for the optimal strategy is linear in the number of millimeters you have available, and the maximum value for a linear function must occur on the boundary values.
The one thing you're missing is this - what would be the optimal strategy if you were using Emperor first (and therefore using Slave for the last 3 rounds)?
King set is significantly more efficient than Slave set, so bet max in R7-9.
The first Slave set (R 4-6) is a bit trickier. The value of 1mm in a round is worth (5 + value in the next round)/5. I know that I should make the same bet in each round of a set, because you should only bet max if 1 mm is worth more than in a later set, and value within a set only changes if you bet max multiple times (Mmm has the same payoff per mm as mmM, and if M is better than m then MMM is optimal). That means I can compare rounds 6 and 7 directly.
Let x = the value of 1mm in round 7 (and subsequent bets)
Let y = the value of 1mm bet in round 6
y = 1 + x/5
If x>y, bet minimum.
To prove x>y, take the value of 1mm in only rounds 7-9 (assume it's lost if you win all 3 to simply the estimation). This is 4/5 + 4/5 * 4/5 + 4/5 * 4/5 * 4/5 = 1.664. 1.664 / 5 + 1 = 1.3328 < 1.664, so bet minimum in R6, so bet minimum in R4-6.
The first set of Kings is more valuable than the second set of Kings, so it must be MMM.
Thus, the optimal strategy for KKKSSSKKKSSS is MMMmmmMMMMMM.
Correct?
You have yet to state what the EV is - I'd like it as an exact value.
And I'll drop a few problem to try to revamp this thread. All of these are taken from past AIMEs.
2011 AIME II P7:
Ed has five identical green marbles, and a large supply of identical red marbles. He arranges the green marbles and some of the red ones in a row and finds that the number of marbles whose right hand neighbor is the same color as themselves is equal to the number of marbles whose right hand neighbor is the other color. An example of such an arrangement is GGRRRGGRG. Let m be the maximum number of red marbles for which such an arrangement is possible, and let N be the number of ways he can arrange the m+5 marbles to satisfy the requirement. Find the remainder when N is divided by 1000.
2007 AIME I P10:
In a 6 x 4 grid (6 rows, 4 columns), 12 of the 24 squares are to be shaded so that there are two shaded squares in each row and three shaded squares in each column. Let N be the number of shadings with this property. Find the remainder when N is divided by 1000.
2012 AIME I P5:
The complex numbers z and w satisfy z^13 = w, w^11 = z, and the imaginary part of z is sin(mπ/n), for relatively prime positive integers m and n with m<n. Find n.
EDIT: OK, my answer to P7 is 3. I can show working later.
EDIT2: I checked against the online problems and solutions; my working and solution were both correct.
2007 AIME I P10 is slightly trickier, though. Also, the wording is slightly poor - I'm going to assume they mean *exactly* two shaded squares in each row and three in each column.
EDIT: I got the right answer for it, but my solution definitely could've been much more elegant. However, I didn't want to spend too long thinking about how to make it elegant.
A. Each player independently (without any knowledge of the opponent's choice), selects one of these swords:
1) Can only attack on odd-numbered rounds but hits every time it attacks.
2) Attacks every round but has an independent 50% chance to hit every round.
B. Repeated rounds (numbered 0, 1, 2, ...) occur during which their weapons are used on the other player. Each player dies when they take exactly n hits; if they both die in the same round, they both die. The game ends when one or both of the players die.
Questions:
What are the probabilities of the three possible outcomes (player 1 survives, player 2 survives, both players die) for the various combinations (sword 1 vs sword 1, sword 1 vs sword 2, sword 2 vs sword 2), as a function of n?
Assuming that the players only care about their own survival and not the death of the other player, what's the optimal strategy for this game?
Alternatively, if you treat it as a zero-sum game, with 1 point for winning, 1/2 points for a draw, and 0 points for losing, what's the optimal strategy?
How would these results change if sword 1 attacked on even-numbered rounds instead of odd-numbered rounds?
I think you need to change sword 1 to attack on evens if you're going to start counting from 0.
correct me if I am misunderstanding something.
edit: rescinded
In fact, I suspect the second version is the more interesting problem, with respect to the game theory - I expect there will be a mixed equilibrium.
Edit: I think you're Noping my comment in an assessment within the context of your question, which I'm not addressing. Correct? I'm still just talking general-isms about the differences.
Yes, if sword 1 gets to do damage in round 0 it has a definite advantage; especially in the limiting case where you can only survive 1 hit - in that case the player with sword 2 cannot win, though it's possible that both players will die.
However, if sword 1 beats sword 2 it makes things interesting here, because sword 1 vs sword 1 means mutually assured destruction.
2v2 is effectively random no matter the health.
1v2 is the only interesting situation here.
To redo the cheese prompt a little:
we have 2 swords, sword ! takes 2 sec to hit does 1 damage always, sword 2 takes 1 sec to hit does 1 damage but only hits 50% of the time.
We can represent this as a series of rounds 0,1,2,3...n where B hits every round after 0 and A hits on even rounds after 0.
In every case A will win if the game goes to 2n rounds, so we can find to probability of B winning as the odds that B does n damage in less than 2n rounds.
Now since the odds of a hit are 50% this makes our probability pretty easy as the odds of any given set of hits in n rounds is (.5)^n.
We then need to find every possible permutation of hits that will win so we have the sum of n<=m<=2n-1 m!/(2n-1-m) for m hits.
so the odds of winning in less moves than sword 1 is .5^(2n-1)*sum(n<=m<=2n-1, m!/(2n-1-m))
or something like that, little rusty at this. Thinking about this there's a more accurate solution that doesn't assume you always go to 2n rounds, but i'm lazy.
The chance of both players dying is also relevant.
teahaggis.Edits: Bad math woo! Still not quite sure I did that right.