Before getting started with the main puzzle, lets build up some confidence with famous interview question.
"You have 100 coins labeled 1 to 100 on them. They are put up in line randomly, such that no order maintained. Its your turn first and you can pick up any coin which is either first or last. At the end of 5oth round, whoever will have higher the summation of coin-values will be the winner. If you are given first chance, find out winning strategy (or at least 'non loosing' strategy)."
Now lets move on to the main puzzle.
"Sid begins by marking a corner square of n by n chessboard. Sud marks an orthogonally adjacent square. Thereafter, Sid and Sud continue alternating each marking a square adjacent to the last one marked, until no unmarked adjacent square is available at which the player whose turn it is to play loses.
For which n does Sid have a winning strategy??"
The first one:
ReplyDeletelet the numbers be A1,A2,... A100
color all coins A1,A3,A5...A99 black and color A2,A4...A100 white. If black sum is more, claim all black coins, otherwise claim all white coins. How to claim all black(or white) coins, i leave as an exercise for others.
The first one:
ReplyDeletelet the numbers be A1,A2,... A100
color all coins A1,A3,A5...A99 black and color A2,A4...A100 white. If black sum is more, claim all black coins, otherwise claim all white coins. How to claim all black(or white) coins, i leave as an exercise for others.
is it mandatory to pick up a coin or we are allowed to pass??
ReplyDeleteits mandatory to pick coin whenever your turn comes.
ReplyDeletefor any n which is odd. because it will have odd number of squares. So if Sid starts filling then he will be the last one to fill a square. hence sud would lose it everytime n is odd.
ReplyDeleteits not that easy. you can deliberately create voids where nobody can mark.
ReplyDeletejust try solving for rectangles that can be used to generlize solution.....what i mean is 1*n rectangle give solution 2*n and so on ....while building for 3*n you can use this both go on doing it.
ReplyDeletefor n odd, there will be a winning strategy. Strategy is: sid will mark the adjacent square in the same direction sud marks.sid can always find such a square(as n is odd). if sid does not get such sqre, he will hit the path they had travelled.this will give a smaller box surrounded by their path with total odd no of squares,in which again sid will start markin from corner(here corner is the adjacent squre of one which sud marked).thus sid will always mark the last sqre, and win.
ReplyDelete