Problem of the Week Fall 2018

Submit electronic solutions to

Glory and prizes could be yours!

November 19

Hat Problems

Problem Background:

A team of n people are each fitted with a hat which is either RED or BLUE. They can see other people’s hats, but not their own. The team wants to guarantee as many people as possible correctly guess the color of their own hat. They can discuss strategy beforehand, but once the hats are assigned, they can’t communicate (other than hearing each other’s guesses). The person putting the hats on them can listen in to their strategy, and will assign hats in the way that thwarts them as much as possible (maximizing wrong guesses.)

In both problems, the challenge is to find a strategy that maximizes the guaranteed correct number of announcements, and determine how many (in terms of n) are guaranteed under that strategy.

Problem 1:

The team members are all put in a line — each can only see the hats on the people in front of them in the line. The person at the end of the line (who can see everyone else’s hat) guesses first, then the next-to-last, and so on until the person in the front (who can see no hats) announces.

Problem 2:

The team members are all in a circle and everyone can see the others’ hats. But they all have to announce at the same time, so they can’t hear anyone else’s before they make their own announcement.

email your solution to before Monday Dec. 3

October 29

Problem: How Many Hand Shakes?

Chris and Pat go to a dinner party with four other couples; each person there shakes hands with everyone he or she doesn't know. Later, Chris does a survey and discovers that every one of the nine other attendees shook hands with a different number of people.

How many people did Pat shake hands with?

email your solution to before Monday Nov. 5

October 22

Problem: Four Ghostly Galleons

Four ghostly galleons – call them E, F, G and H, – sail at night on a ghostly sea so foggy that one side of a ship cannot be seen from the other. Each ship pursues its course steadily, changing neither its speed nor heading. G collides with H amidships; but since they are ghostly galleons they pass through each other with no damage nor change in course. As they part, H’s captain hears G’s say “Tarnation! That’s our third collision this night!” A little while later, F runs into H amidships with the same effect (none) and H’s captain hears the same outburst from F’s. What should H’s captain do to reach her original destination, whatever it may be, with no further collision; and why will doing so succeed?

email your solution to before Monday Oct. 29

October 15

Problem: Goblins

Some Goblins, N in number, are standing in a row while trick-or-treating. Each goblin is at all times either 2' tall or 3' tall, but can change from one height to the other at will. While lined up in such a row, a goblin is called a Local Giant Goblin (LGG) if they are not standing beside a taller goblin. Let G(N) be the total of all occurrences of LGG's as the row of N goblins transmogrifies through all possible height configurations. As an example, with N = 2, the distinct configurations are 2^2^, 23^, 3^2, 3^3^, where a hat (^ to the right of a number) indicates an LGG. Thus G(2) = 6.

(i) Find G(3) and G(4).

(ii) Find, with proof, the general formula for G(N), N = 1, 2, 3, ...

email your solution to before Monday Oct. 15

October 8

Problem: Red and Blue Points

Given n red points and n blue points on the plane, with no three points on a line, prove that there is a matching between red and blue points so that the line segments from each red point to its corresponding blue point do not cross.

email your solution to before Monday Oct. 15

October 1

Problem: Commuting Matrices

Let A, B, P, Q, X, Y be square matrices of the same size. Suppose that:

            A + B + AB = XY                AX = XQ

            P + Q + PQ = YX                PY = YB.

Prove that AB = BA.

email your solution to before Monday Oct. 8

September 24

Problem: Airplane Passengers

One hundred people line up to board an airplane - it's a fully booked flight, and the seats are assigned. But the first person to board, instead of sitting in their assigned seat, takes a random seat instead. Each subsequent passenger takes their assigned seat if available. otherwise a random unoccupied seat.

Finally, the last passenger to board gets on the plane and sits in the last remaining available seat. What is the probability that the last available seat is in fact their assigned seat?

email your solution to before Monday Oct. 1

September 17

Problem: Containing Differences

Let S be a finite set of non-negative integers such that  |x − y| ∈ S whenever x, y ∈ S.

1.   Give an example of such a set which contains ten elements.

2.   If A is a subset of S containing more than two-thirds of the elements of S, prove or disprove that every element of S is the sum or difference of two elements from A.

email your solution to before Monday Sept. 24

September 10

Problem: Overdesigned Clock

I have an exactly accurate clock whose hour hand and minute hand are the same length. In a twelve hour period, how many times is the time on the clock ambiguous?

The two hands are identical (except for the rate they go around) and indistinguishable. We're looking for precisely ambiguous times: if you switch the hour and minute hand, you get another time. An example of an unambiguous time is 6 o'clock (minute hand at 12, hour hand at 6); if the minute hand is pointing to the 6 (on a half hour), the hour hand will be halfway between two numbers - it couldn't be pointing at the 12.

email your solution to before Monday Sept. 17