Mancala!

The answer is Yes.

Hint : Find a sequence of moves player A makes, with each moving ending with a stone landing in her trough, so that she ends up placing more than half the stones in her trough. This way by the time player A puts more than half the stones in her trough, player B would never have even had a turn.

Can we generalize this argument to a board with n holes on each side? If not, for which n will this work? (I have not thought about this ...) Maybe someone will want to make a computer program which, for a given value of n, finds such a sequence (or exhausts all possibilities and thus shows it doesn't exist). Maybe there will be a pattern in the n's.

We could also try to increase the number of players in this game. For example, the board could be triangular for three players.

Edit: Below is some java code that finds such a sequence for a game with N holes per side and K>1 stones starting in each hole. For the cases I tested, it seems that such a sequence usually exists for any N and K>1, except if N = K. However, there are definitely other cases where such a sequence does not exists, for example: (N,K) = (24,48),(25, 50),(25,51),(25,52) but not (25,53).

The process seems quite complicated. Maybe a different way to look at it is this:

Consider a board with N,K given. Consider any distribution of the stones on the board. We can ask 2 questions:

1) Can we reach this board by a sequence of moves (only involving player A) from the starting board state?

2) Can player A win from this board state (with a sequence of moves only involving player A)?

Anybody have any ideas?

...

public class Mancala {

public static int N;
public static int M;
public static int startStonesPerHole;

public static void main(String[] args) { 
    N = Integer.parseInt(args[0]); // number of holes per side, usually 6
    M = 2*N + 2; // M is number of holes and troughs
    int[] board = new int[M]; // board, where index 0 is the left trough
                                    //index 7 is right trough
    startStonesPerHole = Integer.parseInt(args[1]);
                               // is number of stones starting in each hole
                               // is usually 4


    // initialize the board
    for(int i = 0; i < M; i++){
        if(i != 0 && i != N + 1){
            board[i] = startStonesPerHole;
        }
    }

    // bigMove returns a list of moves that correspond to a solution for player
    // A.  if such a list exists, the first index will be the number of moves;
    // otherwise it will be -1

    // Create an initial array of moves (make it sufficiently big)
    int[] initArrayOfMoves = new int[10000];

    int[] arrayOfMoves = bigMove(board, initArrayOfMoves);

    if(arrayOfMoves[0] == -1){
        System.out.println("false");
    } else{
        System.out.println("true");
        for(int i = 1; i <= arrayOfMoves[0]; i++){
            System.out.print(arrayOfMoves[i] + ", ");
        }
    }
}

// n is the index of the starting hole
// note that we had to have this method return a new board
// for in bigMove if just kept modifying the same board
// the recursion would not work
public static int[] move(int[] board, int n){
    // initialize the new board
    int[] newBoard = new int[board.length];
    for(int i = 0; i < newBoard.length; i++){
        newBoard[i] = board[i];
    }

    boolean doesEndInAsTrough = false;

    boolean stop = false;

    // here's the procedure:
    // set tempNumStones = newBoard[n]
    // take the stones from hole n (newBoard[n] = 0)
    // put the stones in holes n+1,n+2,...,n+tempNumStones (mod M)
    // then do this same procedure on hole n+tempNumStones (mod M)
    // but stop if
        // land in hole N + 1 (i.e., player A's trough), in which case
            // set doesEndInAsTrough = true
        // land in in hole 0 (i.e., player B's trough)
        // hole n + tempNumStones (mod M) had zero stones in it
    while(!stop){
        int tempNumStones = newBoard[n];
        newBoard[n] = 0;
        int indexOfLastHole = (n + tempNumStones) % M;
        int numInLastHole = newBoard[indexOfLastHole];
        for(int i = 1; i <= tempNumStones; i++){
            int index = (n + i) % M;
            newBoard[index] = newBoard[index] + 1;
        }
        if(indexOfLastHole == N + 1){
            doesEndInAsTrough = true;
            stop = true;
        } else if(indexOfLastHole == 0 || numInLastHole == 0){
            stop = true;
        } else{
            n = indexOfLastHole;
        }
    }

    // if the move on board starting at hole n does not end in player A's trough,
    // set newBoard[0] = -1;
    if(!doesEndInAsTrough){
        newBoard[0] = -1;
    }

    return newBoard;
}

public static int[] bigMove(int[] board, int[] listOfMoves){
    // if more than half the stones are in A's trough, then A wins, and we
    // are done. we return the successful list of moves
    if(board[N + 1] > N*startStonesPerHole){
        return listOfMoves;
    }

    for(int i = 1; i < M; i++){
        // if not more than half of the stones are in A's trough, then we search
        // for a move which starts with a nonempty hole i on A's side
        // and which ends with the last stone landing in A's trough
        // if we find such a move i, we perform it on the board,
        // update the list of moves which involves
            // incrementing the index 0 element
            // setting listOfMoves[listOfmoves[0]] = i
        // then call bigMove on this new board
        if(board[i] != 0 && i != N + 1){
        int[] newBoard = move(board, i);

        if(newBoard[0] >= 0){
            int[] tempListOfMoves = new int[listOfMoves.length];

            for(int j = 0; j <= listOfMoves[0] + 2; j++){
                tempListOfMoves[j] = listOfMoves[j];
            }

            tempListOfMoves[0] = listOfMoves[0] + 1;

            tempListOfMoves[tempListOfMoves[0]] = i;

            int[] newListOfMoves = bigMove(newBoard, tempListOfMoves);

            // bigMove gives us a new list of moves newListOfMoves that was
            // either successful
            // in which case newListOfMoves[0] > 0, and we return this list
            // otherwise this move is not successful, so we continue on with
            // the for loop

            if (newListOfMoves[0] > 0){
                return newListOfMoves;
            }
        } }
    }

    // if no such hole exists, then we are stuck and the sequence of moves
    // we followed down will not work
    // so we change the element at index 0 in list of moves to -1
    // and return it
    listOfMoves[0] = -1;

    return listOfMoves;
}

}

...