Department of Computer Science

Past Problems

Problem Number 21

December 10, 2003

Two integers are selected at random between 2 and 999. What is the probability that their only common divisor is 1?

Problem Number 20

November 14, 2003

Winner: Peter Kronfeld

Correct solutions were also submitted by:

• George Damyanov
• Troy Mestler
• David Krisch
• Ann Nguyen

A necklace consists of pearls which increase uniformly from a weight of one carat for the end pearls to a weight of 100 carats for the middle pearl. If the necklace weighs altogether 1650 carats and the clasp and string together weigh as much (in carats) as the number of pearls, how many pearls does the necklace contain?

Problem Number 19

October 22, 2003

Winner: Troy Mestler Physics major

Consider the following algorithm:

Start with the fraction 1/1 for the first generation and make two fractions from it by replacing either the numerator or the denominator by the sum of the numerator and denominator. Thus at generation two we have 2/1 and 1/2. Proceed in this fashion, getting 3/1 and 2/3 from 2/1 and getting 3/2 and 1/3 from 1/2 for generation three.

Show that this algorithm generates every positive rational number exactly once and in lowest terms.

Problem Number 18

October 1, 2003

Winner: Troy Mestler Physics major

Consider an acute angle theta () made by two rays A and B meeting at vertex O. Assume that the rays A and B act as mirrors and consider a ray of light starting at some point P in the interior of the angle and moving along a line L that does not pass through O. Show that the number of reflections the light has with sides A and B is finite.

Problem Number 17

May 5, 2003

There is a queue of n+m persons at a theatre box office. Admission is $5. Each of the n people in line have exactly one $5 bill. The other m have exactly one $10 bill. The ticket seller has no change to begin with. What is the probability that the ticket taker will have enough change for everyone as they buy their ticket, i.e. without having to wait past their turn?

Problem Number 16

April 25, 2003

Winner: Adam Urpsis

An island contains cats, birds and snakes. Each day each cat eats a bird for breakfast, each snake has a cat for lunch and each bird has a snake for supper. There are no births or deaths except at these meals.

At a certain time on the n-th day of the month, a bird becomes the only living creature left on the island. What time of day did this happen (i.e. at what meal)? Find an expression (or write a program) to evaluate the number of birds before breakfast on the first day of the month in terms of n.

Problem Number 15

March 28, 2003

No correct solutions were submitted.

As we were all taught at our mother's knee, the harmonic series

1/1 + 1/2 + 1/3 + 1/4 + .... + 1/n + ....

diverges. Throw out all the terms that have a 9 in them, like 1/9, 1/29, 1/911, 1/9923 etc.

Show that the resulting series converges, and the sum is less than 80.

Problem Number 14

March 7, 2003

Winner:

• Fred Strack

Prove that the square of every prime number greater than 3 yields a remainder of 1 when divided by 12.
Hint: Look at the possible remainders when a prime is divided by 6.

Problem Number 13

February 7, 2003

Winner:

• John Manor

Suppose that Norm and Cliff (from Cheers) enter a football pool with Pete Rose. They each put $10 into the pool and then choose the winners of each of ten football games. The player with the largest number of correctly chosen winning teams wins the $30 pool. In the case of a tie, the pool is split.

Assume at first that all three players' choices for each game are randomly determined, and that the actual winner of each game is also randomly determined (say by the flip of a fair coin). If each player chooses his teams independently, then each player wins, on average, $10 (i.e. they get their money back). This can be seen without doing any calculation, on the general principle that the situation is symmetric: All 3 players have the same strategy and nobody has an advantage, so the expected outcomes are the same.

But Norm and Cliff have come up with a scheme to beat Pete, namely, the Evil Twin Strategy:

Cliff (randomly) determines who he thinks will win each game, and Norm chooses the opposite team for each game. Thus if Cliff picks a game incorrectly, then his pal Norm has it right. (Pete is still picking independently and randomly.) Therefore the Cliff-Norm Axis of Evil Twins has at least one of them with at least 5 correct picks. If they split their winnings, how much will they each expect to win on average?

webmaster@cs.sdsu.edu

College of Sciences