PROBLEM SOLVING

ASSIGNMENT-1

Name - SAMARTH BAHUGUNA

BATCH – 68
SAP ID - 590017956

PAGE 1
 QUESTIONS
1. A matchstick game is played with one pile of matches. Two players A and B take
turns to make a move. An allowed move is to remove 1, 3, or 4 matchsticks from
the pile. But, it
is not allowed to repeat the opponent’s last move (So, if, say, your opponent
removes 1 match,
your next move must be to remove 3 or 4 matches). The game ends when it is no
longer possible
to make a move. The player whose turn it is to move is the loser, and the other
player is the
winner.

2. A matchstick game is played with one pile of matches. Two players A and B take
turns to make a move. An allowed move is to remove one or two matchsticks from the
pile. The
game ends when it is no longer possible to make a move. The player who removes the last
stick
loses the game and the other player is the winner.

3. Two players alternately name dates. The winner is the player who names 3lst
December, and the starting date is 1st January.
(a) A player can name the 1st of the next month, or increase the day of the month
by an arbitrary amount, leaving the month unchanged.
(b) A player can increase the day by one, leaving the month unchanged, or name
the 1st of the next month.

4. Suppose there is one pile of matches. In each move, 2, 5 or 6 matches may be

removed. (That is, the subtraction set is {2 ,5 ,6}.)
(a) For each n, (0 ≤ n ≤ 22), determine whether a pile of n matches is a winning or losing
position/state.
(b) Identify a pattern in the winning and losing positions. Specify the pattern by giving
precise details of a boolean function of n that determines whether a pile of n matches is a
winning position or not.

5. There is one pile of stones. Two players are alternatively asked to remove stones
from the pile. On a player’s turn, he/she can remove any number of stones from the pile
with the
following restriction:
The number of stones a player removes from the pile cannot twice the number of stones
removed by the previous player. For the first move, the player is allowed to remove any
number
of stones from the pile as long as it’s less than the total.
The player who removes the last stone(s), wins the game.

6. We have a variant of snakes and ladders. In this game, there is just one counter. The

PAGE 2
two players take it in turn to move the counter at most four spaces forward. The start is
square 1
and the finish is square 25; the winner is the first to reach the finish. As in the usual game
of
snakes and ladders, if the counter lands on the head of a snake, it falls down to the tail of
the
snake; if the counter lands at the foot of a ladder, it climbs to the top of the ladder.
(a) List the positions in this game. Identify the winning and losing positions.
(b) (b) Some of the positions cannot be identified as winning or losing in this way.
Explain why.

7. a) There are two piles of matches. A move is to choose one pile and, from that pile,
remove
1, 2 or 3 matches. What are the winning positions and what is the winning strategy?
b) There are two piles of matches. A move is to choose one pile; from the left pile 1, 2 or
3
matches may be removed, and from the right pile 1 through 7 matches may be removed.
What are the winning positions and what is the winning strategy?
c) There are two piles of matches. A move is to choose one pile; from the left pile, 1, 3 or
4
matches may be removed, and, from the right pile, 1 or 2 matches may be removed.
What are the winning positions and what is the winning strategy?

8. A daisy has 16 petals arranged symmetrically around its center. There are two players.
A move involves removing one petal or two adjacent petals. The winner is the one who
removes
the last petal. Who should win and what is the winning strategy?
Generalise your solution to the case that there are initially n petals and a move
consists of
removing between 1 and M adjacent petals (where M is fixed in advance of the
game).

9. Two players are seated at a rectangular table which initially is bare. They each have an
unlimited supply of circular coins of varying diameter. The players take it in turns to place
a coin
on the table, such that it does not overlap any coin already on the table. The winner is the
one
who puts the last coin on the table. Who should win and what is the winning strategy?
What, if anything, do you assume about the coins in order to justify your answer?

10. A matchstick game is played with more than two piles of matches (can be three, four,
five, and so on…). Two players A and B take turns to make a move. An allowed move is
to select

PAGE 3
any one pile and then remove any number of matches from the that pile. The player who is
forced to remove the last matchstick loses the game, and the other player wins.
Problem is: what should be the winning strategy?

ANSWERS
COMMON DEFINITION:
LOSING POSITION: A position is a winning position if at least one of the positions that
can be obtained from this position by a single move is a losing position
WINNING POSITION: A position is a losing position if every position that can be
obtained from this position by a single move is a winning position

lets see the conditions:-

1. There are two players A & B
2. Player can only remove 1,3 or 4 matchsticks from the pile
3. It is not allowed to repeat opponent’s last move

lets discuss about the cases of winning and losing positions:-

Lets take number of matchsticks as “x”
If ~
x= 0
LP
x=1
WP
remove 1
x=0
x=2
WP
remove 1
x=1
x=3
WP
remove 3
x=0
x=4

PAGE 4
 WP
remove 4
x=0
x=5
WP
remove 1
x=4
x=6
WP
remove 3
x=3
x=7
WP
remove 4
x=3
If x=8, any move will lead to a losing position
x=9
WP
remove 1
x=8
x=10
WP
remove 3
x=7
x=11
WP
remove 4
x=7
x=12
LP on any move

— on every 8th position we get a losing position

— losing positions occurs when n is a multiple of 8

— winning position occurs at every left out values

So for winning, player should leave their opponent at the multiple of 8

This is the winning strategy

PAGE 5
2. For this we can approach symmetrically
Number of matchsticks will be denoted by “m”
lets discuss the given conditions:
1. Each player can move one or two matchsticks

2. Who so ever will remove last matchstick will loose the game

Lets discuss about the cases for winning and losing positions
M Winning position Losing position Remaining sticks

0 yes

1 Yes 0

2 yes 1

3 Yes 1

4 Yes 3

5 Yes 4

6 Yes —

7 yes 6

8 yes 7

9 Yes —

By analysing the cases we can see that on every 3rd position we are

Getting a losing position.

It simply means that at every multiple of 3 (m=0,3,6,9,12,…..) it will

lead

To a losing position

So you can win if you leave your opponent at every multiple of 3.

2. Conditions for the 1st game:

A player can either name the 1st of next month or increase the day of
The day of the current month by any amount without changing the
Month

PAGE 6
 Winning strategy for first player:
If the player forces the opponent to name which are closer to December
Without naming the last date, then he/she can win
Conditions for 2nd game:
The player can increase day by one keeping the month same
Or name the first of next month
Winning strategy for 2nd player:
Player should increase a day by one at a time
He can also jump to next month
Must remember to avoid naming 31st December

PAGE 7
 4. Lets discuss the winning and losing positions:

M Winning position Losing position

0 Yes

1 Yes

2 Yes

3 Yes

4 Yes

5 Yes

6 Yes

7 Yes

8 Yes

9 Yes

10 Yes

11 Yes

12 Yes

13 Yes

14 Yes

15 Yes

16 Yes

17 Yes

18 Yes

19 Yes

20 Yes

21 Yes

22 Yes

Winning positions are 2,3,4,5,6,8,9,10,11,12,14,15,16,17,18,20,21

& 22.

Losing states are 0,1,7&19

PAGE 8
 At every gap of 6 state we can observe a losing state and rest are

the Winning states

To express this as a boolean function of m:

We can represent F(m) as true in winning state and false as in losing

State

So F(m)=

F(m)= -(n/|6|=0)

5. Lets discuss the conditions of game:

First player can remove any number of stones from 1 to n-1
When first player removes x stones the next player can remove
1 and 2x-1 stones
Also they cannot remove the previous player’s count
Winning strategy for the player can be:

S Winning position Losing position Stones he took

1 Yes 1

2 Yes 1 or 2

3 Yes 1,2 0r 3

4 Yes 1 or 2

5 Yes

6 Yes

7 Yes

8 Yes

for the losing positions we can say that if second player play optimally
Then only first player will loose.

6. Lets discuss the winning and losing positions for the game

PAGE 9
 Position (p) Winning position Losing position Moves

1 Yes

2 Yes 345

3 Yes 456

4 Yes 567

5 Yes 678

6 Yes 789

7 Yes 8 9 10

8 Yes 9 10 11

9 Yes 10 11 12

10 Yes 11 12 13

11 Yes 12 13 14

12 Yes 13 14 15

13 Yes 14 15 16

14 Yes 15 16 17

15 Yes 16 17 18

16 Yes 17 18 19

17 Yes 18 19 20

18 Yes 19 20 21

19 Yes 20 21 22

20 Yes 21 22 23

21 Yes 22 23 24

22 Yes 23 24 25

23 Yes 24 25

24 Yes 25

25 Yes Win

Winning and losing positions are totally depend on the placement of

Snakes and ladders, dynamic nature of game as the placement of snake
And ladder can change the possible outcomes

PAGE 10
 Without knowing the arrangements of board we cannot specify the
Positions

7. a) winning and losing positions

-Position x and y is losing if every move leads to opponents
Win
-0,0 is losing position
-Winning position for opponent is when both piles are equal
-losing positions are 0,0 1,1 2,2 3,3 4,4……
-winning position for us is when x != y
B) winning and losing positions
-0,0 is losing position
-make move from when 1-3 from left and 1-7 right
- leave the opponent with less options

C) winning and losing positions

-0,0 is losing position
-focus on controlling left pile and limit the opponent’s move

PAGE 11
 8. Winning and losing positions
P1
Winning state as first player removes first and last petal
P2
Winning state as the first player removes both petals
P3
Winning state the first player removes 1 petal leaving 2 for other
P4
Wining state as the first player removes 1 petal leaving 3 for other
P5
Winning state as the player removes 1 petal leaving 4 for other
P6
Winning state as the first player removes 1 petal leaving 5 for
Other
P7
Winning state as the first player removes 1 petal leaving 6 for
Other
Positions like p8 p12 p16 are the losing positions because the positions
Where the number of remaining petals are the multiples of 4
Therefore any player can win if they don’t start with 4x=any number
They choose

PAGE 12
 9. Assumptions :
Infinte coins varying sizes
Table can hold multiple placements
Logical and optimal play
The first player should win the for following reasons:-
-Because at intial position the table is empty and they
Can place coin according to them
-they can control the space by making the move which occupies
Maximum space
-they can copy the second player’s move making it symmetrical
Winning strategy is by starting in the centre and ensuring he always plays
Last coin

10. Lets discuss the winning and losing positions:

If there are two piles, the player who is left with last stick in
One pile is in losing position
Winning position can be created if the first player aimed to
Create situations where opponent is in losing position
Symmetric piles can also lead to winning position
For 3 piles (3,4,5) player can remove sticks from 5th pile which is
Largest and creat situation like (3,4,3)
This will lead to unequal count of sticks in the piles
The winning strategy for this game can be minting the pace of
Game and creating symmetrical and equal counts of sticks in each
Pile

PAGE 13