[araver]

Assume two players have an infinite amount of equal/identical regular polygon figures (N sides, N>=3) and play the following game:

1) First player places M>1 figures on the table in any position he wants.

2) Second player can move the figures on the table without rotating them (only translation is allowed). Figures can be made to overlap.

Second player wins if he can completely cover one figure using some or all of the rest of the figures already on the table. Otherwise first player wins.

Question 1) For what M and N does the second player always have a winning strategy?

Question 2) For what M and N does the first player always have a winning strategy?

Question 3) Is N important for the winning strategy?

P.S. It's not original. I found a simpler version in an online puzzle competition (which is about to end anyway). But I liked it very much, so I'm sharing it

Edited November 25, 2010 by araver

[Guest]

Any regular polygon could be completely covered by 3 other regular polygons no matter how they are placed.

So, as long as M<4, player 1 always has a winning strategy. It is independant of N.

Edited November 25, 2010 by DeeGee

[araver]

Any regular polygon could be completely covered by 3 other regular polygons no matter how they are placed.

So, as long as M<4, player 1 always has a winning strategy. It is independant of N.

Care to elaborate the reason? (as a bonus since its not asked directly in the OP?)

[Guest]

Care to elaborate the reason? (as a bonus since its not asked directly in the OP?)

Since the polygons can not be rotated by the 2nd player, the maximum number of polygons would be needed if each polygon is placed slightly rotated wrt the each other by player 1. That way, player 2 can choose any polygon to cover and each polygon would need equal number of other polygons to cover it completely.

When the player 2 starts covering the polygons starting from one edge of the polygon to be covered, he will cover one side completely with one polygon but leave out at least 2 other sides that need to be covered separately. That is, one polygon will not be able to cover the other two sides.

May not be the best explanation on paper (not easy to explain), but if you try it practically, you will hopefully see what I mean.

[araver]

Since the polygons can not be rotated by the 2nd player, the maximum number of polygons would be needed if each polygon is placed slightly rotated wrt the each other by player 1. That way, player 2 can choose any polygon to cover and each polygon would need equal number of other polygons to cover it completely.

When the player 2 starts covering the polygons starting from one edge of the polygon to be covered, he will cover one side completely with one polygon but leave out at least 2 other sides that need to be covered separately. That is, one polygon will not be able to cover the other two sides.

May not be the best explanation on paper (not easy to explain), but if you try it practically, you will hopefully see what I mean.

As I said, your answers to Q1, Q2, Q3 are correct and your proposed strategy works for that case. But there is a nice proof (besides trying it practically) for that in all cases, not just the one you mentioned (which may or may not be what player 1 choses to play).

I'm adding a question to the OP, about a slightly modified version of the game, which hopefully might provide a hint on why the strategy works in all cases.

Question 4) For what M and N does the second player always have a winning strategy, if the figure that needs to be covered is selected by the first player?

[Guest]

As I said, your answers to Q1, Q2, Q3 are correct and your proposed strategy works for that case. But there is a nice proof (besides trying it practically) for that in all cases, not just the one you mentioned (which may or may not be what player 1 choses to play).

I'm adding a question to the OP, about a slightly modified version of the game, which hopefully might provide a hint on why the strategy works in all cases.

Question 4) For what M and N does the second player always have a winning strategy, if the figure that needs to be covered is selected by the first player?

Well, I tried it practically after thinking of this reason.

So, without trying out this new part practically, I would still say M<4. The reason being - as figures are either rotated (or not) wrt each other, there would still be same number of polygons required to cover it even if player 1 chooses which polygon to cover.

[araver]

Well, I tried it practically after thinking of this reason.

So, without trying out this new part practically, I would still say M<4. The reason being - as figures are either rotated (or not) wrt each other, there would still be same number of polygons required to cover it even if player 1 chooses which polygon to cover.

Correct answer again (although you did not use spoilers this time ).

Yet I'm afraid we're not on the same page on what a proof means.

I can say for example that xⁿ+yⁿ=zⁿ has no solutions for natural numbers (n>2,x,y,z>0). And even if one would agree with me, one would still require proof, right? And simply saying that the best way to find a solution is considering x and y relatively close and then showing that for this case there is no z, is not a (complete) proof.

[Guest]

If we can cover the circumscribed circle of a polygon with 3 inscribed circles from the same polygon, then the result will be proved. I know that 3 circles can cover a larger circle if the ratio of their radii is approx 0.85 or greater (old puzzle I saw). This is true where cos(360/2N)> 0.85, or N>=8. For N < 8, we could simply use inspection, though I'm sure there's a more elegant proof.

[araver]

If we can cover the circumscribed circle of a polygon with 3 inscribed circles from the same polygon, then the result will be proved. I know that 3 circles can cover a larger circle if the ratio of their radii is approx 0.85 or greater (old puzzle I saw). This is true where cos(360/2N)> 0.85, or N>=8. For N < 8, we could simply use inspection, though I'm sure there's a more elegant proof.

I had a similar idea, although it's not necessary (but it is sufficient) to cover the whole circumscribed circle with the 3 inscribed circles. The polygon itself will do. E.g. for N=3

I'm interested in the 0.85 rule you mentioned so I'll look into it. So far it checks out.

Question 1) For what M and N does the second player always have a winning strategy? - Deegee: M>=4. Rajat_magic: Proof for M>=4, N>=8 - STILL OPEN for N<8.

Question 2) For what M and N does the first player always have a winning strategy? - Deegee: M<=3. Proven for M=3, M=2 - CLOSED.

Question 3) Is N important for the winning strategy? - Deegee: No. - STILL OPEN (pending proof for Q1).

Question 4) For what M and N does the second player always have a winning strategy, if the figure that needs to be covered is selected by the first player? - Deegee: It is the same answer as Q1. Proven for N>=8 by rajat_magic. - STILL OPEN (pending proof for Q1)

[Guest]

I had a similar idea, although it's not necessary (but it is sufficient) to cover the whole circumscribed circle with the 3 inscribed circles. The polygon itself will do. E.g. for N=3

I'm interested in the 0.85 rule you mentioned so I'll look into it. So far it checks out.

clearly, as you said, it is not necessary for the circumscribed circle to be covered (else I would have also prooved that the proposition was false for N<8). Covering the circumscribed circle was just an easy approach (I work 14 hr days - just sneak in 10 mins here and there to check out problems on this site, so quick & dirty = good). Regarding the 0.85 result - it is an approximate result that has somehow stuck in my head from many years ago (it was some sort of "practical maths activity" in school as a teenager). The exact ratio can probably be calculated more precisely.