Matchstick game bonanza!!

Problem: There are 'N' matchsticks placed on the table. You and your opponent are to pick any number of matchsticks between 1 and 5. Its your turn first. The one picking the last stick loses the game. You have to device a strategy such that you always win the game.Also, is there any starting number that cannot guarantee that you always win?

Solution: Here, you have to ensure that the control of the game always remains in your hands. Let us approach this problem from the last. The last matchstick has to be picked by your opponent so as to ensure your win. So, your last turn must ensure that there must be only one matchstick left on the table. If this is not the case, say there are 2 matchsticks. Then, your opponent will pick 1 stick and you are left with only one stick to pick and lose the game.

Similarly, one turn before last of your opponent, there must be more than 6 sticks so that he cannot leave you with 1 stick by picking 5 of them. But if there are more than 7 sticks, he may leave you with the same situation by leaving 7 on the table. If you leave 7, the other can at max pick 5 and min 1 leaving any number between 6 and 2 on the table. You can now pick the desired number leaving the last stick to be picked by him. Now, if there were 8 sticks on the table, your opponent would pick 1 leaving you with 7 sticks. :-( Similarly, one turn before, you should have left 13 sticks on the table.

So, your approach should be to leave (6M + 1) sticks on the table always. Ensure that at the end of each round, 6 less matchsticks are there on the table. (For instance, if your opponent picks 3 sticks, you also pick 3).

But there is a catch in this game, if there are already (6M + 1) sticks on the table initially, and its your turn first, you cannot ensure after your first turn the winning strategy. Now, the control goes into the hand of your opponent and you are at the verge of losing the game.

Similarly, 5 can be replaced with any number 'K'. At the end of each turn, you have to ensure there are (K+1)M + 1 sticks left on the table.

2-input XOR gate using 2:1 mux

2-input XOR gate using 2x1 mux: Figure 1 shows the truth table for a 2-input XOR gate where A and B are the two inputs and OUT is equal to XOR of A and B. If we observe carefully, OUT equals B when A is '0' and B' when A is '1'. So, a 2:1 mux can be used to implement 2-input XOR gate if we connect SEL to A, D0 to B and D1 to B'.

Figure 1: Truth table of 2-input XOR gate

Figure 2 shows the implementation of 2-input XOR gate using 2x1 mux.

Figure 2: Implementation of 2-input XOR gate using 2x1 mux

Similarly, we can connect B to select of mux, and get the XOR gate implemented using similar procedure.

Also read:

• NOT gate using 2:1 mux
• 2-input NOR gate using 2:1 mux
• 2-input XNOR gate using 2:1 mux
• 2-input OR gate using 2:1 mux
• 2-input NAND gate using 2:1 mux
• 2-input AND gate using 2:1 mux