### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for MATH 294A with Professor Savitt at UA

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 2 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 17 views.

## Reviews for Class Note for MATH 294A with Professor Savitt at UA

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Induction Ksenija Simic Muller and Matt Ondrus Feb 287 2007 Example 1 Every positive integer n can be expressed as n 00 0121 0222 CM2M for some M 2 07 where 01 E 01 for all 239 Example 2 Note This is an example of a wrong proof Suppose that S Z21 7 Z is a function with the property that Sn 557171 7 6Sn 7 27 where 51 9 and 52 20 Prove that Sn 3 2 3 Example 3 Suppose you are given a square checkerboard with side length 2 and with one missing square Prove that the remaining squares on the board can be tiled with trominos Note that a tromino is an object shaped like Problem 1 A winning con guration in the game of MiniTetris is a complete tiling of a 2 gtlt 71 board using only the three shapes shown below g Prove that the number of winning con gurations on a 2 gtlt n MiniTetris board 71 2 1 is Tn 2m1 1 3 Problem 2 We are given a chocolate bar with m gtlt 71 squares of chocolate7 and our task is to divide it into mn individual squares We are only allowed to split one piece of chocolate at a time using a vertical or a horizontal break For example7 suppose that the chocolate bar is 2 gtlt 2 The rst split makes two pieces7 both 2 gtlt 1 Each of these pieces requires one more split to form single squares This gives a total of three splits Use strong induction to conclude the following Theorem To divide up a chocolate bar with m gtlt n squares7 we need mm 7 1 splits Problem 3 You begin with a stack of 71 boxes Then you make a sequence of moves In each move7 you divide one stack of boxes into two nonempty stacks The game ends when you have n stacks7 each containing a single box You earn points for each move in particular7 if you divide one stack of height a b into two stacks with heights 1 and b7 then you score ab points for that move Your overall score is the sum of the points that you earn for each move What strategy should you use to maximize your total score Problem 4 Prove that consecutive Fibonacci numbers are always relatively prime Problem 5 Show that every positive integer can be expressed uniquely as the sum of distinct7 non consecutive Fibonacci numbers here7 non consecutive means that no two of the Fibonacci numbers in the sum are consecutive Fibonacci numbers Problem 6 Let n 2k Prove that we can select 71 integers from any 271 7 1 integers such that their sum is divisible by 71 Problem 7 Prove that if you triangulate a convex n gon7 then there are at least two vertices of degree two Note Think of a convex n gon as a graph consisting of n vertices and n edges arranged in a cycle To triangulate an n gon is to join non adjacent vertices with edges in such a way that no edges cross each other and all of the resulting faces are triangles Problem 8 Let Sn denote the number of strings of length 71 built from the alphabet H7 T that do not contain the substring HH Prove that 53 S 1 Sn 54 17 SM 10gtlt 2 H 10gtlt 2 i Problem 9 Prove that the faces of a planar graph can be colored with two colors so that no two adjacent faces are the same color iff all of its vertices have even degree Problem 10 In an m gtlt 71 matrix of real numbers7 we mark at least p ofthe largest numbers 10 S m in every column7 and at least q of the largest numbers 1 S n in every row Prove that at least pq numbers are marked twice Problem 11 Putnam7 1972 Show that7 for all n gt 17 71 does not divide 2 7 1 Problem 12 There are no positive integer solutions of x4 14 22 Hint You need to know that every positive integer solution of a2 b2 02 where a7b7 and c are relatively prime can be expressed in terms of two relatively prime numbers m7 and n where a m2 7 7127 b 277m7 and c m2 712

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.