And, this problem is also from Aditya. I guess this will take more time :)
"In general, in a n X n tic tac toe, if we get n consecutive 'X' or 'O' (horizontally ,diagonally, vertically) its a win. The possible number of chances(ways) to win for a given n X n tic tac toe is 2n+2. (n- horizontal, n- vertical, 2 diagonals). If we change the rules as shown below :
Take a variable k which can vary from 1 to n. Even if the user get k consecutive X or O (horizontally ,diagonally, vertically) ,its a win for a given k value in a n X n tic tac toe. The question is what are the possible number of chances(ways) to win. (find an expression in the form of n and k). For example in a 3 X 3 tic tac toe if k = 2 then the number of possible ways to win is 20. your expression should give this value for n=3(nXn) and k=2."
"In general, in a n X n tic tac toe, if we get n consecutive 'X' or 'O' (horizontally ,diagonally, vertically) its a win. The possible number of chances(ways) to win for a given n X n tic tac toe is 2n+2. (n- horizontal, n- vertical, 2 diagonals). If we change the rules as shown below :
Take a variable k which can vary from 1 to n. Even if the user get k consecutive X or O (horizontally ,diagonally, vertically) ,its a win for a given k value in a n X n tic tac toe. The question is what are the possible number of chances(ways) to win. (find an expression in the form of n and k). For example in a 3 X 3 tic tac toe if k = 2 then the number of possible ways to win is 20. your expression should give this value for n=3(nXn) and k=2."
1 comment:
Ok, This is an example for counting problems. Duc Ha and me got the following result:
- Base case: k = 1 simple
- 2<=k<=n: counting the number of ways in rows + the number of ways in rows + the number of ways in "all" diagonals. We have:
2*n(n-k+1) + 2*(n-k+1) + 4*sum_{i=k}^{n-1} (i-k+1).
Post a Comment