8x1 multiplexer using 4x1 multiplexer

An 8x1 mux can be implemented using two 4x1 muxes and one 2x1 mux. 4 of the inputs can first be decoded using each 4-input mux using two least significant select lines (S0 and S1). The output of the two 4x1 muxes can be further multiplexed with the help of MSB of select lines at further stage. The implementation of 8x1 using 4x1 and 2x1 muxes is shown in figure 1 below:


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.