Feeds:
Posts

## Problems and Solutions from Roberto Bosch Cabrera

Our first speaker of the semester, Roberto Bosch Cabrera, has generously provided us with a set of problems and solutions.  The concepts behind these problems should be very helpful to our students preparing for the next set of AMC contests.  In addition, the art of writing excellent articulations like Roberto’s is critical to advancement in mathematics and is applicable to a variety of other fields.

Here are the first two problems and the solutions which you will find in the attached Adobe Acrobat File (pdf).

## January 21, 2012 – Roberto Bosch Cabrera – “Equations and System of Equations via Inequalities””

The Metroplex Math Circle begins its Spring semester with a lecture and some beautiful problems presented by Roberto Bosch Cabrera!  For example:

This lecture will focus on three well known inequalities:

1. x^2>=0
2. AM – GM
3. Cauchy – Schwarz

## UT Dallas Computer Scientists Make Progress on Math Puzzle

I thought this recent article was a great demonstration that the creativity, diligence and playfulness that are encouraged in Math Circle can also be a part of a rewarding career.

#### UT Dallas Team’s Approach to an Old Problem is Praised as ‘Elegant’

Oct. 28, 2010

Two UT Dallas computer scientists have made progress on a nearly 4-decade-old mathematical puzzle, producing a proof that renowned Stanford computer scientist Don Knuth called “amazing” in his communication back to them.

Created by the mathematician John Conway and known as Topswops, the puzzle starts like this: Begin with a randomly ordered deck of cards numbered 1 to n, with n being however high a number you choose. Now count out the number of cards represented by whatever card is the top card, and turn that block of card

s over on top of the remaining cards. Then count out the number of cards represented by the new top card and turn this whole block over on top of the remaining cards. Repeat until the card numbered 1 comes to the top (realizing that we know the card numbered 1 will always eventually come to the top).

Now here’s what needs to be done: Calculate the maximum and minimum number of steps required with n number of cards.

Knuth had previously proved an exponential upper bound on the number of Topswops steps, and conjectured that one might also prove a matching lower bound. What Dr. Hal Sudborough and Dr. Linda Morales did, however, was to prove a lower bound that is much better than that proposed in Knuth’s conjecture, and Knuth declared their proof technique both “elegant” and “amazing.”

“What I find fascinating about a problem such as bounding the Topswops function is connected to its simplicity, to its fundamental nature, and to the complexity and difficulty of finding an answer,” said Sudborough, the Founders Professor at the Erik Jonsson School of Engineering and Computer Science. “An easily described, easily communicated problem is invaluable for engaging a wide array of participants, from high school students to the most eminent mathematicians.”

He also cited Martin Gardner, a longtime columnist for Scientific American, who wrote of problems such as Topswops, “Let it not be supposed that those Conway card games are trivial. They deal with the theory of set permutations and not only may provide deep theorems but also may have a bearing on practical problems that arise in seemingly unrelated fields.”

And then there’s the sheer mathematical beauty that the problem reveals.

“The Topswops process is a simple one,” said Morales, a senior lecturer in computer science. “The basic algorithm is easily understood by almost anyone, regardless of their training or interests. But the simplicity is deceptive. Hiding behind it is a mathematical world of unexpected richness and beauty. Our research uncovered permutations whose iterate sequences have a fascinating structure, which upon analysis have revealed hitherto unknown lower bounds for the problem. There is much more to learn from the problem. We have tantalizing hints of more revelations just waiting to be uncovered.”

## AMC 8 Preparation Problem #2

The 16 squares on a piece of paper are numbered as shown in the diagram.  While lying on a table, the paper is folded four times in the following sequence.

1. Fold the top half over the bottom half
2. Fold the bottom half over the top half
3. Fold the right half over the left half
4. Fold the left half over the right half

Which numbered sequence is on top after step 4?

A) 1       B)9      C)10    D)14    E)16

## MC^2 Problem Sets

For those of you who haven’t been fortunate enough to get out to Arlington to visit the Mid-Cities Math Circle,  Dr. Grantcharov has posted the problem sets from his last 3 sessions.

You can find previous session hand out on the Mid Cities Math Circle’s Schedule Page.

## Telescoping Sums and Products (Example 2)

This time I will provide both the problem and solution in  the continuing series from Dr. Andreescu’s lecture on Telescoping Sums and Products.

### Example 2.  Evaluate

$\displaystyle\sum^{n}_{k=2}k!(k^2+k+1)$

### Example 2.  Solution

We can write

$\displaystyle\sum^{n}_{k=1}k!(k^2+k+1)=\displaystyle\sum^{n}_{k=1}[(k+1)^2-k)]k!$

$=\displaystyle\sum^{n}_{k=1}[(k+1)!(k+1)-k!k]$

$=(n+1)!(n+1)-1$

## Telescoping Sums and Products (Solutions 1)

Here is the solution provided for this previous problem on Telescoping Sums and Products

### Example 1.  Prove that

$\displaystyle\sum^{n}_{k=1}k^4=\dfrac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$

### Example 1.  Solution

From the Binomial Theorem we have

$\displaystyle(k+1)^5-k^5=5k^4+10k^3+10k^2+5k+1$

thus

$\displaystyle\sum^{n}_{k=1}[(k+1)^5-k^5]=(n+1)^5-1$

It follows that

$\displaystyle 5\sum^{n}_{k=1}k^4+10 \sum^{n}_{k=1}k^3+10 \sum^{n}_{k=1}k^2+5 \sum^{n}_{k=1}k+\sum^{n}_{k=1}1=(n+1)^5-1$

Hence

$\displaystyle5 \sum^{n}_{k=1}k^4=(n+1)^5-10\dfrac{n(n+1)(2n+1)}{6}-5\dfrac{n(n+1)}{6}-(n+1)$

Yielding

$\displaystyle\sum^{n}_{k=1}k^4=\dfrac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$