Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
0
Notifications Mark All Read
- Login
- Get Prime
0
Pick a Stick Puzzle
Stick Game Puzzle
Pick a stick puzzle has two players who are playing a game where they have several sticks lying in a bunch on a table. On their turn, a player has to pick at most 4 sticks. The player who takes the last stick off the table wins. Suppose the game starts with 17 sticks on the table devise a strategy such that the player who starts first wins.
Solution
Solution for Pick a Stick Puzzle:
Let the player who starts the game be player 1, and the other player be player 2.
The goal of player 1 should be to reduce the pile to 5 sticks for his opponent in the second last move. Such that player 2 when making his final move (second last of the game) will have 5 sticks on the board. Now player 2 cannot pick all 5 the maximum he can pick is 4. Therefore, whatever number of sticks he picks between 1-4, there will be at least 1 stick on the table. Which player 1 will pick and win.
Now a strategy that player 1 should follow to make this plan successful. He can start by picking 2 sticks, reducing the number of sticks to 15. Depending on the second move (player 2’s first move), the following are the possible ways the game will go:-
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Case 1: Player 2 picks 4 sticks in his first move
Player 1:- picks 2
Player 2:- picks 4
Sticks left 11
Player 1:- picks 1
Stick left 10
Player 2:- picks 4
Sticks left 6
Player 1:-picks 1
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 4
Sticks left 11
Player 1:-picks 1
Stick left 10
Player 2:- picks 3
Sticks left 7
Player 1:-picks 2
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 4
Sticks left 11
Player 1:- picks 1
Stick left 10
Player 2:- picks 2
Sticks left 8
Player 1:- picks 3
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 4
Sticks left 11
Player 1:- picks 1
Stick left 10
Player 2:- picks 1
Sticks left 9
Player 1:-picks 4
Sticks left 5
Player 1 wins
Case 2: Player 2 picks 3 sticks in his first move
Player 1:- picks 2
Player 2:- picks 3
Sticks left 12
Player 1:- picks 2
Stick left 10
Player 2:- picks 4
Sticks left 6
Player 1:-picks 1
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 3
Sticks left 12
Player 1:-picks 2
Stick left 10
Player 2:- picks 3
Sticks left 7
Player 1:-picks 2
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 3
Sticks left 12
Player 1:- picks 2
Stick left 10
Player 2:- picks 2
Sticks left 8
Player 1:- picks 3
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 3
Sticks left 12
Player 1:- picks 2
Stick left 10
Player 2:- picks 1
Sticks left 9
Player 1:-picks 4
Sticks left 5
Player 1 wins
Case 3: Player 2 picks 2 sticks in his first move
Player 1:- picks 2
Player 2:- picks 2
Sticks left 13
Player 1:- picks 3
Stick left 10
Player 2:- picks 4
Sticks left 6
Player 1:-picks 1
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 2
Sticks left 13
Player 1:-picks 3
Stick left 10
Player 2:- picks 3
Sticks left 7
Player 1:-picks 2
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 2
Sticks left 13
Player 1:- picks 3
Stick left 10
Player 2:- picks 2
Sticks left 8
Player 1:- picks 3
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 2
Sticks left 13
Player 1:- picks 3
Stick left 10
Player 2:- picks 1
Sticks left 9
Player 1:-picks 4
Sticks left 5
Player 1 wins
Case 4: Player 2 picks 1 stick in his first move
Player 1:- picks 2
Player 2:- picks 1
Sticks left 14
Player 1:- picks 4
Stick left 10
Player 2:- picks 4
Sticks left 6
Player 1:-picks 1
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 1
Sticks left 14
Player 1:-picks 4
Stick left 10
Player 2:- picks 3
Sticks left 7
Player 1:-picks 2
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 1
Sticks left 14
Player 1:- picks 4
Stick left 10
Player 2:- picks 2
Sticks left 8
Player 1:- picks 3
Sticks left 5
Player 1 wins
Player 1:- picks 2
Player 2:- picks 1
Sticks left 14
Player 1:- picks 4
Stick left 10
Player 2:- picks 1
Sticks left 9
Player 1:-picks 4
Sticks left 5
Player 1 wins
Therefore from the above solutions, we can see that if player 1 picks 2 sticks he will win the game irrespective of where player 2 moves afterward.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment