Ask Question and Get Free Answers - JUST Ask And Answer > QA > Science & Mathematics > Mathematics
Square game, find winning strategy?

Answers:1   |   LastAnswerAt:2010.10  

Question
visitor
Dragan K 
Asked at 2010.10.12 23:55:35
We have 100 cards around, any with number from 1 to 100, and two player.
First player take one card (any) and put it in the middle.
Second player take another card and put it on the first card, but the sum of bout cards must be a square.
Winner is who play last move.
Can you find the winning strategy?
answer Vikram P  Answered at 2010.10.12 23:55:35
Miryana is Correct, but this is only partly related to my question.

Maximum possible sum = 100+99 = 199

Possible Squares = 4, 9,16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196

This is different from my question in following manner

1) In my question one have to arrange all numbers from 1 to n, so when you start arranging numbers & you find "dead end" you must start again, However in your case such "dead ends" form part of winning strategy!

2) Total number of all such "dead ends" for larger "n" is very difficult to calculate but I can tell you that it will lie between smallest possible chain with "dead end" & entire arrangement for 1 to n.

Just for simplicity, I will start with n=20, here we can cover squares less than 20+19 = 39 which are 4,9,16,25,36

Consider Following play:
Path-1:
A: 20 B:5 A:4 B:12 A:13 B:3 A:6 B:10 A:15 B:1 A:8 B:17 A:19 B:Lost!

Number of cards played 13

Path-2
A: 20 B:16 A:9 B:7 A:2 B:14 A:11 B:5 A:4 B:12 A:13 B:3 A:6 B:10 A:15 B:1 A:8 B:17 A:19 B:Lost!
(Since B is left with 18 which can not be used)

Number of cards played = 19


The above scenario is just given as an example, even with n=20 it is very difficult to list down all such paths with "dead ends"

So for n=100 this can not be done manually, and there is no single best winning strategy as you can see player A's next move always depends upon B's move.

So in this kind of game with n=100 one can find which arrangements are beneficial to player 1 & which are not.


Here goes Pseudo Code giving winning strategies for n=100:

1) List all possible arrangements for n =100

2) Count number of cards used in each arrangement and store it with U(c) array

3) If U(c) is odd then first player (A) wins else second player (B) wins

4) So if U(c) is odd for 6 paths & is even for 4 paths then first player (A) has 60% chances of winning this game while second player (B) only has 40% chance

5) "A" should always know all the arrangements where U(c) gives odd numbers & should always try to force B to stick to that arrangement while "B" should always try to bring "A" on arrangements with U(c) = even number

6) B should try not to get stuck on a "UNIQUE" path
(for example Path-2 in above example) where U(c) = odd number while A must try not to get stuck on a "UNIQUE" path where U(c) = even number.

Now to find exact number we must build a program which will list all possible "dead ends" & "Unique Paths" for n=100 & then only we can conclusively answer this question

Hope this helps :)
1
  • Answer This Question:Square game, find winning strategy? 

  • insert image

    image url:

    such as: http://www.justaaa.com/**/**.jpg

    insert video

    vedio url: