|
|
friendofgunnar
Honorable
Legendary Hero
able to speed up time
|
posted May 08, 2010 12:34 AM |
|
|
Lessee, the distance from Pooh's house to the meeting point is X. The distance from Piglet's house to the meeting point is Y. Pooh's speed is Y in one minute. Piglet's speed is X in 4 minutes. The time it took Pooh to get to the meeting point is therefore X/(Y/1).
t = X/(Y/1)
which is the same amount of time it took Piglet to get to the meeting point
t = Y/(x/4)
X/Y = 4Y/X
X^2 = 4Y^2
X = 2Y
So Pooh took 3 minutes. Piglet took 6 minutes.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
|
posted May 08, 2010 01:31 AM |
|
Edited by dimis at 01:33, 08 May 2010.
|
Q13. The Algebra of Cooperation
Alright, looks like we have technical skills!
Q13. Solve the number rebus
USA + USSR = PEACE .
(The same letters stand for the same digits, different letters denote different digits.)
(B. Kruglikov)
____________
The empty set
|
|
Corribus
Hero of Order
The Abyss Staring Back at You
|
|
posted May 08, 2010 06:07 PM |
|
Edited by Corribus at 18:08, 08 May 2010.
|
For Q13, here's a hint to get people starting: it's very easy, using logic, to figure out what U, P and E stand for. If a four digit number plus a three digit number add to a five digit number, what must the five digit number start with??
I'll wait a little while and provide my full solution after some people have given the problem some time.
____________
I'm sick of following my dreams. I'm just going to ask them where they're goin', and hook up with them later. -Mitch Hedberg
|
|
friendofgunnar
Honorable
Legendary Hero
able to speed up time
|
|
posted May 09, 2010 04:42 AM |
|
|
Here is an interesting problem that comes from the risk game. Let's say that somebody is trying to break your continent bonus and they need to conquer two territories to do it. For example you have south america and you control both Sao Paulo and Dakar. If you have 12 armies what is the best way to distribute them between the two territories to form the best defense?
11 and 1
10 and 2
9 and 3
8 and 4
7 and 5
6 and 6
or does it not make any difference at all how you arrange them?
I'll recapitulate the rules if anybody needs them:
The outcome of battles is decided by rolling dice.
The attacking player rolls one to three dice based on how many armies are in the area he is attacking form.
2 armies -> 1 dice
3 armies -> 2 dice
4 or more armies - > 3 dice
The defending army rolls one or two dice based on how many armies are in the defending area.
1 army -> 1 dice
2 or more armies ->2 dice
The attacker and defender compare the highest dice. If the attacker is higher one of the defender's armies is destroyed. If not then one of the attacker's armies is destroyed (a tie means the attacker is destroyed). Then, if both the attacker and defender rolled more than one dice they compare the next highest dice. If the attacker is higher one of the defender's armies is destroyed. If not one of the attacker's armies is destroyed.
The attacker can keep going as long as he wants and can stop the attack at any time. This makes sense if the attacker's armies drops below 4 because at that point the odds are usually against him. The only time the odds are with the attacker is if he's attacking 3 dice against 2, 3 dice against 1, or 2 dice against one. The odds are against the attacker if he's attacking 2 dice against 2, 1 dice against 2, or 1 dice against 1.
If the attacker destroys all the defender's armies he conquers the territory and can move in as many armies as he pleases. If not the attack has failed.
BTW
I solved this statistically by writing a computer program, not mathematically. If anybody can do this mathematically I will be duly impressed.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
|
posted May 10, 2010 05:36 AM |
|
Edited by dimis at 05:54, 10 May 2010.
|
Hey FoG,
First of all, are you aware that you can calculate the following probabilities:
Defender Rolls 1 Die
Attacker Rolls 1 Die
-- Probability Attacker Wins: 15/36 = 41.67%
-- Probability Defender Wins: 21/36 = 58.33%
Attacker Rolls 2 Dice
-- Probability Attacker Wins: 125/216 = 57.87%
-- Probability Defender Wins: 91/216 = 42.13%
Attacker Rolls 3 Dice
-- Probability Attacker Wins: 855/1,296 = 65.97%
-- Probability Defender Wins: 441/1,296 = 34.03%
Defender Rolls 2 Dice
Attacker Rolls 1 Die
-- Probability Attacker Wins: 55/216 = 25.46%
-- Probability Defender Wins: 161/216 = 74.54%
Attacker Rolls 2 Dice
-- Probability Attacker Wins: 295/1,296 = 22.76%
-- Probability Defender Wins: 581/1,296 = 44.83%
-- Draw (Both Lose 1 Unit): 420/1,296 = 32.41%
Attacker Rolls 3 Dice
-- Probability Attacker Wins: 2,890/7,776 = 37.17%
-- Probability Defender Wins: 2,275/7,776 = 29.26%
-- Draw (Both Lose 1 Unit): 2,611/7,776 = 33.58%
?
____________
The empty set
|
|
Binabik
Responsible
Legendary Hero
|
|
posted May 10, 2010 08:56 AM |
|
|
Quote:
Q13. Solve the number rebus
USA + USSR = PEACE
_USSR
__USA
------
PEACE
P=1
_USSR
__USA
-----
1EACE
U=9
_9SSR
__9SA
-----
1EACE
E=0
_9SSR
__9SA
-----
10AC0
S can = 2 thru 8
If S=2 then A=1 and R=9 -> not true
If S=3 then A=2 and R=8 and C=7 -> this works
P=1
U=9
E=0
S=3
A=2
R=8
C=7
9338+932=10270
|
|
Binabik
Responsible
Legendary Hero
|
|
posted May 10, 2010 09:33 AM |
|
Edited by Binabik at 09:51, 10 May 2010.
|
You guys can continue with your questions, but in the meantime I finally found my PCB software after hunting for it for several months. I thought some people might like some simple topology puzzles in the form of very simple circuit board design. (I had to throw in the topology word to make in on topic in a math thread )
I was planning on drawing up some custom puzzles from scratch, but I ran across a few files that I think are easy enough to post here. So we get a small part of a real circuit board.
The idea is to connect the red rectangles at the bottom with the correct circle at the top.
A real circuit board wouldn't be done this way, but I added labels to the "pads". The purple letters A-Z correspond to the bottom row of red "pads" from left to right, followed by the numbers 1-6. So A is on the far left with 6 on the far right.
If it's not obvious, the purple labels correspond with the pad to the lower right of the label.
Here's the rules.
1) Connect all the pads at the bottom with the correct pads at the top.
2) None of the lines are allowed to cross. (That's a short circuit. I call it the smoke test the first time power is applied )
3) You can't route anything below the red pads.
4) Lines (henceforth "traces" to use proper language) may enter/exit the round pads at top from any angle. You have as much room as you want above the top row of pads.
5) Between horizontally or vertically adjacent round pads, you may only route 2 traces max.
6) Between diagonally adjacent round pads, you may route 3 traces.
I've cleaned the clutter in this one if it's any easier to work with.
I've been doing this off and on for 30 years, so it's kind of hard to judge how it will be for others, but I'm pretty sure this should be an easy one.
If you're curious, notice that 26 letters + 6 numbers equal 32 total. This is one input channel of a 32 bit video router. If I remember right it's 4 X 32 bit input channels and 4 X 32 bit output channels. So any of the 4 input channels can be routed to any of the 4 output channels. Pretty simple circuit.
edit: Adding a close up of what I mean by rules 5 and 6. This pic is close to maximum "density" with two traces going between the adjacent horizontal pads, and 3 between the diagonal pads.
|
|
friendofgunnar
Honorable
Legendary Hero
able to speed up time
|
|
posted May 10, 2010 03:43 PM |
|
|
|
@dimis, yeah you've got the first part. In order to solve the problem mathematically though you have to be able to compile every possible outcome of a campaign to conquer both territories under each defensive configuration. Because I never really delved deeply into probability math I can't think of an easy way to do it. I solved it by writing a program that fights a lot of campaigns, which is what I mean by solving it statistically.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
|
posted May 10, 2010 05:21 PM |
|
Edited by dimis at 18:07, 10 May 2010.
|
I am still not sure what we are trying to do, so I will ask another thing. Do you know that based on the previous numbers we can come up with plots like this (based on exact numbers):
?
____________
The empty set
|
|
Corribus
Hero of Order
The Abyss Staring Back at You
|
|
posted May 10, 2010 05:38 PM |
|
|
Binabik wrote:
Quote:
P=1
U=9
E=0
S=3
A=2
R=8
C=7
Yes, this is the correct answer. However, here's how you can do it without resorting to trial and error, and want to prove that there is only one solution:
Starting from:
9SSR
9SA
-----
10AC0
From the rightmost column, the sum of R and A must be 10.
(1) R + A = 10
The second rightmost column: the sum of S plus itself plus 1 (carried over from the 10 in the rightmost column) equals either C (if the sum is less than 10) or 10 + C (if the sum is more than 10).
(2) Either 2S + 1 = C ; or 2S + 1 = C + 10.
The third rightmost column: The sum of 9 + S has to be greater than ten, so a 1 digit will be carried over. However, if the sum of 2S + 1 was greater than 10, we'll have an extra 1 to contend with. Therefore
(3) Either S + 9 = A + 10 ; or S + 10 = A + 10.
This gives us two sets of three equations to work with.
It's pretty clear that if S + 10 = A + 10, then S = A, which is forbidden because each letter represents a different digit. Therefore we're left with a single set of three equations.
(1) R + A = 10
(2) 2S + 1 = C
(3) S = A + 1
Each digit can have a value of no more than 9. Also, from equation 2, the digit represented by C must be odd. Therefore C = 7, 5 or 3 (it can't be 1 because P is already 1 and it can't be 9 because U is already 9).
This basically gives us only three combinations might work:
C = 7, S = 3, A = 2, R = 8
C = 5, S = 2, A = 1, R = 9
C = 3, S = 1, A = 0, R = 10
The second and third combiantions don't work because A cannot = 0 or 1 and R cannot = 9 or 10.
Therefore the only solution is C = 7, S = 3, A = 2, R = 8 (and U = 9, E = 0 and P = 1).
By the way, Binabik, it's a little unclear to me what the object is of the circuit puzzle. Could you provide a completed example?
____________
I'm sick of following my dreams. I'm just going to ask them where they're goin', and hook up with them later. -Mitch Hedberg
|
|
alcibiades
Honorable
Undefeatable Hero
of Gold Dragons
|
|
posted May 10, 2010 06:06 PM |
|
|
I was going to say this was impossible, but I think this one plays by all the rules, or did I miss something?
____________
What will happen now?
|
|
Corribus
Hero of Order
The Abyss Staring Back at You
|
|
posted May 10, 2010 08:36 PM |
|
Edited by Corribus at 20:37, 10 May 2010.
|
I'll pose one now so that dimis has a chance to play.
Back to dimis's numbering system:
Q14. Let a pair of numbers (x,y) be called square if their sum (x + y) and product (xy) are both perfect squares. For instance, 5 and 20 are square because 20+5 = 25 (5^2) and 20*5 = 100 (10^2). Prove that no pair can be square if one of the members is equal to 3.
By the way, I don't have the answer, so it'll be news to me, too.
____________
I'm sick of following my dreams. I'm just going to ask them where they're goin', and hook up with them later. -Mitch Hedberg
|
|
Warmonger
Promising
Legendary Hero
fallen artist
|
|
posted May 10, 2010 08:43 PM |
|
|
|
alcibiades
Honorable
Undefeatable Hero
of Gold Dragons
|
|
posted May 10, 2010 09:58 PM |
|
|
Quote:
Alci, you routed four paths diagonally between pins on the right side of the chip.
True, doesn't matter,however, there's plenty of room to draw that line the other way around (on the right side) of the blue dot, so that should not be an issue.
EDIT > In fact I've done it a number of times on the right hand half side of the diagram, but it's all in the bottom row, so there's plento of room to simply shift all the lines a row to the right.
____________
What will happen now?
|
|
Binabik
Responsible
Legendary Hero
|
|
posted May 11, 2010 02:31 AM |
|
Edited by Binabik at 05:41, 11 May 2010.
|
Quote:
By the way, Binabik, it's a little unclear to me what the object is of the circuit puzzle. Could you provide a completed example?
Alci did exactly what I was looking for. There is a natural solution to this. And although there are probably many solutions, his solution is almost exactly the same as mine because it's the most obvious.
What I was looking for was to illustrate one of the most basic patterns in circuit board design. If you notice his solution, the same or very similar pattern is repeated four times. I assume that once he saw the basic pattern, then it became easy to do the rest of them.
Strictly from the mathematics topology point of view, the rule about only 2 traces between pads is somewhat of a red herring. By the rules of topology, the shapes (traces and pads) can be stretched, twisted and formed as much as needed, so long as they maintain the same basic topological shape. This would allow for infinite traces to run between pads and still maintain network integrity.
However, adding this restriction makes the puzzle a little more realistic. It also illustrates the difference between theory and real world. In the real world we can't have infinitely narrow traces, they can only be manufactured to some minimum width (typically around 0.004 inches or 0.1mm).
So let's look at some topology.
The two shapes below are topologically the same. (ignore the round pads for now)
Now lets make two of that shape. The pair on the left is NOT topologically the same as the shape on the right.
Now let's create a "circle". The two shapes on the left are the same. But they are different than the shapes on the right. In each case we have electrically connected the four nodes of the network, however that does not mean they are electrically or topologically the same. See the delta and star networks here. The first two shapes below would be delta configurations, the far right would be a star configuration, and the third from left is a "daisy chain" which is the most common configuration, but not shown in the wiki example.
Now let's make a figure 8. They are electrically and topologically the same. (ignoring the inductor I created on the right in case anyone catches that)
I'm going to call this shape a ladder.
Now let's modify the ladder and make it 8 copies of our very first shape.
Now let's play some games. Remember the first pair of shapes? They were electrically and topologically the same.
Let's continue that thought.
And finally, let's look closely at what Alci did. He said he initially thought it was impossible, but it's easy once you see it.
The shape is already there, you just have to find it.
|
|
friendofgunnar
Honorable
Legendary Hero
able to speed up time
|
|
posted May 11, 2010 05:33 AM |
|
|
@dimis, yes you're on your way. You still have to answer the fundamental question though which is "Does the way the defender split his army affect the likelihood that he will be conquered?" And if so for a defender's army N, what is the best formation for a two territories?
N - 1, 1
N - 2, 2
N - 3, 3
etc...
BTW what software are you using?
|
|
Ecoris
Promising
Supreme Hero
|
|
posted May 11, 2010 10:39 AM |
|
|
Quote:
I'll pose one now so that dimis has a chance to play.
Back to dimis's numbering system:
Q14. Let a pair of numbers (x,y) be called square if their sum (x + y) and product (xy) are both perfect squares. For instance, 5 and 20 are square because 20+5 = 25 (5^2) and 20*5 = 100 (10^2). Prove that no pair can be square if one of the members is equal to 3.
By the way, I don't have the answer, so it'll be news to me, too.
Ah, perfect squares. There's a strategy that never seems to fail and it works in this case too:
Any perfect square is congruent to 0 or 1 modulo 4. (I.e. either x^2 or x^2 - 1 is divisible by four).
Say x = 3. Then y has to be congruent to 1 or 2 modulo 4 if x+y is to be a sqaure. But then their product is congruent to either 2 or 3 modulo 4, hence not a square.
This proves it not just for 3, but also for 7, 11, 15, ...
It is now natural to ask the following question: For each x not congruent to 3 modulo 4, is there a y such that (x,y) is a 'square-pair'?
____________
|
|
alcibiades
Honorable
Undefeatable Hero
of Gold Dragons
|
|
posted May 11, 2010 12:45 PM |
|
|
Quote:
And finally, let's look closely at what Alci did. He said he initially thought it was impossible, but it's easy once you see it.
Actually, the reason why I thought it was impossible was because of the assymetry of how you placed the letters - i.e. group Q through X is closer to group I through P than it is to group Y through 6. Thus, I had to modify the whole thing midway because I thought the distance between groups were the same. 
____________
What will happen now?
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
|
posted May 11, 2010 05:49 PM |
|
Edited by dimis at 20:13, 11 May 2010.
|
Risk
@Fog:
For me the above analysis is the end of the road and the reasons why last time I played Risk was 8 years ago; I will explain shortly.
First of all, for the first part regarding the probabilities of the various outcomes of a single "conflict", I proved them all on a piece of paper (we can go through them; that's one problem on its own). I had done the same calculations in the past, but they are in some drawer in Greece... Anyway, for the second part, I didn't use software either. However, for the second part most likely you need a computer because the exact fractional values for the probabilities that are plotted come as entries in a matrix that captures the behavior of the corresponding Markov Chain for the "battle" process. For this reason, if I have to perform these computations again I would use Maple, because at some point in the computations, we need the inverse of a Matrix and Maple is handy there. Of course the other option is to write down everything on my own. In any case this involves solving many partial problems. In fact, I had created relevant programs in the past, but just like the notes above, they are in Greece too. So, right now, essentially you are asking me to write down a similar program again... For the second part I write that most likely we need a computer because I haven't written anything down yet in order to check if we can get a closed form of the inverse matrix I describe above. However, this Markov Chain has a kind of "suspicious" matrix in the sense that we might be able to infer the inverse by induction. I am just making this comment here for the mathematical point of view and it is true that I haven't checked it in the past either. However, the motivation is low because of what is about to come. Btw, the picture above for the second part comes from here, where the guy models everything as a Markov Chain and performs the computations that we want; so, for the actual plotted values I just trust him right now, but I can also verify everything independently if this is needed (however, I remember vividly the shape of the line A=D in his plot from my own work in the past and this is for sure ok).
Anyway, let's come back to your initial question, which is about the "optimal configuration of troops" between two countries. First of all, you are also hiding additional information. How many people are considered to be attackers ? One ? Two ? More ? How many troops does the attacker(s) have ? What sort of strategy/ies will he/they follow ? Is his/their sole purpose to break our benefit of having an entire continent ? We really have to specify these if we want a well-posed question, otherwise we can not get an answer. Also, how many neighboring countries does Dakar have on the map ? How many different opponents are in these countries ? So, from now on we have to start assuming stuff and I am wondering what you assume in your simulations. But regardless, the natural way of rephrasing the "optimal splitting" of the army is to find the configuration that minimizes the probability that the attacker wins.
The probability that the attacker wins both countries is equal to the product of the probabilities of conquering both. By the plot it is obvious that we should split the army in such a way that all the troops are concentrated in one of the two regions if the guy attacks with the same amount of troops both regions. Another idea for these computations is to fix the amount of troops the attacker is willing to dedicate to the whole process, compute the expected losses in the first battle, and now compute the probability that the attacker wins the second battle with the remaining forces.
But I don't want to stop even there. The plot also makes it clear that as long as the attacker comes with at least our troops and that number is at least 5, then he is bound to win. So that minimization above is kind of pointless, because the end result is the same. We will lose the continent if we simply defend (with high probability). And even if we are lucky and our dice rolls go against the expected scenarios that are plotted and we don't lose the continent, we will be significantly weakened (as well as our opponent). What I am trying to say here is that there is no such thing as best defense in Risk because all of them are bound to fail under very reasonable assumptions. And now that we have suffered significant losses, another guy can come after us (we are an easy prey). He will have more troops and we are bound to lose again. So, what is the point of a game where no matter how well you play, if two people come after us, we lose with high probability ? This is precisely the reason that I do not participate in the game that you guys want to start. Perhaps there is something interesting in the case of 1vs1 but then, there are better 1vs1 games; chess, heroes (III) ...
And here I will give you an anecdote. So, 8 years ago we were gathered together at a house of a friend and we played Risk. At some point I was going after domination in the north and south America. When I conquered Alaska, another guy (SirAlkis; I just mention his name because some people know him too) had reached the north-eastern-most part of Asia (Kamchaka) in the previous turn and we had a stack facing each other. However, both of us had fronts in many other regions too (none of which was between the two of us). So my move was to withdraw the army from Alaska and relocate it in other fronts. The reason is that it was pointless for both of us to open another front. Now, Alkis realized the nature of my move, and did not attack. However, when I made the move, the other two guys did not get the reason, and they said that because we were close friends (me and Alkis) we had agreed not to fight each other in advance (which was certainly not true since we had other conflicts in other parts of the world earlier). So, now the two other players wanted to punish us and both of them came after me. Needless to say, I was the first one out of the game since I had to face two armies and the probabilities in this game are working against the defender; simply because this is the nature of the game. In the end, they also suffered significant losses because I was still trying to minimize their probability of winning (which is really painful when you are defending and losing), and finally Alkis dominated everywhere because meanwhile he was also reaping the benefits of Australia and at some point (points ?) Asia. That was the last time I played Risk since the next day I started looking at all the above analysis and the result really is disappointing for the defender. Bottom line, if at least two people decide not too late in the game to come after us, then no matter how well we play we are bound to lose. That was the last time I played Risk and probably for ever.
Do you want to know how the exact values are computed via Markov Chains in the second plot above ?
____________
The empty set
|
|
ihor
Supreme Hero
Accidental Hero
|
|
posted May 11, 2010 06:03 PM |
|
|
Since Ecoris posted his solution on Q14, I'll post mine. Its not so short and elegant, but its mine .
3+x=a^2
3x=b^2
Since 3 divides b^2, then 3 divides b and therefore b^2 is divisible by 9. So x is divisible by 3. Let x=3y.
We have
3(1+y)=a^2
9y=b^2  y=c^2
So
3(1+c^2)=a^2
Similarly to the first part we get 1+c^2 is divisible by 3, which is impossible since c^2 is congruent to 0 or 1 modulo 3. Thus we have a contradiction.
|
| |
|
|
This thread is pages long: 
