Problem Solving Group

This was the first meeting of PSG over the summer of 2011. People around this summer include: Lucas Van Meter, Bill Huber, Kirsten Baer, Paul Gallahger, Mitchell Johnston, Chang Cao, and Nuzhat Arif.

At this meeting we discussed three problems, listed below:

1.  Let (a[n]), n = 0, 1, 2, …,  be an infinite sequence of positive integers such that gcd(a[n+1], a[n]) > a[n-1] for all n >= 1.  Prove that a[n] >= 2^n for n >= 1.  (I haven’t thought about this or checked it, so some adjustment of the index  n  might be needed for the result to be true.)

2.  The functional equation f(2p-1)/2 = f(Sqrt(p)) – constant, 0 < p < 1, is satisfied by Arcsine.  What is a “minimal” additional set of conditions (such as continuity, antisymmetry, differentiability, slope at 0, whatever) needed to make this uniquely characterize Arcsine?

We assume that the wheel has thin spokes connecting the circular rim radially towards a hub at the center. (Some performance wheels are actually built this way.)  The wheel is assumed to roll in a plane parallel to the plane of the film; the camera does not pan. The shutter speed is assumed to be slow enough so that there is some blurring, but fast enough so that some parts of some spokes are without visible blur. The problem is to determine which parts of which spokes will be the most clearly imaged.
What generalizations and assumptions are needed to make this question more realistic?  (It would be nice to make an empirical test of our solution!)

Here is a summation of our discussion on the first problem written by lucas. It is not complete yet but maybe lucas will finish it later. PSG 6-2-11

We talked about the bicycle problem but did not write up any math analysis of the problem. Anyone care to comment on it?

We made a lot of work on the functional equation. Some of that can be seen in the photos.

Lastly we have some photos that we took during the meeting.

It’s a new year! Here are some nice problems to celebrate.

Holiday problems

In addition to these problems found by Bill I have two computer science questions that I heard over break.

1) Suppose you have two identical glass orbs and are confronted with a hundred story building. Your task is to find out the lowest floor that these orbs break at when you drop them. To do this you have only one method, experimentation. One step consists of dropping an orb out of a window and observing if it shatters or not. If an orb shatters you may not use it for further experimentation. So for example if I drop a ball from the 50th floor and it breaks and then drop my second ball the the 25th floor and it breaks I lose because I have no way of knowing the lowest floor it would break from. The question is: what is the fewest number of step you need in order to guarantee you have determined the answer. In other words, minimize the worst case scenario of an algorithm that finds the answer. After you have done this generalize to n orbs and an x story building.

2) You have a finite directed connected graph such that each node has at most one edge leading out from it. Each node is labeled randomly. If one were to pick a node and continue along to the next node repeatedly this graph would either terminate or fall into a loop. Our task is to determine if there is a loop in a given graph and if so what length the loop is. The only information we can keep in our tiny little computer heads however is the number of steps we have taken (more on that soon) and the name of two nodes and their succeeding nodes respectively. We have the ability to assign a new random node or a node we currently know the name of to these two memory slots. For example we could start with a random node A in one slot. If A has the successor B then we could assign B to our second memory slot. Alternatively we could have assigned our second memory slot to a new random node Alpha with successor Beta. Each assignment of of a new node to a memory slot counts as a step. What is the most efficient algorithm to determine if the graph has a loop and if so what length the loop is? (remember that your algorithm has to halt even if there is no loop).

I hope these two problems were stated without too much confusion.

Enjoy and lets see how many of these we can solve!

Lynne Butler writes:

Nineteen Haverford students took either Part A or Part B of the Putnam Exam last Saturday. Seventeen took both parts. This year, problem A1 really was easy, so everyone got at least one problem! (Take a peek; the problems are posted on a bulletin board outside my office.)

Thanks to Bill Huber for encouraging students to make problem-solving part of their recreational life at Haverford, to Jeff for giving an extension on a take-home to students in Math 215 who took the Putnam, and to Putnam fellow Marshall Buck who talked with two group of students (totaling 7 individuals) who travelled to NJ to practice with him.

Click here for this year’s exam.

Students: discuss the problems and their solutions by responding to this post! You can also post your solutions to the bulletin board outside Lynne’s office, KINSC H212.