6.042/18.062J Mathematics for Computer Science February 15,2005
Srini Devadas and Eric Lehman
Problem Set 3 Solutions
Due,Tuesday,February 22 at 9 PM
Problem 1,An urn contains 75 white balls and 150 black balls,While there are at least
2 balls remaining in the urn,you repeat the following operation,You remove 2 balls
selected arbitrarily and then,
If at least one of the two balls is black,then you discard one black ball and put the
other ball back in the urn,
If both of the balls are white,then you discard them both and put a new black ball
into the urn,
Prove that the urn never reaches the state where it is empty except for one black ball,
Solution,We use induction,Let P(n) be the proposition that the urn always contains
an odd number of white balls,
Base case,Initially,the urn contains 75 white balls,which is an odd number,so P(0) is
true,
Inductive step,Suppose that the urn contains an odd number of white balls after n steps,
If there are fewer than 2 balls remaining,then the process ends,Otherwise,there are then
two cases,
1,You draw at least one black ball,Then the number of black balls decreases by one
and the number of white balls is unchanged,Therefore,the number of white balls
remains odd,
2,You draw two white balls,Then the number of black balls increases by one,and the
number of white balls decreases by two,Again,the number of white balls remains
odd,
Thus,the urn still contains an odd number of white balls after n + 1 steps,By induction,
the urn always contains an odd number of white balls,Therefore,the urn can never hold
just one black ball and zero white balls,since zero is even,
Problem 2,A puzzle toy contains the numbers 1,...,35 written on small circular disks,
The disks are arranged on an oval track with no gaps so that the whole sequence of disks
can slide clockwise or counterclockwise around the track,
2 Problem Set 3
1 2
3
4
5
6
7
Disks slide around track.
of four disks.
Turning dial reverses the order
35
34
33
In addition,the track runs through a circular dial that is four disks wide,This dial can be
rotated 180 degrees,reversing the order of the four disks on that portion of the track,For
example,if the dial were turned in the con?guration above,then the the order of 34,35,
1,2 would become 2,1,35,34,
Suppose that the puzzle is initially in the state shown above with numbers increasing
counterclockwise around the track,Prove that no sequence of operations has the effect of
swapping disks only 1 and 2 while leaving all the other disks in the same order,
Solution,Associate each con?guration of the puzzle with a permutation of the num-
bers 1,...,35 by taking the numbers in counterclockwise order starting in the middle of
the dial,Thus,the example con?guration corresponds to the permutation,
1 2 3,.,35
Now we use induction on the number of operations,Let P(n) be the proposition that
after n operations,there are an even number of inversions,
Base case,Initially,there are zero inversions,Since zero is even,P(0) is true,
Inductive step,Suppose that after n steps there are an even number of inversions,There
are now three cases to consider,
Suppose the dial is turned 180 degrees,This transforms the permutation
s
1
s
2
s
3
s
4
...s
32
s
33
s
34
s
35
into the permutation,
s
35
s
34
s
3
s
4
...s
32
s
33
s
2
s
1
3 Problem Set 3
This amounts to swapping s
1
with s
35
and s
2
with s
34
,Each swap changes the parity
of the number of inversions,so after two swaps there are still an even number of
inversions,
Suppose that the numbers are rotated one position clockwise around the track,This
transforms the permutation
s
1
s
2
s
3
s
4
...s
32
s
33
s
34
s
35
into the permutation,
s
2
s
3
s
4
...s
32
s
33
s
34
s
35
s
1
This reverses the order of exactly 34 pairs of disks,s
1
and every other disk,This
changes the parity of the number of inversions 34 times,which leaves an even num-
ber of inversions,
Similarly,rotating one position counterclockwise reverses the order of 34 pairs,
again leaving an even number of inversions,
By induction,the number of inversions is always even,Therefore,the con?guration in
which 1 and 2 are swapped (which has 1 inversion) is unreachable,
Problem 3,A regular 52-card deck is arranged as follows,
A? 2,.,K? A? 2?,.,K? A? 2?,.,K? A? 2?,.,K?
In a perfect shuf?e,the deck is?rst divided into two piles,one containing the top 26 cards
and the other the bottom 26,These two piles are then recombined into a single deck by
perfectly interlacing them,
This interlacing process can be done in two different ways since the new top card could
come from the top of either 26-card pile,So over a sequence of perfect shuf?es,many
different arrangements of the deck can be obtained,Prove that no sequence of perfect
shuf?es puts the deck in the following order,
A? 2?,.,K? A? 2?,.,K? A? 2?,.,K? A? 2?,.,K?
Solution,We use induction,De?ne the cards in the i-th and (52? i)-th positions in
the deck to be opposites,Thus,for example,the top card is opposite the bottom card,the
second card is opposite the next to last card,and the two cards in the middle of the deck
4 Problem Set 3
are opposite each other,Let P(n) be the proposition that opposite cards are the same
color,
Base case,In the initial con?guration,hearts are opposite diamonds and clubs are opposite
spades,Therefore,all opposite cards are the same color,
Inductive step,Suppose that all opposite cards are the same color,Consider an arbitrary
con?guration of the deck,
c
1
c
2
c
3
.,, c
52
A perfect shuf?e leaves the deck in one of the following orders,
c
1
c
27
c
2
c
28
c
3
c
29
.,, c
25
c
51
c
26
c
52
c
27
c
1
c
28
c
2
c
29
c
3
.,, c
51
c
25
c
52
c
26
In both cases,exactly the same cards remain opposites,c
1
and c
52
,c
2
and c
51
,etc,So,in
particular,opposite cards are still the same color,
By induction,opposite cards are always the same color,Therefore,the hearts,clubs,
diamonds,spades con?guration is unreachable since there all opposite cards are different
colors,
Problem 4,Prove the following basic facts about greatest common divisors,
(a) gcd(ka,kb) = k · gcd(a,b) for all k > 0.
Solution,The smallest positive value of
s · (ka) + t · (kb) = k a + t b)· (s · ·
over all s,t ∈ Z is k times the smallest positive value of
s a + t b· ·
over all s,t ∈ Z,The?rst quantity is gcd(ka,kb) and the second is gcd(a,b),There-
fore,gcd(ka,kb) = kgcd(a,b),
(b) gcd(a,b) = gcd(a + kb,b) for all k ∈ Z,
Solution,We show that every linear combination of a and b is a linear combination
of a + kb and b and vice-versa,
If x = s a + t b,then x = s
· (a + kb) + t
b where s
= s and t
= t? s
k.· · ·
If x = s
· (a + kb) + t
b,then x = s a + t b where s = s
and t = t
+ s
k.· · ·
Thus,in particular,the smallest positive linear combinations are equal,so gcd(a,b) =
gcd(a + kb,b),
5 Problem Set 3
Problem 5,Here is a long run of composite numbers,
114,115,116,117,118,119,120,121,122,123,124,125,126
Prove that there exist arbitrarily long runs of composite numbers,Consider numbers a
little bigger than n! where n! = n·(n?1) 3 2 1.··· · ·
Solution,Let k be some natural number such that 1 < k ≤ n,We know k (n! + k)|
because k | n! and k k,Thus,the numbers n!+2,n!+3,n!+4,...,n!+n are all composite,|
This is a run of n?1 consecutive composite numbers,Because we can choose n arbitrarily,
we know arbitrarily long runs of composite numbers exist,
Problem 6,Here is a very,very fun game,Initially,there is a blackboard with the numbers
1309 and 1729 written on it,Now you and I take turns; you go?rst,On each player’s
turn,he or she must write a new positive integer on the board that is the difference of two
numbers that are already there,The?rst person who can not create a new number loses
the game,
For example,your?rst move must be 1729? 1309 = 420,Then I could play either
1309?420 = 889 or 1729?420 = 1309,and so forth,
(a) Prove every number written on the board is a multiple of 7 less than or equal to
1729,
Solution,We use induction,Let P(n) be the proposition that after n moves,every
number on the board is a positive linear combination of 1729 and 1390,
Base case,P(0) is true because 1729 and 1390 are trivial linear combinations of 1729
and 1390,
Inductive step,Assume that after n moves,every number on the board is a positive
linear combination of 1729 and 1390,The next number written on the board is also
a positive linear combination,because,
The rules require the number to be positive,
The new number must be a difference of two numbers already on the board,
which are themselves linear combinations of 1729 and 1390 by assumption,
And a difference of linear combinations is another linear combination,
By induction,every number on the board is a positive linear combination of 1729
and 1390,And every positive linear combination of 1729 and 1390 is a multiple of
gcd(1729,1390) = 7,
(b) Prove that every positive multiple of 7 less than or equal to 1729 is on the board
at the end of the game,
Solution,Let x be the smallest number on the board at the end of the game,By
the Division Algorithm,there exist integers q and r such that 1729 = q ·x + r where
6 Problem Set 3
0 ≤ r < x,When no more moves are possible,1729? x must already be on the
board,and thus so must 1729? 2x,.,, 1729? (q? 1)x,However,1729? qx = r can
not be on the board,since r < x and x is de?ned to be the smallest number there,
The only explanation is that r = 0,which implies that x | 1729,By a symmmetric
argument,x | 1390,Therefore,x is a common divisor of x and y,The only common
divisors of 1729 and 1390 are 1 and 7,and x can not be 1 by the preceding problem
part,Therefore,7 is on the board at the end of the game,Since no more moves are
possible,1729? 7,1729? 2 7,.,,,7,0 must all be on the board as well,So every ·
positive multiple of of 7 less than or equal to 1729 is on the board at the end of the
game,
(c) Who wins?
Solution,There are 1729/7 = 247 numbers on the board at the end of the game,
Thus,there were 247? 2 = 245 moves,Since you go?rst,you also get the last move
and win the game,
Problem 7,Prove the following theorem,
Theorem,If gcd(a,b) = 1,then gcd(a + b,a? b) = 1 or 2,
Solution,Since gcd(a,b) = 1,there exist integers s and t such that,
s· a + t· b = 1
Now there is a linear combination of a + b and a? b equal to 2,
(s + t)· (a + b) + (s? t)· (a? b) = 2(s· a + t· b) = 2
Thus gcd(a + b,a? b) is at most 2,which implies it is equal to 1 or 2,
Srini Devadas and Eric Lehman
Problem Set 3 Solutions
Due,Tuesday,February 22 at 9 PM
Problem 1,An urn contains 75 white balls and 150 black balls,While there are at least
2 balls remaining in the urn,you repeat the following operation,You remove 2 balls
selected arbitrarily and then,
If at least one of the two balls is black,then you discard one black ball and put the
other ball back in the urn,
If both of the balls are white,then you discard them both and put a new black ball
into the urn,
Prove that the urn never reaches the state where it is empty except for one black ball,
Solution,We use induction,Let P(n) be the proposition that the urn always contains
an odd number of white balls,
Base case,Initially,the urn contains 75 white balls,which is an odd number,so P(0) is
true,
Inductive step,Suppose that the urn contains an odd number of white balls after n steps,
If there are fewer than 2 balls remaining,then the process ends,Otherwise,there are then
two cases,
1,You draw at least one black ball,Then the number of black balls decreases by one
and the number of white balls is unchanged,Therefore,the number of white balls
remains odd,
2,You draw two white balls,Then the number of black balls increases by one,and the
number of white balls decreases by two,Again,the number of white balls remains
odd,
Thus,the urn still contains an odd number of white balls after n + 1 steps,By induction,
the urn always contains an odd number of white balls,Therefore,the urn can never hold
just one black ball and zero white balls,since zero is even,
Problem 2,A puzzle toy contains the numbers 1,...,35 written on small circular disks,
The disks are arranged on an oval track with no gaps so that the whole sequence of disks
can slide clockwise or counterclockwise around the track,
2 Problem Set 3
1 2
3
4
5
6
7
Disks slide around track.
of four disks.
Turning dial reverses the order
35
34
33
In addition,the track runs through a circular dial that is four disks wide,This dial can be
rotated 180 degrees,reversing the order of the four disks on that portion of the track,For
example,if the dial were turned in the con?guration above,then the the order of 34,35,
1,2 would become 2,1,35,34,
Suppose that the puzzle is initially in the state shown above with numbers increasing
counterclockwise around the track,Prove that no sequence of operations has the effect of
swapping disks only 1 and 2 while leaving all the other disks in the same order,
Solution,Associate each con?guration of the puzzle with a permutation of the num-
bers 1,...,35 by taking the numbers in counterclockwise order starting in the middle of
the dial,Thus,the example con?guration corresponds to the permutation,
1 2 3,.,35
Now we use induction on the number of operations,Let P(n) be the proposition that
after n operations,there are an even number of inversions,
Base case,Initially,there are zero inversions,Since zero is even,P(0) is true,
Inductive step,Suppose that after n steps there are an even number of inversions,There
are now three cases to consider,
Suppose the dial is turned 180 degrees,This transforms the permutation
s
1
s
2
s
3
s
4
...s
32
s
33
s
34
s
35
into the permutation,
s
35
s
34
s
3
s
4
...s
32
s
33
s
2
s
1
3 Problem Set 3
This amounts to swapping s
1
with s
35
and s
2
with s
34
,Each swap changes the parity
of the number of inversions,so after two swaps there are still an even number of
inversions,
Suppose that the numbers are rotated one position clockwise around the track,This
transforms the permutation
s
1
s
2
s
3
s
4
...s
32
s
33
s
34
s
35
into the permutation,
s
2
s
3
s
4
...s
32
s
33
s
34
s
35
s
1
This reverses the order of exactly 34 pairs of disks,s
1
and every other disk,This
changes the parity of the number of inversions 34 times,which leaves an even num-
ber of inversions,
Similarly,rotating one position counterclockwise reverses the order of 34 pairs,
again leaving an even number of inversions,
By induction,the number of inversions is always even,Therefore,the con?guration in
which 1 and 2 are swapped (which has 1 inversion) is unreachable,
Problem 3,A regular 52-card deck is arranged as follows,
A? 2,.,K? A? 2?,.,K? A? 2?,.,K? A? 2?,.,K?
In a perfect shuf?e,the deck is?rst divided into two piles,one containing the top 26 cards
and the other the bottom 26,These two piles are then recombined into a single deck by
perfectly interlacing them,
This interlacing process can be done in two different ways since the new top card could
come from the top of either 26-card pile,So over a sequence of perfect shuf?es,many
different arrangements of the deck can be obtained,Prove that no sequence of perfect
shuf?es puts the deck in the following order,
A? 2?,.,K? A? 2?,.,K? A? 2?,.,K? A? 2?,.,K?
Solution,We use induction,De?ne the cards in the i-th and (52? i)-th positions in
the deck to be opposites,Thus,for example,the top card is opposite the bottom card,the
second card is opposite the next to last card,and the two cards in the middle of the deck
4 Problem Set 3
are opposite each other,Let P(n) be the proposition that opposite cards are the same
color,
Base case,In the initial con?guration,hearts are opposite diamonds and clubs are opposite
spades,Therefore,all opposite cards are the same color,
Inductive step,Suppose that all opposite cards are the same color,Consider an arbitrary
con?guration of the deck,
c
1
c
2
c
3
.,, c
52
A perfect shuf?e leaves the deck in one of the following orders,
c
1
c
27
c
2
c
28
c
3
c
29
.,, c
25
c
51
c
26
c
52
c
27
c
1
c
28
c
2
c
29
c
3
.,, c
51
c
25
c
52
c
26
In both cases,exactly the same cards remain opposites,c
1
and c
52
,c
2
and c
51
,etc,So,in
particular,opposite cards are still the same color,
By induction,opposite cards are always the same color,Therefore,the hearts,clubs,
diamonds,spades con?guration is unreachable since there all opposite cards are different
colors,
Problem 4,Prove the following basic facts about greatest common divisors,
(a) gcd(ka,kb) = k · gcd(a,b) for all k > 0.
Solution,The smallest positive value of
s · (ka) + t · (kb) = k a + t b)· (s · ·
over all s,t ∈ Z is k times the smallest positive value of
s a + t b· ·
over all s,t ∈ Z,The?rst quantity is gcd(ka,kb) and the second is gcd(a,b),There-
fore,gcd(ka,kb) = kgcd(a,b),
(b) gcd(a,b) = gcd(a + kb,b) for all k ∈ Z,
Solution,We show that every linear combination of a and b is a linear combination
of a + kb and b and vice-versa,
If x = s a + t b,then x = s
· (a + kb) + t
b where s
= s and t
= t? s
k.· · ·
If x = s
· (a + kb) + t
b,then x = s a + t b where s = s
and t = t
+ s
k.· · ·
Thus,in particular,the smallest positive linear combinations are equal,so gcd(a,b) =
gcd(a + kb,b),
5 Problem Set 3
Problem 5,Here is a long run of composite numbers,
114,115,116,117,118,119,120,121,122,123,124,125,126
Prove that there exist arbitrarily long runs of composite numbers,Consider numbers a
little bigger than n! where n! = n·(n?1) 3 2 1.··· · ·
Solution,Let k be some natural number such that 1 < k ≤ n,We know k (n! + k)|
because k | n! and k k,Thus,the numbers n!+2,n!+3,n!+4,...,n!+n are all composite,|
This is a run of n?1 consecutive composite numbers,Because we can choose n arbitrarily,
we know arbitrarily long runs of composite numbers exist,
Problem 6,Here is a very,very fun game,Initially,there is a blackboard with the numbers
1309 and 1729 written on it,Now you and I take turns; you go?rst,On each player’s
turn,he or she must write a new positive integer on the board that is the difference of two
numbers that are already there,The?rst person who can not create a new number loses
the game,
For example,your?rst move must be 1729? 1309 = 420,Then I could play either
1309?420 = 889 or 1729?420 = 1309,and so forth,
(a) Prove every number written on the board is a multiple of 7 less than or equal to
1729,
Solution,We use induction,Let P(n) be the proposition that after n moves,every
number on the board is a positive linear combination of 1729 and 1390,
Base case,P(0) is true because 1729 and 1390 are trivial linear combinations of 1729
and 1390,
Inductive step,Assume that after n moves,every number on the board is a positive
linear combination of 1729 and 1390,The next number written on the board is also
a positive linear combination,because,
The rules require the number to be positive,
The new number must be a difference of two numbers already on the board,
which are themselves linear combinations of 1729 and 1390 by assumption,
And a difference of linear combinations is another linear combination,
By induction,every number on the board is a positive linear combination of 1729
and 1390,And every positive linear combination of 1729 and 1390 is a multiple of
gcd(1729,1390) = 7,
(b) Prove that every positive multiple of 7 less than or equal to 1729 is on the board
at the end of the game,
Solution,Let x be the smallest number on the board at the end of the game,By
the Division Algorithm,there exist integers q and r such that 1729 = q ·x + r where
6 Problem Set 3
0 ≤ r < x,When no more moves are possible,1729? x must already be on the
board,and thus so must 1729? 2x,.,, 1729? (q? 1)x,However,1729? qx = r can
not be on the board,since r < x and x is de?ned to be the smallest number there,
The only explanation is that r = 0,which implies that x | 1729,By a symmmetric
argument,x | 1390,Therefore,x is a common divisor of x and y,The only common
divisors of 1729 and 1390 are 1 and 7,and x can not be 1 by the preceding problem
part,Therefore,7 is on the board at the end of the game,Since no more moves are
possible,1729? 7,1729? 2 7,.,,,7,0 must all be on the board as well,So every ·
positive multiple of of 7 less than or equal to 1729 is on the board at the end of the
game,
(c) Who wins?
Solution,There are 1729/7 = 247 numbers on the board at the end of the game,
Thus,there were 247? 2 = 245 moves,Since you go?rst,you also get the last move
and win the game,
Problem 7,Prove the following theorem,
Theorem,If gcd(a,b) = 1,then gcd(a + b,a? b) = 1 or 2,
Solution,Since gcd(a,b) = 1,there exist integers s and t such that,
s· a + t· b = 1
Now there is a linear combination of a + b and a? b equal to 2,
(s + t)· (a + b) + (s? t)· (a? b) = 2(s· a + t· b) = 2
Thus gcd(a + b,a? b) is at most 2,which implies it is equal to 1 or 2,
