## Canada/USA MathCamp Qualifying Quiz

Go back to the Math Jam Archive
**Copyright © 2017 AoPS Incorporated. This page is copyrighted
material. You can view and print this page for your own use, but you cannot
share the contents of this file with others.**

#### Facilitator: Dan Zaharopol

DanZ
2010-06-15 19:31:48

Hello everyone! Welcome to the Math Jam for the 2010 Mathcamp Qualifying Quiz.

Hello everyone! Welcome to the Math Jam for the 2010 Mathcamp Qualifying Quiz.

DanZ
2010-06-15 19:31:56

My name is Dan. I'm an instructor at camp (and also an instructor here at AoPS), and I'll be there this summer. I also helped to grade this year's quiz and make admissions decisions.

My name is Dan. I'm an instructor at camp (and also an instructor here at AoPS), and I'll be there this summer. I also helped to grade this year's quiz and make admissions decisions.

DanZ
2010-06-15 19:32:06

For those of you who aren't familiar with it, the Mathcamp Qualifying Quiz is an eight-question untimed set of problems which all applicants to Canada/USA Mathcamp must solve for admission. You don't need to solve all of the problems, but you need to make good progress! It's one of several factors that impacts your admission. I'm expecting that many of you were indeed applicants this year. To follow along, you should all have the quiz open in another window:

http://www.mathcamp.org/prospectiveapplicants/quiz/index.php

For those of you who aren't familiar with it, the Mathcamp Qualifying Quiz is an eight-question untimed set of problems which all applicants to Canada/USA Mathcamp must solve for admission. You don't need to solve all of the problems, but you need to make good progress! It's one of several factors that impacts your admission. I'm expecting that many of you were indeed applicants this year. To follow along, you should all have the quiz open in another window:

http://www.mathcamp.org/prospectiveapplicants/quiz/index.php

DanZ
2010-06-15 19:32:22

Additionally, if you did apply this year, I recommend having your solutions open. That way, you can reply more quickly to the questions I ask of the room. I like to have a very interactive session, so I'm expecting you all to pitch in to the solutions!

Additionally, if you did apply this year, I recommend having your solutions open. That way, you can reply more quickly to the questions I ask of the room. I like to have a very interactive session, so I'm expecting you all to pitch in to the solutions!

DanZ
2010-06-15 19:32:31

We are going to go through all eight problems on the quiz. I'm going to try to show you more than just fully correct answers: I also want to show you how

We are going to go through all eight problems on the quiz. I'm going to try to show you more than just fully correct answers: I also want to show you how

*you*could come up with those answers, and how to write them up in a way that really communicates the mathematics you're doing. I'll also address common mistakes on several of the problems and how to get around them.
DanZ
2010-06-15 19:32:52

This whole session is rather experimental --- we've never done anything like it before --- so I'd love to get your comments during or after the session on how it went and how useful it was (or wasn't).

This whole session is rather experimental --- we've never done anything like it before --- so I'd love to get your comments during or after the session on how it went and how useful it was (or wasn't).

DanZ
2010-06-15 19:33:00

We're going to start relatively slowly, but accelerate as we go along. The idea is for everyone to be able to follow at first, but be warned that things will get more and more difficult as we go on.

We're going to start relatively slowly, but accelerate as we go along. The idea is for everyone to be able to follow at first, but be warned that things will get more and more difficult as we go on.

DanZ
2010-06-15 19:33:09

Because there are a lot of questions, and because they do all take a lot of work, this isn't going to be a short Math Jam and so I want to jump right into things. But first: do you all have any general questions for me?

Because there are a lot of questions, and because they do all take a lot of work, this isn't going to be a short Math Jam and so I want to jump right into things. But first: do you all have any general questions for me?

DanZ
2010-06-15 19:33:25

(I reserve the right to punt your questions to the end of the session in the interest of time, though, so apologies in advance if I don't answer them.)

(I reserve the right to punt your questions to the end of the session in the interest of time, though, so apologies in advance if I don't answer them.)

DanZ
2010-06-15 19:33:36

Oh, also: this chat room is moderated. That means your messages go only to me, and I will choose which to pass on.

Oh, also: this chat room is moderated. That means your messages go only to me, and I will choose which to pass on.

DanZ
2010-06-15 19:33:40

So feel free to contribute to problems.

So feel free to contribute to problems.

sachiroo
2010-06-15 19:34:10

How do you choose the problems for the qual quiz?

How do you choose the problems for the qual quiz?

DanZ
2010-06-15 19:34:31

Former staff members get together to do it over e-mail, creating problems, modifying them, or using obscure sources you won't find on Google Books. :)

Former staff members get together to do it over e-mail, creating problems, modifying them, or using obscure sources you won't find on Google Books. :)

mathwiz172
2010-06-15 19:34:42

What was the average number of questions correct for campers this year?

What was the average number of questions correct for campers this year?

DanZ
2010-06-15 19:34:46

I have no idea, I'm afraid.

I have no idea, I'm afraid.

DanZ
2010-06-15 19:35:00

And it's not clear how much it matters: different problems were weighted differently in our minds.

And it's not clear how much it matters: different problems were weighted differently in our minds.

lvdrlvr55
2010-06-15 19:35:10

Is there a point system for grading?

Is there a point system for grading?

DanZ
2010-06-15 19:35:23

We do have one, but we fudge it a lot and go back over all quizzes near a boundary.

We do have one, but we fudge it a lot and go back over all quizzes near a boundary.

hcs
2010-06-15 19:35:39

Did the length of your solution(s) have an effect on grading?

Did the length of your solution(s) have an effect on grading?

DanZ
2010-06-15 19:35:45

No; it had to be complete, though.

No; it had to be complete, though.

gh625
2010-06-15 19:36:08

Did you give partial credit?

Did you give partial credit?

DanZ
2010-06-15 19:36:11

Yes, definitely.

Yes, definitely.

Great Spheres
2010-06-15 19:36:13

What if your solution weren't the most elegant one, would you not necessarily get full points?

What if your solution weren't the most elegant one, would you not necessarily get full points?

DanZ
2010-06-15 19:36:29

Let me put it this way: if someone showed great insight on a problem, we would prefer them over someone who only did the bare minimum to solve it.

Let me put it this way: if someone showed great insight on a problem, we would prefer them over someone who only did the bare minimum to solve it.

DanZ
2010-06-15 19:36:41

Ok, I think most of your other questions will be answered as we go along.

Ok, I think most of your other questions will be answered as we go along.

DanZ
2010-06-15 19:36:43

So let's get going!

So let's get going!

DanZ
2010-06-15 19:36:50

Problem 1: Towers of Hanoi

Problem 1: Towers of Hanoi

DanZ
2010-06-15 19:36:55

The first question is based on the classic "Towers of Hanoi" problem, so we should actually start off by discussing that. This problem is actually probably the easiest on the quiz, but it will also take us the longest to discuss, so my apologies if this drags a bit!

The first question is based on the classic "Towers of Hanoi" problem, so we should actually start off by discussing that. This problem is actually probably the easiest on the quiz, but it will also take us the longest to discuss, so my apologies if this drags a bit!

DanZ
2010-06-15 19:37:13

(For those of you who know this problem well, bear with me: I am starting so that everyone can follow, but we will be accelerating soon.)

(For those of you who know this problem well, bear with me: I am starting so that everyone can follow, but we will be accelerating soon.)

DanZ
2010-06-15 19:37:17

The Towers of Hanoi problem works as follows. There are three pegs, labeled A, B, and C. On peg A are n discs, going from the largest (on the bottom) to the smallest (on the top). Your goal is to move all of the pegs from A to C, but:

1. You are only allowed to move one disc at a time.

2. You can only move the disc that is at the top of any peg (i.e. you have to move the discs on top before you reach the discs on bottom).

3. You can only place a disc on a peg if the disc below it is larger.

The Towers of Hanoi problem works as follows. There are three pegs, labeled A, B, and C. On peg A are n discs, going from the largest (on the bottom) to the smallest (on the top). Your goal is to move all of the pegs from A to C, but:

1. You are only allowed to move one disc at a time.

2. You can only move the disc that is at the top of any peg (i.e. you have to move the discs on top before you reach the discs on bottom).

3. You can only place a disc on a peg if the disc below it is larger.

DanZ
2010-06-15 19:37:27

You can see a model at:

http://en.wikipedia.org/wiki/Tower_of_Hanoi

You can see a model at:

http://en.wikipedia.org/wiki/Tower_of_Hanoi

DanZ
2010-06-15 19:37:39

For example, it is illegal to take the top disc from peg A and move it to peg C, and then to move the next disc from peg A to peg C --- the top disc on peg A was the smallest, and so you've just put a bigger disc on top of a smaller disc, violating rule 3.

For example, it is illegal to take the top disc from peg A and move it to peg C, and then to move the next disc from peg A to peg C --- the top disc on peg A was the smallest, and so you've just put a bigger disc on top of a smaller disc, violating rule 3.

DanZ
2010-06-15 19:37:50

How many moves does it take to move all n discs from peg A to peg C?

How many moves does it take to move all n discs from peg A to peg C?

hcs
2010-06-15 19:39:05

according to wikipedia $2^n -1$

according to wikipedia $2^n -1$

DanZ
2010-06-15 19:39:08

DanZ
2010-06-15 19:39:18

Normally I'd want to lead you through this problem step-by-step, but it's easily online, so let me just summarize how it works, so we can use it to generalize to the Mathcamp quiz problem.

Normally I'd want to lead you through this problem step-by-step, but it's easily online, so let me just summarize how it works, so we can use it to generalize to the Mathcamp quiz problem.

DanZ
2010-06-15 19:39:27

DanZ
2010-06-15 19:39:35

Now let's go back to the problem, moving all of the discs from peg A to peg C. Note that moving the largest disc requires have all of the other discs on one peg, because otherwise you'd put the largest disc on top of a smaller disc. So in order to move the largest disc at all, you must first get all of the other discs to another peg, requiring U(n-1) moves.

Now let's go back to the problem, moving all of the discs from peg A to peg C. Note that moving the largest disc requires have all of the other discs on one peg, because otherwise you'd put the largest disc on top of a smaller disc. So in order to move the largest disc at all, you must first get all of the other discs to another peg, requiring U(n-1) moves.

DanZ
2010-06-15 19:39:47

In any solution, you must also at some point move the largest disc to peg C; that requires one move. Since moving the largest disc requires having all of the other discs on one peg, you must now move the other n-1 discs to peg C as well, requiring at least U(n-1) moves.

In any solution, you must also at some point move the largest disc to peg C; that requires one move. Since moving the largest disc requires having all of the other discs on one peg, you must now move the other n-1 discs to peg C as well, requiring at least U(n-1) moves.

DanZ
2010-06-15 19:40:07

DanZ
2010-06-15 19:40:34

gh625
2010-06-15 19:41:03

Induction

Induction

hcs
2010-06-15 19:41:03

induction

induction

Shortgeek
2010-06-15 19:41:03

induction? Or is there a cleverer way?

induction? Or is there a cleverer way?

DanielC
2010-06-15 19:41:03

induction

induction

MJStone
2010-06-15 19:41:03

And induction

And induction

kevin7
2010-06-15 19:41:03

Induction?

Induction?

Iamerror
2010-06-15 19:41:03

induction

induction

Arouet
2010-06-15 19:41:17

by induction

by induction

smartkid11235813
2010-06-15 19:41:17

induction

induction

math911
2010-06-15 19:41:17

Induction.

Induction.

DanZ
2010-06-15 19:41:18

In answer to Shortgeek: induction works; I will also show you a cleverer way.

In answer to Shortgeek: induction works; I will also show you a cleverer way.

DanZ
2010-06-15 19:41:24

DanZ
2010-06-15 19:41:36

DanZ
2010-06-15 19:42:00

For those who are interested in other ways of solving recurrences, this comment may be helpful (but is certainly not needed for the quiz):

For those who are interested in other ways of solving recurrences, this comment may be helpful (but is certainly not needed for the quiz):

hcs
2010-06-15 19:42:02

shortgeek: there are things like the master method

shortgeek: there are things like the master method

DanZ
2010-06-15 19:42:20

And now, at last, we are ready for the actual qualifying quiz problem. We start with part (a):

And now, at last, we are ready for the actual qualifying quiz problem. We start with part (a):

DanZ
2010-06-15 19:42:26

DanZ
2010-06-15 19:42:42

ziv
2010-06-15 19:43:41

S(n) = 3S(n - 1) + 2

S(n) = 3S(n - 1) + 2

MJStone
2010-06-15 19:43:41

You need a different sequence of moves. U(N) = 3U(N-1) + 2

You need a different sequence of moves. U(N) = 3U(N-1) + 2

kevin7
2010-06-15 19:43:41

To get the biggest ring to C, we need to get it through B first.

To get the biggest ring to C, we need to get it through B first.

L2gB
2010-06-15 19:43:41

S(n)=3^n-1

S(n)=3^n-1

Great Spheres
2010-06-15 19:43:41

You can't store the n-1 discs in a side-peg

You can't store the n-1 discs in a side-peg

hcs
2010-06-15 19:43:41

the number of moves it takes to solve for one disc

the number of moves it takes to solve for one disc

peefthepur1
2010-06-15 19:43:41

all the rings except the base ring move 3 times

all the rings except the base ring move 3 times

gh625
2010-06-15 19:43:41

S(n)=3S(n-1)+2

S(n)=3S(n-1)+2

DanielC
2010-06-15 19:43:41

S(n)= 3S(n-1) +2

S(n)= 3S(n-1) +2

professordad
2010-06-15 19:43:41

add the number of moves from A to C needed

add the number of moves from A to C needed

Great Spheres
2010-06-15 19:43:41

So you have to move them to C in order to get the largest to B, then back to A, and then move the largest disc to C.

So you have to move them to C in order to get the largest to B, then back to A, and then move the largest disc to C.

.cpp
2010-06-15 19:43:41

You can't move a peg from A to C in one move.

You can't move a peg from A to C in one move.

DanZ
2010-06-15 19:43:49

Ah! Well, now, consider what needs to happen if we are going to move the largest disc, which starts on peg A. We must get all of the other discs off of A and onto C, to make room for this largest disc on peg B. How many moves does that require?

Ah! Well, now, consider what needs to happen if we are going to move the largest disc, which starts on peg A. We must get all of the other discs off of A and onto C, to make room for this largest disc on peg B. How many moves does that require?

MJStone
2010-06-15 19:44:41

U(N-1)

U(N-1)

Shortgeek
2010-06-15 19:44:41

S(n-1)

S(n-1)

smartkid11235813
2010-06-15 19:44:41

S(n-1)

S(n-1)

Arouet
2010-06-15 19:44:41

s(n-1)

s(n-1)

gh625
2010-06-15 19:44:41

S(n-1)

S(n-1)

DanielC
2010-06-15 19:44:41

S(n-1)

S(n-1)

ziv
2010-06-15 19:44:41

Move top $n-1$ discs from A to C ($S(n-1) moves)

Move top $n-1$ discs from A to C ($S(n-1) moves)

kevin7
2010-06-15 19:44:41

s(n-1) moves.

s(n-1) moves.

DanZ
2010-06-15 19:44:45

DanZ
2010-06-15 19:45:00

DanZ
2010-06-15 19:45:04

Now we move the largest disc to peg C, at last. And then what?

Now we move the largest disc to peg C, at last. And then what?

Shortgeek
2010-06-15 19:45:41

move them all on, for a final S(n-1)

move them all on, for a final S(n-1)

MJStone
2010-06-15 19:45:41

Another S(n-1) to move the others onto C.

Another S(n-1) to move the others onto C.

L2gB
2010-06-15 19:45:41

move them back again

move them back again

vwu9
2010-06-15 19:45:41

we need another S(n-1) moves

we need another S(n-1) moves

Great Spheres
2010-06-15 19:45:41

All the rest of the n-1 discs back to C

All the rest of the n-1 discs back to C

smartkid11235813
2010-06-15 19:45:41

Move n-1 stack back from A to C

Move n-1 stack back from A to C

Arouet
2010-06-15 19:45:41

move all the rest to c

move all the rest to c

gh625
2010-06-15 19:45:41

Move the rest of the discs back to peg C.

Move the rest of the discs back to peg C.

peefthepur1
2010-06-15 19:45:41

S(n-1) again

S(n-1) again

abhinand
2010-06-15 19:45:48

then do S(n-1) again

then do S(n-1) again

PurpleEnigma
2010-06-15 19:45:48

Move the n-1 disks back to peg C

Move the n-1 disks back to peg C

Iamerror
2010-06-15 19:45:48

we need another S(n-1) moves to get the other on top of it

we need another S(n-1) moves to get the other on top of it

hcs
2010-06-15 19:45:48

the same thing we do every night, pinky. move the rest of the discs over!

the same thing we do every night, pinky. move the rest of the discs over!

DanZ
2010-06-15 19:45:53

Great Spheres
2010-06-15 19:46:48

So that's in total 3S(n-1)+2

So that's in total 3S(n-1)+2

L2gB
2010-06-15 19:46:48

so (S(n-1))3+2?

so (S(n-1))3+2?

PurpleEnigma
2010-06-15 19:46:48

3S(n-1)+2

3S(n-1)+2

gh625
2010-06-15 19:46:48

S(n)=3S(n-1)+2

S(n)=3S(n-1)+2

DanielC
2010-06-15 19:46:48

3s(n-1)+2

3s(n-1)+2

Iamerror
2010-06-15 19:46:48

3S(n-1)+2

3S(n-1)+2

kevin7
2010-06-15 19:46:48

3s(n-1) + 2

3s(n-1) + 2

Arouet
2010-06-15 19:46:48

3S(n-1)+2

3S(n-1)+2

avec_une_h
2010-06-15 19:46:48

3S(n-1) + 2

3S(n-1) + 2

smartkid11235813
2010-06-15 19:46:48

3S(n-1)+2

3S(n-1)+2

ziv
2010-06-15 19:46:48

.cpp
2010-06-15 19:46:48

esly8
2010-06-15 19:46:48

S(n)=3S(n-1)+2

S(n)=3S(n-1)+2

DanZ
2010-06-15 19:46:57

DanZ
2010-06-15 19:47:04

Now, there are actually two pieces to writing that "=" sign up there. The first is that we know that we can do it in at most 3S(n - 1) + 2 moves --- we came up with a pattern that lets us do it. We also need to show that it actually takes that many moves; maybe there's a clever way to do it faster!

Now, there are actually two pieces to writing that "=" sign up there. The first is that we know that we can do it in at most 3S(n - 1) + 2 moves --- we came up with a pattern that lets us do it. We also need to show that it actually takes that many moves; maybe there's a clever way to do it faster!

DanZ
2010-06-15 19:47:09

Fortunately, there isn't. Here's why:

1. In order to move all n discs to peg C, you must first move the largest disc to peg B. That requires moving the other n-1 discs to peg C, requiring at least S(n-1) moves since S(n) is defined as the least number of moves required to move n discs from peg A to peg C, plus one move to actually move the largest disc.

2. Now, at some point, you must move the largest disc from peg B to peg C. That again requires having all of the other n-1 discs on peg A, so they must get moved over in your process, again requiring at least S(n-1) moves plus the one move to move the largest disc over.

3. And now the n-1 discs must find their way from peg A to peg C. Even if you have some ultra-fancy way of doing this, it must require at least S(n-1) moves by the definition of S(n). (If your ultra-fancy way involves moving the largest disc again, we can ignore those moves because they don't change anything.)

Fortunately, there isn't. Here's why:

1. In order to move all n discs to peg C, you must first move the largest disc to peg B. That requires moving the other n-1 discs to peg C, requiring at least S(n-1) moves since S(n) is defined as the least number of moves required to move n discs from peg A to peg C, plus one move to actually move the largest disc.

2. Now, at some point, you must move the largest disc from peg B to peg C. That again requires having all of the other n-1 discs on peg A, so they must get moved over in your process, again requiring at least S(n-1) moves plus the one move to move the largest disc over.

3. And now the n-1 discs must find their way from peg A to peg C. Even if you have some ultra-fancy way of doing this, it must require at least S(n-1) moves by the definition of S(n). (If your ultra-fancy way involves moving the largest disc again, we can ignore those moves because they don't change anything.)

DanZ
2010-06-15 19:47:36

DanZ
2010-06-15 19:47:46

So, suppose that you'd just derived this relationship. What would you do now?

So, suppose that you'd just derived this relationship. What would you do now?

DanZ
2010-06-15 19:47:51

If you were solving this for the first time?

If you were solving this for the first time?

Great Spheres
2010-06-15 19:48:31

Get S(1)

Get S(1)

gh625
2010-06-15 19:48:31

Write out a few terms

Write out a few terms

Titandrake
2010-06-15 19:48:31

List values for n = 1,2,3, etc...

List values for n = 1,2,3, etc...

Iamerror
2010-06-15 19:48:31

plug in values and see if it worked

plug in values and see if it worked

MJStone
2010-06-15 19:48:31

Plug in numbers, find some clever patterns with remainders

Plug in numbers, find some clever patterns with remainders

ziv
2010-06-15 19:48:31

smartkid11235813
2010-06-15 19:48:31

Find S(n) in terms of n

Find S(n) in terms of n

soccer22
2010-06-15 19:48:31

calculate the first few terms of S(n)

calculate the first few terms of S(n)

digitsman
2010-06-15 19:48:31

digitsman, out!

digitsman, out!

Arouet
2010-06-15 19:48:31

work out beginning values and look for a pattern

work out beginning values and look for a pattern

blabla4198
2010-06-15 19:48:31

plug in n and s

plug in n and s

DanZ
2010-06-15 19:48:35

gh625
2010-06-15 19:49:09

Same as before

Same as before

hcs
2010-06-15 19:49:09

induction now

induction now

PowerOfPi
2010-06-15 19:49:09

induction!

induction!

professordad
2010-06-15 19:49:09

induction again

induction again

smartkid11235813
2010-06-15 19:49:09

Induction!

Induction!

lvdrlvr55
2010-06-15 19:49:09

check it with both n and n-1

check it with both n and n-1

bixiazheng
2010-06-15 19:49:09

induction

induction

avec_une_h
2010-06-15 19:49:09

induction

induction

Titandrake
2010-06-15 19:49:09

induction

induction

Arouet
2010-06-15 19:49:09

induction again

induction again

Shortgeek
2010-06-15 19:49:09

defining Q(n) = S(n) + 1, and observing that Q(n) = 3 * Q(n-1)

defining Q(n) = S(n) + 1, and observing that Q(n) = 3 * Q(n-1)

Iamerror
2010-06-15 19:49:09

induction again

induction again

stevenyu10a
2010-06-15 19:49:09

induction

induction

DanielC
2010-06-15 19:49:09

let t(n) equal S(n) + 1

let t(n) equal S(n) + 1

Great Spheres
2010-06-15 19:49:09

It follows the recurrence relation which we just proved, plus S(1) which we calculated

It follows the recurrence relation which we just proved, plus S(1) which we calculated

DanZ
2010-06-15 19:49:12

DanZ
2010-06-15 19:49:54

Now, I told you that I'd also show you how to write these up to be good proofs, the kind we're looking for. Your writing style wasn't that important on the quiz (but it could make a small difference); if you included all of the important elements for the proof was important.

Now, I told you that I'd also show you how to write these up to be good proofs, the kind we're looking for. Your writing style wasn't that important on the quiz (but it could make a small difference); if you included all of the important elements for the proof was important.

DanZ
2010-06-15 19:49:58

The final solution that you submit should have all of these elements in it. For example, here would be my final solution:

The final solution that you submit should have all of these elements in it. For example, here would be my final solution:

DanZ
2010-06-15 19:50:06

DanZ
2010-06-15 19:50:39

DanZ
2010-06-15 19:50:46

DanZ
2010-06-15 19:50:53

Ok. That was not short! Any questions?

Ok. That was not short! Any questions?

DanZ
2010-06-15 19:50:58

(Future questions will indeed go faster.)

(Future questions will indeed go faster.)

DanZ
2010-06-15 19:51:48

Then let's do part (b), but let's do this one more quickly.

Then let's do part (b), but let's do this one more quickly.

DanZ
2010-06-15 19:51:52

DanZ
2010-06-15 19:51:55

What's different here?

What's different here?

DanZ
2010-06-15 19:53:14

So, a quick note.

So, a quick note.

DanZ
2010-06-15 19:53:25

Saying "it only takes half the moves because they only go half as far" is not sufficiently rigorous for us.

Saying "it only takes half the moves because they only go half as far" is not sufficiently rigorous for us.

DanZ
2010-06-15 19:53:29

You have to prove it!

You have to prove it!

Great Spheres
2010-06-15 19:53:31

The largest disc only needs to move once

The largest disc only needs to move once

bixiazheng
2010-06-15 19:53:31

you have to use C as the extra peg

you have to use C as the extra peg

Iamerror
2010-06-15 19:53:31

the base value is only one, not two

the base value is only one, not two

Shortgeek
2010-06-15 19:53:31

you don't need to do as much, only move it one peg

you don't need to do as much, only move it one peg

ziv
2010-06-15 19:53:31

we're moving to the middle peg, and the problem isn't symmetrical

we're moving to the middle peg, and the problem isn't symmetrical

MeowmixOX;D
2010-06-15 19:53:31

less symmetry

less symmetry

avec_une_h
2010-06-15 19:53:31

we need to move the discs to B, not C

we need to move the discs to B, not C

Great Spheres
2010-06-15 19:53:31

So then we get the procedure is to move the n-1 discs to C, the largest to B, and then the n-1 from C to B

So then we get the procedure is to move the n-1 discs to C, the largest to B, and then the n-1 from C to B

professordad
2010-06-15 19:53:31

we move from peg A to peg B

we move from peg A to peg B

mathwiz172
2010-06-15 19:53:31

only have to move bottom ring once

only have to move bottom ring once

DanZ
2010-06-15 19:53:39

That's right, we're only trying to get to peg B. That screws up our inductive relationship --- up until now, we've only been keeping track of getting from peg A to peg C.

That's right, we're only trying to get to peg B. That screws up our inductive relationship --- up until now, we've only been keeping track of getting from peg A to peg C.

DanZ
2010-06-15 19:53:47

Let's create yet another sequence, P(n), which represents the minimum number of moves required to move n discs from peg A to peg B in this system.

Let's create yet another sequence, P(n), which represents the minimum number of moves required to move n discs from peg A to peg B in this system.

DanZ
2010-06-15 19:53:54

Can you give me a formula for P(n)? You can use S(n) in your formula.

Can you give me a formula for P(n)? You can use S(n) in your formula.

DanZ
2010-06-15 19:54:52

If you are saying S(n)/2, again, you need to give proof!

If you are saying S(n)/2, again, you need to give proof!

Shortgeek
2010-06-15 19:55:20

P(n) = P(n-1) + 1 + S(n-1)

P(n) = P(n-1) + 1 + S(n-1)

ziv
2010-06-15 19:55:20

$P(n) = S(n-1) + 1 + P(n - 1)$

$P(n) = S(n-1) + 1 + P(n - 1)$

DanielC
2010-06-15 19:55:20

P(n) = S(n-1) + 1 + P(n-1)

P(n) = S(n-1) + 1 + P(n-1)

PowerOfPi
2010-06-15 19:55:20

P(n)=S(n-1)+P(n-1)+1

P(n)=S(n-1)+P(n-1)+1

MeowmixOX;D
2010-06-15 19:55:20

P(n)= S(n)+1+P(n-1)

P(n)= S(n)+1+P(n-1)

smartkid11235813
2010-06-15 19:55:20

P(n)=S(n-1)+1+P(n-1)

P(n)=S(n-1)+1+P(n-1)

Great Spheres
2010-06-15 19:55:20

S(n+1) = S(n) +P(n) + 1

S(n+1) = S(n) +P(n) + 1

DanZ
2010-06-15 19:55:23

DanZ
2010-06-15 19:55:35

Ok, I'm not sure what to make of that. What should we do?

Ok, I'm not sure what to make of that. What should we do?

Shortgeek
2010-06-15 19:56:07

put in values, find a pattern, find a formula, induct or be clever

put in values, find a pattern, find a formula, induct or be clever

DanielC
2010-06-15 19:56:07

look at values

look at values

Great Spheres
2010-06-15 19:56:07

Find P(1)!

Find P(1)!

smartkid11235813
2010-06-15 19:56:07

Calculate Values and find relationship

Calculate Values and find relationship

DanZ
2010-06-15 19:56:10

DanZ
2010-06-15 19:56:14

Erm. Hrm. That doesn't look familiar. Any ideas?

Erm. Hrm. That doesn't look familiar. Any ideas?

peregrinefalcon88
2010-06-15 19:56:41

its a sum of powers of three

its a sum of powers of three

kevin7
2010-06-15 19:56:42

They're half of the values from before.

They're half of the values from before.

Great Spheres
2010-06-15 19:56:42

S(n) / 2, which we shall prove by induction

S(n) / 2, which we shall prove by induction

Shortgeek
2010-06-15 19:56:42

compare it to S(n)?

compare it to S(n)?

mathwiz172
2010-06-15 19:56:42

multiply all the answers by 2

multiply all the answers by 2

ksun48
2010-06-15 19:56:46

1, 1+3, 1+3+9, ... so we

1, 1+3, 1+3+9, ... so we

smartkid11235813
2010-06-15 19:56:50

See if 2P(n)=S(n)

See if 2P(n)=S(n)

DanZ
2010-06-15 19:57:06

DanZ
2010-06-15 19:57:14

DanZ
2010-06-15 19:57:19

Either way, giving us the same result.

Either way, giving us the same result.

DanZ
2010-06-15 19:57:23

If you're not familiar with geometric series, take a look at:

http://www.artofproblemsolving.com/Wiki/index.php/Geometric_series

(and there are plenty of AoPS classes that cover them, for example)

If you're not familiar with geometric series, take a look at:

http://www.artofproblemsolving.com/Wiki/index.php/Geometric_series

(and there are plenty of AoPS classes that cover them, for example)

DanZ
2010-06-15 19:57:31

I'm going to leave out how to write this solution up nicely, since it's very similar to part (a).

I'm going to leave out how to write this solution up nicely, since it's very similar to part (a).

DanZ
2010-06-15 19:57:54

We need to move on pretty quickly, but I want to share with you some alternative solutions.

We need to move on pretty quickly, but I want to share with you some alternative solutions.

DanZ
2010-06-15 19:58:15

Here is a solution submitted just now by MJStone that is very elegant:

Here is a solution submitted just now by MJStone that is very elegant:

MJStone
2010-06-15 19:58:21

If you think about the rules of the game, only two moves at most are possible at any time. You can move A to B or B to A, but not both; B and C have a similar relationship. So 2 moves total.

If you think about the rules of the game, only two moves at most are possible at any time. You can move A to B or B to A, but not both; B and C have a similar relationship. So 2 moves total.

MJStone
2010-06-15 19:58:21

Now, of those two moves, one must always be the reverse of the previous move, and clearly, this cannot be part of an optimal solution. So really, there is only one move to make at any time!

Now, of those two moves, one must always be the reverse of the previous move, and clearly, this cannot be part of an optimal solution. So really, there is only one move to make at any time!

MJStone
2010-06-15 19:58:21

This has an interesting consequence that every arrangement of discs that can be made must be made at some point (and exactly once--twice would again mean a nonoptimal solution). This requires a little more proof, which I can type out if you'd like.

This has an interesting consequence that every arrangement of discs that can be made must be made at some point (and exactly once--twice would again mean a nonoptimal solution). This requires a little more proof, which I can type out if you'd like.

MJStone
2010-06-15 19:58:21

The total number of arrangements, of course, is 3^n. But since the starting arrangement is already in place, the answer is 3^n - 1.

The total number of arrangements, of course, is 3^n. But since the starting arrangement is already in place, the answer is 3^n - 1.

MJStone
2010-06-15 19:58:21

This also makes part b easier. Since we know that our solution to a already passes through the arrangement required for b, and the game is symmetrical at that point, we can just divide the answer by 2.

This also makes part b easier. Since we know that our solution to a already passes through the arrangement required for b, and the game is symmetrical at that point, we can just divide the answer by 2.

DanZ
2010-06-15 19:58:46

I'd like to leave you with the following absolutely gorgeous solution by Mathieu, a former Mathcamper and later instructor. It will only make sense to you if you know a touch of graph theory, but if you do, I think you'll love it as much as I do --- and it takes MJStone's solution and makes it even more precise.

I'd like to leave you with the following absolutely gorgeous solution by Mathieu, a former Mathcamper and later instructor. It will only make sense to you if you know a touch of graph theory, but if you do, I think you'll love it as much as I do --- and it takes MJStone's solution and makes it even more precise.

DanZ
2010-06-15 19:59:00

DanZ
2010-06-15 19:59:32

Problem 2: The 100-Game

Problem 2: The 100-Game

DanZ
2010-06-15 19:59:36

Now let's pick up the pace. Here's the question:

Now let's pick up the pace. Here's the question:

DanZ
2010-06-15 19:59:41

DanZ
2010-06-15 19:59:53

Imagine that you're tackling this problem. Your question is, as a player, how can I get any handle on what happens during the game? What's the key insight that allows you some control?

Imagine that you're tackling this problem. Your question is, as a player, how can I get any handle on what happens during the game? What's the key insight that allows you some control?

ziv
2010-06-15 20:00:53

it's all about the value of the sum mod 11

it's all about the value of the sum mod 11

abhinand
2010-06-15 20:00:53

we can always make the sum 11 if we are second

we can always make the sum 11 if we are second

mathwiz172
2010-06-15 20:00:53

you can always make it add up to 11

you can always make it add up to 11

Arouet
2010-06-15 20:00:53

do the opposite of your opponent

do the opposite of your opponent

kevin7
2010-06-15 20:00:53

You can make the sum go up by 11 every two turns.

You can make the sum go up by 11 every two turns.

MJStone
2010-06-15 20:00:53

Completing the 11. Play 7 to their 4 or 4 to their 7.

Completing the 11. Play 7 to their 4 or 4 to their 7.

lvdrlvr55
2010-06-15 20:00:53

Because we cannot determine what our opponent will choose to add, it is advantageous to work towards multiples of 11 (4+7=11). If our opponent adds 4, then we can add 7; and vice versa. This would require us to go second. However, the smallest multiple of 11 ending in two 0’s would be 1100. Perhaps if we took the first turn, a faster and easier strategy could be found.

Because we cannot determine what our opponent will choose to add, it is advantageous to work towards multiples of 11 (4+7=11). If our opponent adds 4, then we can add 7; and vice versa. This would require us to go second. However, the smallest multiple of 11 ending in two 0’s would be 1100. Perhaps if we took the first turn, a faster and easier strategy could be found.

smartkid11235813
2010-06-15 20:00:53

you can always pick the oppisite number as your opponent

you can always pick the oppisite number as your opponent

mathwiz172
2010-06-15 20:00:53

or a multiple of 11

or a multiple of 11

Shortgeek
2010-06-15 20:00:53

if it's your turn, you can force the number to reach 11 plus what you give off

if it's your turn, you can force the number to reach 11 plus what you give off

mathwiz172
2010-06-15 20:00:53

or 4 more than a multiple of 11

or 4 more than a multiple of 11

Titandrake
2010-06-15 20:00:53

aka 4+7 always equals 11

aka 4+7 always equals 11

sachiroo
2010-06-15 20:01:01

11's!

11's!

DanielC
2010-06-15 20:01:08

saying the opposite number results in adding 11 to your previous sum

saying the opposite number results in adding 11 to your previous sum

Great Spheres
2010-06-15 20:01:08

You can't control your opponent's moves, so you'd have to take advantage of the fact that no matter what your opponent does it's always possible to go up by 11 in two moves

You can't control your opponent's moves, so you'd have to take advantage of the fact that no matter what your opponent does it's always possible to go up by 11 in two moves

DanZ
2010-06-15 20:01:13

Ah-ha! As a player, I can make sure that my move plus my opponent's previous move sums to 11. Thus, I can make sure that the game goes up in multiples of 11.

Ah-ha! As a player, I can make sure that my move plus my opponent's previous move sums to 11. Thus, I can make sure that the game goes up in multiples of 11.

DanZ
2010-06-15 20:01:23

So, for example, if the first player plays 7, then the second player could play 4, totaling 11. Then the first player might play, say, 4, in which case the second player plays 7, giving 22. And so forth, going up by 11 each time. If the second player could keep this up until she or he gets to 1100, they win!

So, for example, if the first player plays 7, then the second player could play 4, totaling 11. Then the first player might play, say, 4, in which case the second player plays 7, giving 22. And so forth, going up by 11 each time. If the second player could keep this up until she or he gets to 1100, they win!

DanZ
2010-06-15 20:01:29

Unfortunately, if the first player is at all smart, that won't work. Why not?

Unfortunately, if the first player is at all smart, that won't work. Why not?

mathwiz172
2010-06-15 20:02:19

but isn't it a faster win if you start out with 4, then add up multiples of 11? then you can go to 400

but isn't it a faster win if you start out with 4, then add up multiples of 11? then you can go to 400

Great Spheres
2010-06-15 20:02:19

Thus when you find out that 400-4 is a multiple of eleven, you can see that the first player should move 4 first

Thus when you find out that 400-4 is a multiple of eleven, you can see that the first player should move 4 first

turak
2010-06-15 20:02:19

They can reach a multiple before you

They can reach a multiple before you

avec_une_h
2010-06-15 20:02:19

Because there are smaller numbers that are 4 or 7 mod 11

Because there are smaller numbers that are 4 or 7 mod 11

turak
2010-06-15 20:02:19

400, 700

400, 700

smartkid11235813
2010-06-15 20:02:19

they will hit a multiple of 100 before 1100

they will hit a multiple of 100 before 1100

Iamerror
2010-06-15 20:02:19

because at one point you will come within 4 of a multiple of 100

because at one point you will come within 4 of a multiple of 100

quadraticfanatic
2010-06-15 20:02:19

could play 11's on you and get a lower hundred

could play 11's on you and get a lower hundred

Shortgeek
2010-06-15 20:02:19

because the first player can maneuver the game into 400 by starting with 4

because the first player can maneuver the game into 400 by starting with 4

gh625
2010-06-15 20:02:19

The first player can use the same strategy and get to a multiple of 100 first.

The first player can use the same strategy and get to a multiple of 100 first.

peefthepur1
2010-06-15 20:02:19

He might get an 100 before the second player adds either a 4 or a 7

He might get an 100 before the second player adds either a 4 or a 7

sachiroo
2010-06-15 20:02:19

They could reach 400 by summing 11's starting with 4.

They could reach 400 by summing 11's starting with 4.

DanZ
2010-06-15 20:02:25

There's an opportunity for the first player to get to a multiple of 100 first: when the second player gets to 396 (a multiple of 11), the first player can add 4 and win, well before we get to 1100!

There's an opportunity for the first player to get to a multiple of 100 first: when the second player gets to 396 (a multiple of 11), the first player can add 4 and win, well before we get to 1100!

DanZ
2010-06-15 20:02:37

Does this suggest a better strategy for either player?

Does this suggest a better strategy for either player?

gh625
2010-06-15 20:03:01

Go first

Go first

Arouet
2010-06-15 20:03:01

start with the 4

start with the 4

smartkid11235813
2010-06-15 20:03:01

Go first and start with 4

Go first and start with 4

forthewinalcumus
2010-06-15 20:03:01

yes, the 1st player can control the game

yes, the 1st player can control the game

lvdrlvr55
2010-06-15 20:03:01

Yes, start with 4 and then alternate.

Yes, start with 4 and then alternate.

bixiazheng
2010-06-15 20:03:01

1st

1st

PowerOfPi
2010-06-15 20:03:01

first player has advantage

first player has advantage

Great Spheres
2010-06-15 20:03:01

It's possible to prove that the first player can gaurantee a win at 400.

It's possible to prove that the first player can gaurantee a win at 400.

MJStone
2010-06-15 20:03:08

First player starts with 4, then always plays opposite of the opponent

First player starts with 4, then always plays opposite of the opponent

peefthepur1
2010-06-15 20:03:08

1st player

1st player

DanZ
2010-06-15 20:03:09

Yes! If the first player starts off by putting in 4, the first player can make sure that we keep going up by 11 from 4: so the pattern would go:

4

either 8 or 11

15

either 19 or 22

26

either 30 or 33

37

...

Yes! If the first player starts off by putting in 4, the first player can make sure that we keep going up by 11 from 4: so the pattern would go:

4

either 8 or 11

15

either 19 or 22

26

either 30 or 33

37

...

DanZ
2010-06-15 20:03:20

If the first player keeps it up, we eventually get to 400, which is a multiple of 11 plus 4.

If the first player keeps it up, we eventually get to 400, which is a multiple of 11 plus 4.

DanZ
2010-06-15 20:03:25

Does this work?

Does this work?

DanielC
2010-06-15 20:03:57

yes\

yes\

bixiazheng
2010-06-15 20:03:57

yes

yes

forthewinalcumus
2010-06-15 20:03:57

so the 1st player wins, right?

so the 1st player wins, right?

abhinand
2010-06-15 20:03:57

YES

YES

ziv
2010-06-15 20:03:57

yes

yes

Shortgeek
2010-06-15 20:03:57

of course, we have to be careful that player 2 doesn't hit 100, 200, or 300 -- but we can show they don't through boring numbers

of course, we have to be careful that player 2 doesn't hit 100, 200, or 300 -- but we can show they don't through boring numbers

L2gB
2010-06-15 20:03:57

yes

yes

Arouet
2010-06-15 20:03:57

should

should

quadraticfanatic
2010-06-15 20:03:57

yes

yes

Shortgeek
2010-06-15 20:03:57

so yes it works

so yes it works

Great Spheres
2010-06-15 20:03:57

So 11n+4 is the number after the first player moves. It's possible to show that 11n+4 plus then 4 or 7 cannot equal 100, 200, or 300, so the second player can't achieve a victory.

So 11n+4 is the number after the first player moves. It's possible to show that 11n+4 plus then 4 or 7 cannot equal 100, 200, or 300, so the second player can't achieve a victory.

avec_une_h
2010-06-15 20:03:57

yes

yes

kevin7
2010-06-15 20:03:57

If the 1st player is consistent, yes

If the 1st player is consistent, yes

DanZ
2010-06-15 20:04:00

Yes, it does. What more do you need to do in your solution to this problem besides giving this strategy?

Yes, it does. What more do you need to do in your solution to this problem besides giving this strategy?

ziv
2010-06-15 20:04:34

show it can't be 100, 200, or 300

show it can't be 100, 200, or 300

smartkid11235813
2010-06-15 20:04:34

yes show that 100,200, and 300 are impossible to reach and you prove your solution

yes show that 100,200, and 300 are impossible to reach and you prove your solution

forthewinalcumus
2010-06-15 20:04:34

PROVE IT

PROVE IT

PurpleEnigma
2010-06-15 20:04:34

prove it?

prove it?

L2gB
2010-06-15 20:04:34

prove player 2 cant win before hand

prove player 2 cant win before hand

Great Spheres
2010-06-15 20:04:34

Block counter-strategies

Block counter-strategies

Iamerror
2010-06-15 20:04:34

proof that it works every time

proof that it works every time

Shortgeek
2010-06-15 20:04:34

make sure they don't hit 100, 200, or 300

make sure they don't hit 100, 200, or 300

professordad
2010-06-15 20:04:34

a proof?

a proof?

Titandrake
2010-06-15 20:04:34

prove ther isn't a way for the 2nd player to reach a 100 first, which i didn't do

prove ther isn't a way for the 2nd player to reach a 100 first, which i didn't do

sachiroo
2010-06-15 20:04:34

Some sort of rigor... I wish there was a better way to do it than the boring numbers way.

Some sort of rigor... I wish there was a better way to do it than the boring numbers way.

DanielC
2010-06-15 20:04:37

check that player two can't get100, 200, or 300

check that player two can't get100, 200, or 300

quadraticfanatic
2010-06-15 20:04:37

prove that opponent cannot get 100, 200, or 300

prove that opponent cannot get 100, 200, or 300

DanZ
2010-06-15 20:04:45

Yeah, this is not super-interesting, but you don't have to do a lot.

Yeah, this is not super-interesting, but you don't have to do a lot.

DanZ
2010-06-15 20:04:46

You need to show that the second player is unable, through any plays, to get to 100, 200, or 300. (It's the first player that gets to 400.)

You need to show that the second player is unable, through any plays, to get to 100, 200, or 300. (It's the first player that gets to 400.)

DanZ
2010-06-15 20:04:51

Here's a complete solution:

Here's a complete solution:

DanZ
2010-06-15 20:04:57

DanZ
2010-06-15 20:05:22

You can also express it using modular arithmetic, btw:

You can also express it using modular arithmetic, btw:

PowerOfPi
2010-06-15 20:05:23

Second player can attain values 8 or 0 mod 11, but none of 100, 200, or 300 are 8 or 0 mod 11.

Second player can attain values 8 or 0 mod 11, but none of 100, 200, or 300 are 8 or 0 mod 11.

DanZ
2010-06-15 20:05:27

Any questions about that problem?

Any questions about that problem?

Shortgeek
2010-06-15 20:05:47

is there a prettier way?

is there a prettier way?

DanZ
2010-06-15 20:05:59

Unfortunately, not that I know of for this problem; on the other hand, it's short. :)

Unfortunately, not that I know of for this problem; on the other hand, it's short. :)

fortenforge
2010-06-15 20:06:04

Is there anything special about 4 and 7?

Is there anything special about 4 and 7?

DanZ
2010-06-15 20:06:16

No. This would essentially work unchanged for virtually any two numbers.

No. This would essentially work unchanged for virtually any two numbers.

DanZ
2010-06-15 20:07:02

(I don't think that if they're coprime matters, so long as you can get to a multiple of 100.)

(I don't think that if they're coprime matters, so long as you can get to a multiple of 100.)

DanZ
2010-06-15 20:07:18

Problem 3: One-to-one and Onto

Problem 3: One-to-one and Onto

DanZ
2010-06-15 20:07:22

Here's part (a) of our next problem.

Here's part (a) of our next problem.

DanZ
2010-06-15 20:07:28

DanZ
2010-06-15 20:07:46

DanZ
2010-06-15 20:08:06

Iamerror
2010-06-15 20:08:54

6

6

kevin7
2010-06-15 20:08:54

1+5 = 6

1+5 = 6

nwalton125
2010-06-15 20:08:54

6

6

bixiazheng
2010-06-15 20:08:54

6

6

Titandrake
2010-06-15 20:08:54

6

6

math911
2010-06-15 20:08:54

1+r

1+r

.cpp
2010-06-15 20:08:54

1+5=6

1+5=6

professordad
2010-06-15 20:08:54

DanielC
2010-06-15 20:08:54

6

6

hcs
2010-06-15 20:08:54

it can't be -8 because then it would be negative

it can't be -8 because then it would be negative

avec_une_h
2010-06-15 20:08:54

6

6

Shortgeek
2010-06-15 20:08:54

6 because it can't be -7 because it only goes to positive integers

6 because it can't be -7 because it only goes to positive integers

quadraticfanatic
2010-06-15 20:08:54

six

six

DanZ
2010-06-15 20:08:58

It's F(1) = 1 + 5 = 6. That's because F(1) is either 1 + 5 or 1 - 8, and 1 - 8 isn't in the set {1, 2, 3, ...}.

It's F(1) = 1 + 5 = 6. That's because F(1) is either 1 + 5 or 1 - 8, and 1 - 8 isn't in the set {1, 2, 3, ...}.

DanZ
2010-06-15 20:09:05

DanielC
2010-06-15 20:09:33

7

7

MJStone
2010-06-15 20:09:33

7

7

Iamerror
2010-06-15 20:09:33

7

7

nwalton125
2010-06-15 20:09:33

7

7

avec_une_h
2010-06-15 20:09:33

7

7

quadraticfanatic
2010-06-15 20:09:33

seven

seven

Shortgeek
2010-06-15 20:09:33

7 similarly

7 similarly

abhinand
2010-06-15 20:09:33

7

7

hcs
2010-06-15 20:09:33

the same reasoning applies, we must add

the same reasoning applies, we must add

professordad
2010-06-15 20:09:33

lvdrlvr55
2010-06-15 20:09:33

7

7

L2gB
2010-06-15 20:09:33

7

7

Arouet
2010-06-15 20:09:33

7

7

Great Spheres
2010-06-15 20:09:33

Same logic applies to give 7.

Same logic applies to give 7.

roflmao14723
2010-06-15 20:09:33

7

7

math911
2010-06-15 20:09:33

2+r=7

2+r=7

stevenyu10a
2010-06-15 20:09:33

7

7

.cpp
2010-06-15 20:09:33

2+5=7

2+5=7

smartkid11235813
2010-06-15 20:09:33

7 cant be -6

7 cant be -6

kevin7
2010-06-15 20:09:33

7, and so on until F(9)

7, and so on until F(9)

DanZ
2010-06-15 20:09:35

For the same reason, it's 7.

For the same reason, it's 7.

DanZ
2010-06-15 20:09:38

When does this change?

When does this change?

forthewinalcumus
2010-06-15 20:10:00

so F(2) is 7 and F(3) is 8... until you get F(9) is either 1 or 16

so F(2) is 7 and F(3) is 8... until you get F(9) is either 1 or 16

math911
2010-06-15 20:10:00

9

9

MJStone
2010-06-15 20:10:00

9

9

Great Spheres
2010-06-15 20:10:00

9

9

Iamerror
2010-06-15 20:10:00

at nine

at nine

Titandrake
2010-06-15 20:10:00

at F(9)

at F(9)

forthewinalcumus
2010-06-15 20:10:00

when you get up to 9

when you get up to 9

stevenyu10a
2010-06-15 20:10:00

f(6)

f(6)

PowerOfPi
2010-06-15 20:10:00

at F(9)

at F(9)

hcs
2010-06-15 20:10:00

when we get to a number where n-8 is positive

when we get to a number where n-8 is positive

PurpleEnigma
2010-06-15 20:10:00

at 9, then it can be 1 or 14

at 9, then it can be 1 or 14

nwalton125
2010-06-15 20:10:00

f(9)

f(9)

peefthepur1
2010-06-15 20:10:00

n>8?

n>8?

bixiazheng
2010-06-15 20:10:00

F(9)

F(9)

lvdrlvr55
2010-06-15 20:10:00

F(9)

F(9)

Arouet
2010-06-15 20:10:00

at 9

at 9

quadraticfanatic
2010-06-15 20:10:00

at 9, cuz we need it to be 1

at 9, cuz we need it to be 1

DanZ
2010-06-15 20:10:06

.cpp
2010-06-15 20:10:40

F(9), because we need to have a F(x)=1.

F(9), because we need to have a F(x)=1.

Titandrake
2010-06-15 20:10:40

F(9) has to equal 1

F(9) has to equal 1

smartkid11235813
2010-06-15 20:10:40

at F(9) because 1 has to be an answer

at F(9) because 1 has to be an answer

Shortgeek
2010-06-15 20:10:40

F(9), which must equal 1 because something has to hit 1

F(9), which must equal 1 because something has to hit 1

Titandrake
2010-06-15 20:10:41

or else not onto

or else not onto

MJStone
2010-06-15 20:10:41

Because it's onto, it must change at 9

Because it's onto, it must change at 9

Great Spheres
2010-06-15 20:10:41

You realize then that F-inverse of 1 must exist as well, because F is bijective.

You realize then that F-inverse of 1 must exist as well, because F is bijective.

quadraticfanatic
2010-06-15 20:10:41

1.

1.

Arouet
2010-06-15 20:10:41

1

1

bixiazheng
2010-06-15 20:10:41

9-8

9-8

stevenyu10a
2010-06-15 20:10:41

1

1

forthewinalcumus
2010-06-15 20:10:41

1,

1,

MJStone
2010-06-15 20:10:41

To be 1

To be 1

smartkid11235813
2010-06-15 20:10:41

1 have to have a 1

1 have to have a 1

DanielC
2010-06-15 20:10:41

1 because f(x) is onto

1 because f(x) is onto

kevin7
2010-06-15 20:10:41

the latter, since we need f(n) = 1 for some n

the latter, since we need f(n) = 1 for some n

L2gB
2010-06-15 20:10:41

1

1

MeowmixOX;D
2010-06-15 20:10:41

1

1

.cpp
2010-06-15 20:10:41

1

1

ziv
2010-06-15 20:10:41

1, because there is no other n for which F(n) could be 1

1, because there is no other n for which F(n) could be 1

hcs
2010-06-15 20:10:41

if we go any higher we will never reach 1, and the function would not be onto

if we go any higher we will never reach 1, and the function would not be onto

PowerOfPi
2010-06-15 20:10:41

1 because it hasn't already been an F(k)

1 because it hasn't already been an F(k)

Iamerror
2010-06-15 20:10:41

1, because all the inputs for F(x) must also be outputs

1, because all the inputs for F(x) must also be outputs

nwalton125
2010-06-15 20:10:43

1, otherwise F(n) can never equal one

1, otherwise F(n) can never equal one

roflmao14723
2010-06-15 20:10:43

1

1

Great Spheres
2010-06-15 20:10:45

Thus, F inverse of 1 is 9, and F(9) is 1

Thus, F inverse of 1 is 9, and F(9) is 1

DanZ
2010-06-15 20:10:50

DanZ
2010-06-15 20:10:56

DanZ
2010-06-15 20:11:04

What's the pattern with how F(n) behaves?

What's the pattern with how F(n) behaves?

math911
2010-06-15 20:11:59

mod 13

mod 13

Shortgeek
2010-06-15 20:11:59

in intervals of 13, F(n) - n repeats

in intervals of 13, F(n) - n repeats

forthewinalcumus
2010-06-15 20:11:59

it continues in cycles

it continues in cycles

kevin7
2010-06-15 20:11:59

Every 13 values, it repeats. (8 values add, 5 values subtract)

Every 13 values, it repeats. (8 values add, 5 values subtract)

Iamerror
2010-06-15 20:11:59

+5 for 8 and then -8 for 5

+5 for 8 and then -8 for 5

avec_une_h
2010-06-15 20:11:59

add for 5, subtract for 8

add for 5, subtract for 8

professordad
2010-06-15 20:11:59

linear for 8 terms, then goes down and up, and so on

linear for 8 terms, then goes down and up, and so on

stevenyu10a
2010-06-15 20:11:59

period of 13

period of 13

Great Spheres
2010-06-15 20:11:59

It's based on intervals of integers; frmo 1-13, 14-16, etc.

It's based on intervals of integers; frmo 1-13, 14-16, etc.

math911
2010-06-15 20:11:59

it repeats every 13 times

it repeats every 13 times

abhinand
2010-06-15 20:11:59

cyclic

cyclic

roflmao14723
2010-06-15 20:11:59

first 9 add, next 5 subtract, repeat

first 9 add, next 5 subtract, repeat

smartkid11235813
2010-06-15 20:11:59

F(n) = n+5 for n=1.2.3.4.5.6.7.8 (mod 13)

F(n) = n+5 for n=1.2.3.4.5.6.7.8 (mod 13)

bixiazheng
2010-06-15 20:11:59

Increases for 7 values, then drops 12 and increases 4, then ads 14 and increases 7...

Increases for 7 values, then drops 12 and increases 4, then ads 14 and increases 7...

ziv
2010-06-15 20:11:59

has a period of 13 kind of... increases by 13 each run-through

has a period of 13 kind of... increases by 13 each run-through

blabla4198
2010-06-15 20:11:59

it goes consecutively, then skips, goes consecutive, and skips... (goes on and on)

it goes consecutively, then skips, goes consecutive, and skips... (goes on and on)

PowerOfPi
2010-06-15 20:11:59

F(n)=n+5 for n=1-8, 14-21, 28-35, ...

F(n)=n+5 for n=1-8, 14-21, 28-35, ...

Titandrake
2010-06-15 20:11:59

1-8 mod 13 it's +5, rest is -8

1-8 mod 13 it's +5, rest is -8

MJStone
2010-06-15 20:12:02

If it's 1 through s mod (r+s), then F(n)=n+r. Otherwise, F(n) = n-s

If it's 1 through s mod (r+s), then F(n)=n+r. Otherwise, F(n) = n-s

DanZ
2010-06-15 20:12:06

It's a permutation on each 13 numbers. That is, for the numbers 1-8, it adds 5; then for 9-13, it subtracts 8; then for 14-21 it adds 5; then for 22-26 it subtracts 8; and so forth.

It's a permutation on each 13 numbers. That is, for the numbers 1-8, it adds 5; then for 9-13, it subtracts 8; then for 14-21 it adds 5; then for 22-26 it subtracts 8; and so forth.

DanZ
2010-06-15 20:12:22

Now that we have a pattern, lets find a way to write it nicely: that is often a key step in better understanding a problem.

Now that we have a pattern, lets find a way to write it nicely: that is often a key step in better understanding a problem.

ziv
2010-06-15 20:12:27

i.e. F(n + 13) = F(n) + 13

i.e. F(n + 13) = F(n) + 13

DanZ
2010-06-15 20:12:32

That's one nice way to say it.

That's one nice way to say it.

DanZ
2010-06-15 20:12:56

DanZ
2010-06-15 20:13:12

DanZ
2010-06-15 20:13:26

What do we have to do now?

What do we have to do now?

blabla4198
2010-06-15 20:14:07

give proof

give proof

smartkid11235813
2010-06-15 20:14:07

prove it meets both definitions

prove it meets both definitions

DanZ
2010-06-15 20:14:10

We have to prove that this is true! We were somewhat lenient with this when looking over quizzes, but in general you should prove it. In this case, it is not hard.

We have to prove that this is true! We were somewhat lenient with this when looking over quizzes, but in general you should prove it. In this case, it is not hard.

DanZ
2010-06-15 20:14:17

DanZ
2010-06-15 20:14:44

More importantly, how do we calculate F(2010), and what is it?

More importantly, how do we calculate F(2010), and what is it?

quadraticfanatic
2010-06-15 20:15:44

since 2010 is 8(mod 13), F(2010)=2015

since 2010 is 8(mod 13), F(2010)=2015

smartkid11235813
2010-06-15 20:15:44

2010=8 (mod 13)

2010=8 (mod 13)

L2gB
2010-06-15 20:15:44

see if we add or subtract by finding the remainder of 2010/13

see if we add or subtract by finding the remainder of 2010/13

hcs
2010-06-15 20:15:44

2010 mod 13 is 8, so F(2010) is 2010+5=2015

2010 mod 13 is 8, so F(2010) is 2010+5=2015

Shortgeek
2010-06-15 20:15:44

take 2010 mod 13, see it is 8, note that F(8) = 8 + 5, so F(2010) = 2010 + 5 = 2015

take 2010 mod 13, see it is 8, note that F(8) = 8 + 5, so F(2010) = 2010 + 5 = 2015

PowerOfPi
2010-06-15 20:15:44

2010 mod 13 = 5, so F(2010)=2010+5=2015.

2010 mod 13 = 5, so F(2010)=2010+5=2015.

forthewinalcumus
2010-06-15 20:15:44

2010 can be written as 154x13 plus 8, so it is 2010 plus 5, or 2015, right?

2010 can be written as 154x13 plus 8, so it is 2010 plus 5, or 2015, right?

DanielC
2010-06-15 20:15:44

2010 = 8 (mod13) = F(2010) = 2010 +5 = 2015

2010 = 8 (mod13) = F(2010) = 2010 +5 = 2015

smartkid11235813
2010-06-15 20:15:44

thus F(2010) = n+5 = 2015

thus F(2010) = n+5 = 2015

professordad
2010-06-15 20:15:45

2010 = 154 * 13 + 8 so F(n) = 2010 + 5 = 2015 since m = 8

2010 = 154 * 13 + 8 so F(n) = 2010 + 5 = 2015 since m = 8

kevin7
2010-06-15 20:15:45

f(2010) is 2015, since 2010 = 8 mod 13

f(2010) is 2015, since 2010 = 8 mod 13

nwalton125
2010-06-15 20:15:50

m=2010 mod 13, using that, we can plug in n=2010 and find the answer

m=2010 mod 13, using that, we can plug in n=2010 and find the answer

DanZ
2010-06-15 20:15:52

DanZ
2010-06-15 20:16:05

Now for part (b):

Now for part (b):

DanZ
2010-06-15 20:16:18

What's the first thing we do?

What's the first thing we do?

DanZ
2010-06-15 20:16:20

Ack, wait.

Ack, wait.

DanZ
2010-06-15 20:16:53

One moment, I'm getting a very strange LaTeX error

One moment, I'm getting a very strange LaTeX error

DanZ
2010-06-15 20:17:30

DanZ
2010-06-15 20:17:50

What's the first thing we do?

What's the first thing we do?

Great Spheres
2010-06-15 20:18:45

This is my favorite part! This is where I used F(n) is congruent to n+r and that every input and its value have the same quotient when divided by 13 to show that the function is just a loop. I then said that you can make a map of F that says 1 -> 6 -> 11 -> 2 -> etc. And this ended up being a loop.

This is my favorite part! This is where I used F(n) is congruent to n+r and that every input and its value have the same quotient when divided by 13 to show that the function is just a loop. I then said that you can make a map of F that says 1 -> 6 -> 11 -> 2 -> etc. And this ended up being a loop.

ziv
2010-06-15 20:18:45

kevin7
2010-06-15 20:18:45

Try to establish the same pattern as we had before, for variables r and s?

Try to establish the same pattern as we had before, for variables r and s?

Shortgeek
2010-06-15 20:18:45

Well if you apply it n times, then you add r X times and subtract s Y times -- rX = sY, and X + Y = n. We're looking for common multiples of r and s.

Well if you apply it n times, then you add r X times and subtract s Y times -- rX = sY, and X + Y = n. We're looking for common multiples of r and s.

MJStone
2010-06-15 20:18:45

Perhaps test it with the r and s given in part a.

Perhaps test it with the r and s given in part a.

quadraticfanatic
2010-06-15 20:18:45

experiment with small numbers

experiment with small numbers

forthewinalcumus
2010-06-15 20:18:57

use our known equations -- u know, the ones we derived in part a

use our known equations -- u know, the ones we derived in part a

DanZ
2010-06-15 20:18:59

These are all reasonable.

These are all reasonable.

DanZ
2010-06-15 20:19:15

DanZ
2010-06-15 20:19:21

DanZ
2010-06-15 20:19:35

Great Spheres
2010-06-15 20:20:49

You can then just examine one interval like 1-13, and then after you do that, extrapolate to the rest of the integers

You can then just examine one interval like 1-13, and then after you do that, extrapolate to the rest of the integers

Shortgeek
2010-06-15 20:20:49

there's an upper bound on how many times you can permute before something hits a loop -- it can only visit (r + s) spots

there's an upper bound on how many times you can permute before something hits a loop -- it can only visit (r + s) spots

quadraticfanatic
2010-06-15 20:20:49

see how many permutations it takes to get back around

see how many permutations it takes to get back around

smartkid11235813
2010-06-15 20:20:49

Figure out how many elements the k-fold compisition goes through before it returns to the original element

Figure out how many elements the k-fold compisition goes through before it returns to the original element

DanZ
2010-06-15 20:21:03

These are all true, but Great Spheres is the one that gives us a way of doing that. Let me take that proposal and state it more carefully.

These are all true, but Great Spheres is the one that gives us a way of doing that. Let me take that proposal and state it more carefully.

DanZ
2010-06-15 20:21:08

DanielC
2010-06-15 20:21:22

since adding r and subtracting s are equivalent (mod r + s), and we do not have to worry about going out of the set as seen above, we can treat F(x) like x+r

since adding r and subtracting s are equivalent (mod r + s), and we do not have to worry about going out of the set as seen above, we can treat F(x) like x+r

DanZ
2010-06-15 20:21:27

What I'm about to say can be more easily said using modular arithmetic, but I'll avoid it for now.

What I'm about to say can be more easily said using modular arithmetic, but I'll avoid it for now.

DanZ
2010-06-15 20:21:34

DanZ
2010-06-15 20:21:51

Great Spheres
2010-06-15 20:23:14

We must add it (r+s)/GCF(r,s) times

We must add it (r+s)/GCF(r,s) times

kevin7
2010-06-15 20:23:14

(r+s) / GCF (r, s)

(r+s) / GCF (r, s)

forthewinalcumus
2010-06-15 20:23:14

LCM (r, r plus s)

LCM (r, r plus s)

aaronlandesman
2010-06-15 20:23:14

i think it is r+s/ gcd (r,s)

i think it is r+s/ gcd (r,s)

DanZ
2010-06-15 20:23:32

DanZ
2010-06-15 20:24:01

DanZ
2010-06-15 20:24:06

I'm a little bit unhappy when I get that answer. Can anyone tell why?

I'm a little bit unhappy when I get that answer. Can anyone tell why?

quadraticfanatic
2010-06-15 20:25:05

it ugly

it ugly

hcs
2010-06-15 20:25:05

it looks ugly

it looks ugly

ziv
2010-06-15 20:25:05

it's a multiple of r divided by r

it's a multiple of r divided by r

Iamerror
2010-06-15 20:25:05

lcm(r,anyhting) divides by r

lcm(r,anyhting) divides by r

smartkid11235813
2010-06-15 20:25:05

can be written more simply as (r+s)/GCF(r,s)

can be written more simply as (r+s)/GCF(r,s)

DanZ
2010-06-15 20:25:15

These are legitimate reasons. (Although LCM is a perfectly fine function.)

These are legitimate reasons. (Although LCM is a perfectly fine function.)

DanZ
2010-06-15 20:25:20

But for my money, I'm unhappy because it's not clear that if you switch r and s, you get the same answer. But from what we did, it really feels like switching r and s should give the same result!

But for my money, I'm unhappy because it's not clear that if you switch r and s, you get the same answer. But from what we did, it really feels like switching r and s should give the same result!

DanZ
2010-06-15 20:25:31

DanZ
2010-06-15 20:25:51

Indeed, that answer shows that switching r and s makes no difference!

Indeed, that answer shows that switching r and s makes no difference!

Great Spheres
2010-06-15 20:26:08

You can also use Euclid's algorithm, although when I was working with it I was in GCDs

You can also use Euclid's algorithm, although when I was working with it I was in GCDs

DanZ
2010-06-15 20:26:10

Certainly true.

Certainly true.

DanZ
2010-06-15 20:26:12

Here's how I would write a full proof, but skipping the part where we define F (which we did above). For simplicity, this will assume that you know a bit of modular arithmetic; if you don't, you can think about how you'd translate our work above into a proof.

Here's how I would write a full proof, but skipping the part where we define F (which we did above). For simplicity, this will assume that you know a bit of modular arithmetic; if you don't, you can think about how you'd translate our work above into a proof.

DanZ
2010-06-15 20:26:20

DanZ
2010-06-15 20:26:28

DanZ
2010-06-15 20:26:52

DanZ
2010-06-15 20:26:55

Questions on that problem?

Questions on that problem?

DanZ
2010-06-15 20:27:17

Notice, by the way, that I have carefully proved both that my result works and that it is the least possible result that works.

Notice, by the way, that I have carefully proved both that my result works and that it is the least possible result that works.

DanZ
2010-06-15 20:28:01

Problem 4: 2^n and 5^n

Problem 4: 2^n and 5^n

DanZ
2010-06-15 20:28:07

DanZ
2010-06-15 20:28:12

ziv
2010-06-15 20:28:42

hcs
2010-06-15 20:28:42

2*5=10

2*5=10

MJStone
2010-06-15 20:28:42

Their product is 10^n

Their product is 10^n

kevin7
2010-06-15 20:28:42

2^n * 5^n = 10^n

2^n * 5^n = 10^n

gh625
2010-06-15 20:28:42

They multiply to give 10^n

They multiply to give 10^n

Titandrake
2010-06-15 20:28:42

2^n * 5^n = 10^n

2^n * 5^n = 10^n

peregrinefalcon88
2010-06-15 20:28:42

product is 10

product is 10

sachiroo
2010-06-15 20:28:42

They multiply to equal 10^n.

They multiply to equal 10^n.

DanielC
2010-06-15 20:28:42

their product is 10^n

their product is 10^n

Great Spheres
2010-06-15 20:28:42

2^n times 5^n is 10^n

2^n times 5^n is 10^n

L2gB
2010-06-15 20:28:42

when multiplied together, you get 10^n

when multiplied together, you get 10^n

nwalton125
2010-06-15 20:28:47

2^n*5^n=10^n

2^n*5^n=10^n

DanZ
2010-06-15 20:28:49

DanZ
2010-06-15 20:28:57

DanZ
2010-06-15 20:29:49

DanZ
2010-06-15 20:30:09

Unfortunately, that's not good enough. For all we know, maybe differences in the later digits account for this being different somehow. Worse, the digits are not the same for all square roots of powers of 10: take the square of any even power of 10 and it starts with 10! We need to decide between these two possibilities, and actually

Unfortunately, that's not good enough. For all we know, maybe differences in the later digits account for this being different somehow. Worse, the digits are not the same for all square roots of powers of 10: take the square of any even power of 10 and it starts with 10! We need to decide between these two possibilities, and actually

*prove*it. Don't despair, though; we have the basic ideas.
DanZ
2010-06-15 20:30:27

So let's see what to do next:

So let's see what to do next:

DanZ
2010-06-15 20:30:41

DanZ
2010-06-15 20:31:00

What can you tell me about the sign of k + p?

What can you tell me about the sign of k + p?

DanZ
2010-06-15 20:31:32

Wait, that was the wrong question.

Wait, that was the wrong question.

DanZ
2010-06-15 20:31:40

What can you tell me about the

What can you tell me about the

*parity*of k + p?
DanZ
2010-06-15 20:32:10

And can anyone tell me why?

And can anyone tell me why?

smartkid11235813
2010-06-15 20:32:59

odd

odd

Shortgeek
2010-06-15 20:32:59

must be odd, not sure why

must be odd, not sure why

avec_une_h
2010-06-15 20:32:59

it's odd

it's odd

ziv
2010-06-15 20:32:59

if it was even, then the left term would be a little less than 1000.... so it would start with a 9, not a 1! so k+p is odd

if it was even, then the left term would be a little less than 1000.... so it would start with a 9, not a 1! so k+p is odd

kevin7
2010-06-15 20:32:59

It appears to always be odd...

It appears to always be odd...

DanZ
2010-06-15 20:33:02

Ah-ha! It cannot be even. If k + p was even, then the RHS would have more digits than the LHS, but we chose k so that would not be the case. (Notice how this takes care of one of the problems we encountered before: if we would have an even power of 10 or not.)

Ah-ha! It cannot be even. If k + p was even, then the RHS would have more digits than the LHS, but we chose k so that would not be the case. (Notice how this takes care of one of the problems we encountered before: if we would have an even power of 10 or not.)

DanZ
2010-06-15 20:33:14

L2gB
2010-06-15 20:34:47

they are 31...

they are 31...

Shortgeek
2010-06-15 20:34:47

they are the first ten digits of sqrt(10) times a power of 10

they are the first ten digits of sqrt(10) times a power of 10

kevin7
2010-06-15 20:34:47

They're the same as the first ten digits of sqrt(10)!

They're the same as the first ten digits of sqrt(10)!

.cpp
2010-06-15 20:34:47

Must be around the square root of 10.

Must be around the square root of 10.

Titandrake
2010-06-15 20:34:47

same as the first ten digits of root 10

same as the first ten digits of root 10

smartkid11235813
2010-06-15 20:34:47

must be the digits of sqrt(10) 3162277660

must be the digits of sqrt(10) 3162277660

Arouet
2010-06-15 20:34:47

close to root 10

close to root 10

ziv
2010-06-15 20:34:47

DanZ
2010-06-15 20:34:54

DanZ
2010-06-15 20:35:02

I'll leave writing it up to you, since the above form is already very close to a full write-up.

I'll leave writing it up to you, since the above form is already very close to a full write-up.

DanZ
2010-06-15 20:35:05

Questions?

Questions?

DanZ
2010-06-15 20:35:24

We are about half-way done at this point, with some very interesting problems left to go.

We are about half-way done at this point, with some very interesting problems left to go.

L2gB
2010-06-15 20:35:48

how about the extra?

how about the extra?

smartkid11235813
2010-06-15 20:35:48

are we going to do the extra bonus part

are we going to do the extra bonus part

aaronlandesman
2010-06-15 20:35:48

can you explain 4 extra?

can you explain 4 extra?

DanZ
2010-06-15 20:35:54

I'm afraid I won't be doing that here right now.

I'm afraid I won't be doing that here right now.

DanZ
2010-06-15 20:36:01

In part for time, in part because I don't have it prepared.

In part for time, in part because I don't have it prepared.

DanZ
2010-06-15 20:36:07

Sorry about that. :(

Sorry about that. :(

Great Spheres
2010-06-15 20:36:36

Is it possible to prove that it exists, though?

Is it possible to prove that it exists, though?

DanZ
2010-06-15 20:36:39

Yes, it is.

Yes, it is.

MJStone
2010-06-15 20:36:42

How complicated is it? I never solved it myself.

How complicated is it? I never solved it myself.

DanZ
2010-06-15 20:36:49

It's not bad with the right idea and some bookkeeping.

It's not bad with the right idea and some bookkeeping.

DanZ
2010-06-15 20:36:58

Ok, let us press forwards!

Ok, let us press forwards!

DanZ
2010-06-15 20:37:05

Problem 5: Xs and Os

Problem 5: Xs and Os

DanZ
2010-06-15 20:37:11

DanZ
2010-06-15 20:37:24

DanZ
2010-06-15 20:37:33

DanZ
2010-06-15 20:37:40

Let's start with (a). Is it true?

Let's start with (a). Is it true?

Shortgeek
2010-06-15 20:38:04

ayup

ayup

Titandrake
2010-06-15 20:38:04

yes

yes

ziv
2010-06-15 20:38:04

yup! :)

yup! :)

Iamerror
2010-06-15 20:38:04

yes

yes

kevin7
2010-06-15 20:38:04

yes

yes

gh625
2010-06-15 20:38:04

yes

yes

MJStone
2010-06-15 20:38:04

Yes

Yes

Great Spheres
2010-06-15 20:38:04

It is

It is

lvdrlvr55
2010-06-15 20:38:04

yes

yes

L2gB
2010-06-15 20:38:04

yes

yes

gh625
2010-06-15 20:38:04

use strong induction

use strong induction

DanielC
2010-06-15 20:38:04

yes

yes

aaronlandesman
2010-06-15 20:38:04

indeed i believe it is

indeed i believe it is

DanZ
2010-06-15 20:38:06

Yes, it is. Let's see how to prove it.

Yes, it is. Let's see how to prove it.

DanZ
2010-06-15 20:38:13

If we allow for repeating sequences, how many sequences of length n are there?

If we allow for repeating sequences, how many sequences of length n are there?

MJStone
2010-06-15 20:38:46

2^n

2^n

Shortgeek
2010-06-15 20:38:46

2^n

2^n

kevin7
2010-06-15 20:38:46

2^n

2^n

avec_une_h
2010-06-15 20:38:46

2^n

2^n

Titandrake
2010-06-15 20:38:46

2^n

2^n

ziv
2010-06-15 20:38:46

sachiroo
2010-06-15 20:38:46

2^n

2^n

L2gB
2010-06-15 20:38:46

2^n

2^n

Great Spheres
2010-06-15 20:38:46

2^n

2^n

nwalton125
2010-06-15 20:38:46

2^n

2^n

.cpp
2010-06-15 20:38:46

Arouet
2010-06-15 20:38:46

2^n

2^n

DanZ
2010-06-15 20:38:49

DanZ
2010-06-15 20:38:53

Now, we need to subtract out the repeating sequences. What repeating sequences do we need to subtract out?

Now, we need to subtract out the repeating sequences. What repeating sequences do we need to subtract out?

MJStone
2010-06-15 20:40:20

Factors of n

Factors of n

hcs
2010-06-15 20:40:20

all of the ones of length dividing n

all of the ones of length dividing n

sachiroo
2010-06-15 20:40:20

Sequences that are of a length that divides n.

Sequences that are of a length that divides n.

gh625
2010-06-15 20:40:20

There's one repeating sequence for each non-repeating sequence which has a length which divides n.

There's one repeating sequence for each non-repeating sequence which has a length which divides n.

smartkid11235813
2010-06-15 20:40:20

2^n- a(A)- a(B)- ... A,B,... are facors of n (inc 1)

2^n- a(A)- a(B)- ... A,B,... are facors of n (inc 1)

Great Spheres
2010-06-15 20:40:20

The number of repeating sequences is the number of sequences of a length of a factor of n,

The number of repeating sequences is the number of sequences of a length of a factor of n,

Shortgeek
2010-06-15 20:40:20

for each possible repetition length K (where K must divide n), you need to subtract out a_K possible repetitive sequences to avoid repeats.

for each possible repetition length K (where K must divide n), you need to subtract out a_K possible repetitive sequences to avoid repeats.

MJStone
2010-06-15 20:40:20

Well, sequences of lengths that are factors of n

Well, sequences of lengths that are factors of n

Arouet
2010-06-15 20:40:20

factors of n

factors of n

Shortgeek
2010-06-15 20:40:20

one for each possible "repeatee"

one for each possible "repeatee"

aaronlandesman
2010-06-15 20:40:20

sorry i should be the sum of 2^d for all n that divide d

sorry i should be the sum of 2^d for all n that divide d

DanZ
2010-06-15 20:40:27

DanZ
2010-06-15 20:40:34

MJStone
2010-06-15 20:41:52

a(d)

a(d)

Shortgeek
2010-06-15 20:41:52

a_d, because you can only subtract ones that themselves don't repeat smaller ones

a_d, because you can only subtract ones that themselves don't repeat smaller ones

L2gB
2010-06-15 20:41:52

a_d

a_d

kevin7
2010-06-15 20:41:52

a_d. If we subtracted 2^d, we'd be oversubtracting since some of the strings of length d are themselves repetitions of strings of an even shorter length

a_d. If we subtracted 2^d, we'd be oversubtracting since some of the strings of length d are themselves repetitions of strings of an even shorter length

Great Spheres
2010-06-15 20:41:52

a sub d (I can't Latex that, I don't know how to, makes it hard), but we want to filter out the repeating strings of smaller length because then, if we had a smaller e, then it would also be a factor of n that'd be counted

a sub d (I can't Latex that, I don't know how to, makes it hard), but we want to filter out the repeating strings of smaller length because then, if we had a smaller e, then it would also be a factor of n that'd be counted

smartkid11235813
2010-06-15 20:41:52

a(d)

a(d)

MJStone
2010-06-15 20:41:52

Because if we only do 2^d, then we subtract a repeating sequence of length some other d. But we'll already be subtracting that too.

Because if we only do 2^d, then we subtract a repeating sequence of length some other d. But we'll already be subtracting that too.

Titandrake
2010-06-15 20:41:52

the # of sequences of length d that do not have repeating sequences, or else you overcount

the # of sequences of length d that do not have repeating sequences, or else you overcount

DanZ
2010-06-15 20:41:56

DanZ
2010-06-15 20:42:08

It

It

*is*possible to subtract 2^d and then add back in the sequences you double-subtracted, then subtract off the sequences you double-added, etc. etc. etc., but that is*messy*. I did see a few quizzes that managed it correctly, though!
DanZ
2010-06-15 20:42:19

DanZ
2010-06-15 20:42:26

What's the idea from here on out?

What's the idea from here on out?

gh625
2010-06-15 20:43:28

use strong induction

use strong induction

hcs
2010-06-15 20:43:28

complete induction

complete induction

DanielC
2010-06-15 20:43:28

induction

induction

ziv
2010-06-15 20:43:28

ohhh strong induction! (I did the inclusion/exclusion thing)

ohhh strong induction! (I did the inclusion/exclusion thing)

Great Spheres
2010-06-15 20:43:28

But we split it into parity-cases

But we split it into parity-cases

MeowmixOX;D
2010-06-15 20:43:28

induction?

induction?

smartkid11235813
2010-06-15 20:43:28

prove all n are divisable by 6, strong induction

prove all n are divisable by 6, strong induction

Titandrake
2010-06-15 20:43:28

you can build up from the given table

you can build up from the given table

kevin7
2010-06-15 20:43:28

a_1 and a_2 are 2 mod 6, use strong induction to prove conjecture a

a_1 and a_2 are 2 mod 6, use strong induction to prove conjecture a

L2gB
2010-06-15 20:43:28

prove it is divisible by 6, so 2 and 3

prove it is divisible by 6, so 2 and 3

Shortgeek
2010-06-15 20:43:28

(strong) induction on the fact that a_n (mod 6) == 0

(strong) induction on the fact that a_n (mod 6) == 0

MJStone
2010-06-15 20:43:33

Well, 2^n - 2^2 is always a multiple of 6 for even ns, and 2^n - 2^1 for odd ns.

Well, 2^n - 2^2 is always a multiple of 6 for even ns, and 2^n - 2^1 for odd ns.

chhan92
2010-06-15 20:43:39

find the each piece modulo 6 and add them up to prove that it is indeed modular to 0

find the each piece modulo 6 and add them up to prove that it is indeed modular to 0

DanZ
2010-06-15 20:43:41

DanZ
2010-06-15 20:43:47

We must divide into two cases: n odd and n even.

We must divide into two cases: n odd and n even.

DanZ
2010-06-15 20:43:49

Case 1: n odd

Case 1: n odd

DanZ
2010-06-15 20:43:54

kevin7
2010-06-15 20:44:30

2

2

DanielC
2010-06-15 20:44:31

2

2

Shortgeek
2010-06-15 20:44:31

2! (which equals 2 if you are less happy)

2! (which equals 2 if you are less happy)

smartkid11235813
2010-06-15 20:44:31

2

2

MJStone
2010-06-15 20:44:31

2

2

professordad
2010-06-15 20:44:31

two

two

Iamerror
2010-06-15 20:44:31

2

2

MeowmixOX;D
2010-06-15 20:44:31

2

2

Titandrake
2010-06-15 20:44:31

2

2

Great Spheres
2010-06-15 20:44:33

2^n when divided by 6 is always 2 if n is odd

2^n when divided by 6 is always 2 if n is odd

DanZ
2010-06-15 20:44:35

MJStone
2010-06-15 20:45:12

2

2

Shortgeek
2010-06-15 20:45:12

2 as well

2 as well

Iamerror
2010-06-15 20:45:12

2

2

Great Spheres
2010-06-15 20:45:12

a1=2, so we subtract 2 there

a1=2, so we subtract 2 there

smartkid11235813
2010-06-15 20:45:12

2

2

DanielC
2010-06-15 20:45:12

2

2

DanZ
2010-06-15 20:45:16

Great Spheres
2010-06-15 20:45:58

and thus we get that an = 2^n - 2 - all other a ds and then because of our inductive hypothesis, the ads disappear, and we get it's congruent to zero, QED.

and thus we get that an = 2^n - 2 - all other a ds and then because of our inductive hypothesis, the ads disappear, and we get it's congruent to zero, QED.

kevin7
2010-06-15 20:45:58

all the factors of n, which we assumed were 0 mod 6. we don't subtract a_2, so we're done for this case.

all the factors of n, which we assumed were 0 mod 6. we don't subtract a_2, so we're done for this case.

MJStone
2010-06-15 20:45:58

Only factors where d>=3

Only factors where d>=3

Iamerror
2010-06-15 20:45:58

a(other factors)

a(other factors)

Shortgeek
2010-06-15 20:45:58

well, we DON'T subtract a_2, so assuming the inductive hypothesis, a bunch of things that are 0 mod 6

well, we DON'T subtract a_2, so assuming the inductive hypothesis, a bunch of things that are 0 mod 6

DanZ
2010-06-15 20:46:03

ziv
2010-06-15 20:46:05

a bunch of multiples of 6

a bunch of multiples of 6

DanZ
2010-06-15 20:46:10

Case 2: n even

Case 2: n even

DanZ
2010-06-15 20:46:16

professordad
2010-06-15 20:47:05

a_2

a_2

kevin7
2010-06-15 20:47:05

we subtract both a_1 and a_2, getting 0 mod 6 again.

we subtract both a_1 and a_2, getting 0 mod 6 again.

Shortgeek
2010-06-15 20:47:05

we DO subtract off a_2, for an extra -2 bringing it down to 0

we DO subtract off a_2, for an extra -2 bringing it down to 0

Iamerror
2010-06-15 20:47:05

we must subtract off a(2) as well

we must subtract off a(2) as well

Great Spheres
2010-06-15 20:47:05

Yes! We get also that we need a2, which is congruent also to 2 modulo six

Yes! We get also that we need a2, which is congruent also to 2 modulo six

DanielC
2010-06-15 20:47:05

we must subtract a_2 = 2

we must subtract a_2 = 2

Titandrake
2010-06-15 20:47:05

subtract a1 and a2

subtract a1 and a2

MJStone
2010-06-15 20:47:05

Whoops, a_2

Whoops, a_2

aaronlandesman
2010-06-15 20:47:10

n is divisible by both 1 and 2

n is divisible by both 1 and 2

L2gB
2010-06-15 20:47:10

we subtract another 2 because n is divisable by 2

we subtract another 2 because n is divisable by 2

MJStone
2010-06-15 20:47:10

Add back in 2^1 of course :)

Add back in 2^1 of course :)

smartkid11235813
2010-06-15 20:47:17

subtracting 4=A(2), thus you get a(n)=0 (mod 6)

subtracting 4=A(2), thus you get a(n)=0 (mod 6)

Great Spheres
2010-06-15 20:47:17

So we get an = 2^n - 2 - 2 - ads and then because n is even 2^n is congruent to 4, so we get that this is simply 4 - 2 - 2 - 0 - ... which is zero (inductive hypothesis).

So we get an = 2^n - 2 - 2 - ads and then because n is even 2^n is congruent to 4, so we get that this is simply 4 - 2 - 2 - 0 - ... which is zero (inductive hypothesis).

DanZ
2010-06-15 20:47:19

DanZ
2010-06-15 20:47:27

Thus, a_n is divisible by 6 for all n greater than 2.

Thus, a_n is divisible by 6 for all n greater than 2.

DanZ
2010-06-15 20:47:34

That's part (a).

That's part (a).

DanZ
2010-06-15 20:47:42

Part (b)

Part (b)

DanZ
2010-06-15 20:47:49

DanZ
2010-06-15 20:48:14

Titandrake
2010-06-15 20:49:19

find the max value of all the a_d added together

find the max value of all the a_d added together

Shortgeek
2010-06-15 20:49:19

put upper and lower bounds on a_n; 2^n and 2^n - 2^(n+1/2) respectively

put upper and lower bounds on a_n; 2^n and 2^n - 2^(n+1/2) respectively

ziv
2010-06-15 20:49:19

ziv
2010-06-15 20:49:19

then squeeze theorem!

then squeeze theorem!

Great Spheres
2010-06-15 20:49:19

I said b_n = the sum of a_ds (ds are factors of n), and then said I think I did a proof by contradiction

I said b_n = the sum of a_ds (ds are factors of n), and then said I think I did a proof by contradiction

DanZ
2010-06-15 20:49:30

Here's my suggestion.

Here's my suggestion.

DanZ
2010-06-15 20:49:32

DanZ
2010-06-15 20:49:50

DanZ
2010-06-15 20:49:56

First of all, can someone give me a bound on what d is?

First of all, can someone give me a bound on what d is?

smartkid11235813
2010-06-15 20:50:52

d<=n/2

d<=n/2

MJStone
2010-06-15 20:50:52

1 through n/2

1 through n/2

Titandrake
2010-06-15 20:50:52

d less or equal to n / 2

d less or equal to n / 2

Shortgeek
2010-06-15 20:50:52

(n+1)/2

(n+1)/2

ziv
2010-06-15 20:50:57

DanZ
2010-06-15 20:51:04

DanZ
2010-06-15 20:51:16

(A really easy upper bound.)

(A really easy upper bound.)

Great Spheres
2010-06-15 20:51:44

2^d

2^d

MJStone
2010-06-15 20:51:44

2^d

2^d

Great Spheres
2010-06-15 20:51:44

or, 2^floor n/2

or, 2^floor n/2

Shortgeek
2010-06-15 20:51:44

2^d

2^d

MJStone
2010-06-15 20:51:44

Because we don't need to be any more precise really

Because we don't need to be any more precise really

smartkid11235813
2010-06-15 20:51:44

2^(n/2)

2^(n/2)

ziv
2010-06-15 20:51:44

Great Spheres
2010-06-15 20:51:44

or, 2^ n/22 if you don't like floors

or, 2^ n/22 if you don't like floors

aaronlandesman
2010-06-15 20:51:44

2^d

2^d

Iamerror
2010-06-15 20:51:47

2^(n/2)

2^(n/2)

DanZ
2010-06-15 20:51:49

DanZ
2010-06-15 20:52:18

(If so, to what?)

(If so, to what?)

MJStone
2010-06-15 20:53:07

Assume n/2 is an integer, then geometric series

Assume n/2 is an integer, then geometric series

smartkid11235813
2010-06-15 20:53:07

2^(n/2+1)

2^(n/2+1)

Shortgeek
2010-06-15 20:53:07

absolutely. We know that floor(n/2) < n/2, so we sum the geometric series to 2^(n/2 + 1) - 1

absolutely. We know that floor(n/2) < n/2, so we sum the geometric series to 2^(n/2 + 1) - 1

DanZ
2010-06-15 20:53:10

DanZ
2010-06-15 20:53:23

DanZ
2010-06-15 20:53:39

Incidentally, a number of you used other approaches.

Incidentally, a number of you used other approaches.

DanZ
2010-06-15 20:53:48

I do remember a few with the squeeze theorem that worked out, although there were also some with errors.

I do remember a few with the squeeze theorem that worked out, although there were also some with errors.

DanZ
2010-06-15 20:54:01

A number of quizzes tried using l'Hopital's rule, but I'm afraid this was usually doomed to failure.

A number of quizzes tried using l'Hopital's rule, but I'm afraid this was usually doomed to failure.

DanZ
2010-06-15 20:54:19

The problem was that even if you took a term-by-term derivative of the top and bottom, the number of terms itself changes as n changes, and so your derivative fails!

The problem was that even if you took a term-by-term derivative of the top and bottom, the number of terms itself changes as n changes, and so your derivative fails!

DanZ
2010-06-15 20:54:36

Thus, l'Hopital is not so helpful here.

Thus, l'Hopital is not so helpful here.

DanZ
2010-06-15 20:54:40

Anyway, questions about this problem?

Anyway, questions about this problem?

DanZ
2010-06-15 20:55:44

Problem 6: T(x)

Problem 6: T(x)

DanZ
2010-06-15 20:55:54

DanZ
2010-06-15 20:55:58

What kind of sequence is embedded within f(x)?

What kind of sequence is embedded within f(x)?

hcs
2010-06-15 20:56:38

it's geometric

it's geometric

ziv
2010-06-15 20:56:38

geometric

geometric

gh625
2010-06-15 20:56:38

geometric

geometric

Great Spheres
2010-06-15 20:56:38

a geometric

a geometric

Arouet
2010-06-15 20:56:38

geometric(ish)

geometric(ish)

professordad
2010-06-15 20:56:38

geometric

geometric

kevin7
2010-06-15 20:56:38

A geometric? but the 1-x thing messes it up...

A geometric? but the 1-x thing messes it up...

smartkid11235813
2010-06-15 20:56:38

geometric?

geometric?

Shortgeek
2010-06-15 20:56:38

geometric -- but actually two geometrics and an arithmetic, which makes it evil

geometric -- but actually two geometrics and an arithmetic, which makes it evil

Great Spheres
2010-06-15 20:56:38

After some point it actuall IS a geometric sequence.

After some point it actuall IS a geometric sequence.

DanZ
2010-06-15 20:56:41

DanZ
2010-06-15 20:56:52

DanZ
2010-06-15 20:57:36

Actually, don't bother typing it out, it's just the geometric series formula.

Actually, don't bother typing it out, it's just the geometric series formula.

DanZ
2010-06-15 20:57:38

professordad
2010-06-15 20:57:43

DanZ
2010-06-15 20:57:48

Ok, actually, thank you for doing that!

Ok, actually, thank you for doing that!

DanZ
2010-06-15 20:57:55

Anyway, how would we get the first sum?

Anyway, how would we get the first sum?

Shortgeek
2010-06-15 20:58:51

N-1 - (geometric series)

N-1 - (geometric series)

ziv
2010-06-15 20:58:51

split it into the sum of the 1's and sum of the x^n's

split it into the sum of the 1's and sum of the x^n's

Shortgeek
2010-06-15 20:58:51

(N-1) - [(1-x^N)/(1-x)]

(N-1) - [(1-x^N)/(1-x)]

smartkid11235813
2010-06-15 20:58:51

split it up into 1 and -x^n

split it up into 1 and -x^n

DanielC
2010-06-15 20:58:54

pull out N-1*1

pull out N-1*1

DanZ
2010-06-15 20:58:58

DanZ
2010-06-15 20:59:14

Great Spheres
2010-06-15 20:59:33

We need some idea of N for that though

We need some idea of N for that though

DanZ
2010-06-15 20:59:48

Very good point. But we have one; we chose N so that x^N <= 1/2 < x^{N - 1}.

Very good point. But we have one; we chose N so that x^N <= 1/2 < x^{N - 1}.

DanZ
2010-06-15 21:00:06

So you should use that in bounding this fraction.

So you should use that in bounding this fraction.

Shortgeek
2010-06-15 21:00:41

x^N is less than 1/2, so it's less than 1 - x / 1-x = 1

x^N is less than 1/2, so it's less than 1 - x / 1-x = 1

MJStone
2010-06-15 21:00:41

1

1

Iamerror
2010-06-15 21:00:41

1

1

quadraticfanatic
2010-06-15 21:00:41

the greatest it can get is one!!!

the greatest it can get is one!!!

DanZ
2010-06-15 21:00:45

DanZ
2010-06-15 21:00:50

aaronlandesman
2010-06-15 21:01:50

well then this fraction is positive

well then this fraction is positive

Iamerror
2010-06-15 21:01:50

0

0

ziv
2010-06-15 21:01:50

it can be down to N-1, but not including it

it can be down to N-1, but not including it

Shortgeek
2010-06-15 21:01:50

if x = 0, it can be 0 -- but both terms are necessarily nonnegative (though it's ugly to prove that for the top) so it's at least 0.

if x = 0, it can be 0 -- but both terms are necessarily nonnegative (though it's ugly to prove that for the top) so it's at least 0.

chhan92
2010-06-15 21:01:52

0

0

DanZ
2010-06-15 21:01:55

DanZ
2010-06-15 21:02:08

DanielC
2010-06-15 21:03:19

x must be a nth root of 2

x must be a nth root of 2

DanielC
2010-06-15 21:03:19

*1/2

*1/2

ziv
2010-06-15 21:03:19

Shortgeek
2010-06-15 21:03:19

if x^N = 1/2 or if x^N = x/2

if x^N = 1/2 or if x^N = x/2

DanZ
2010-06-15 21:03:24

DanZ
2010-06-15 21:03:30

(Which is equivalent to many of the conditions you gave.)

(Which is equivalent to many of the conditions you gave.)

DanZ
2010-06-15 21:03:36

professordad
2010-06-15 21:04:39

N = 2010 :D

N = 2010 :D

MJStone
2010-06-15 21:04:39

It's 2010

It's 2010

Shortgeek
2010-06-15 21:04:39

N = 2010

N = 2010

Great Spheres
2010-06-15 21:04:39

N is 2010

N is 2010

smartkid11235813
2010-06-15 21:04:45

N=2010

N=2010

DanZ
2010-06-15 21:04:48

Great Spheres
2010-06-15 21:05:45

x^2010=1/2

x^2010=1/2

MJStone
2010-06-15 21:05:45

2x^2010 = 1

2x^2010 = 1

DanielC
2010-06-15 21:05:45

x is the 2010th root of 1/2

x is the 2010th root of 1/2

Shortgeek
2010-06-15 21:05:45

if 2x^N - x = 1 -x, x^N = 1/2, and N = 2010 so x = 1/(2^(1/2010))

if 2x^N - x = 1 -x, x^N = 1/2, and N = 2010 so x = 1/(2^(1/2010))

ziv
2010-06-15 21:05:48

aaronlandesman
2010-06-15 21:05:50

just put in N=2010 and solve for x

just put in N=2010 and solve for x

smartkid11235813
2010-06-15 21:05:52

x^n=1/2

x^n=1/2

DanZ
2010-06-15 21:05:57

DanZ
2010-06-15 21:06:12

Questions?/

Questions?/

Shortgeek
2010-06-15 21:07:42

why would you inflict such a monstrosity of algebra upon us?

why would you inflict such a monstrosity of algebra upon us?

DanZ
2010-06-15 21:07:45

Hrm.

Hrm.

DanZ
2010-06-15 21:07:47

Sorry. :(

Sorry. :(

DanZ
2010-06-15 21:08:56

I will say that we do try to include lots of different types of problems.

I will say that we do try to include lots of different types of problems.

DanZ
2010-06-15 21:08:59

Guess this one maybe went too far!

Guess this one maybe went too far!

DanZ
2010-06-15 21:09:06

Problem 7: Dominoes

Problem 7: Dominoes

DanZ
2010-06-15 21:09:14

DanZ
2010-06-15 21:09:20

The first thing to notice is that this problem actually consists of two parts: first, finding the required conditions, and then showing that if those conditions are satisfied then the board can be tiled!

The first thing to notice is that this problem actually consists of two parts: first, finding the required conditions, and then showing that if those conditions are satisfied then the board can be tiled!

DanZ
2010-06-15 21:09:26

A common mistake was to follow the following path. First, you might observe that 2-by-2 squares can be covered by either two horizontal or two vertical dominoes. So far so good. Then you can take a 2m-by-2n board and cover it by 2-by-2 squares; since you need to have an equal number of horizontal and vertical dominoes, the number of 2-by-2 squares must be even, so you conclude that all boards must be 4m-by-2n or 2m-by-4n. Where this goes wrong is that you failed to prove that one of these is actually necessary, and you failed to prove it for a good reason: it's not necessary! A little experimentation would show, for example, that a 3-by-8 board can be tiled.

A common mistake was to follow the following path. First, you might observe that 2-by-2 squares can be covered by either two horizontal or two vertical dominoes. So far so good. Then you can take a 2m-by-2n board and cover it by 2-by-2 squares; since you need to have an equal number of horizontal and vertical dominoes, the number of 2-by-2 squares must be even, so you conclude that all boards must be 4m-by-2n or 2m-by-4n. Where this goes wrong is that you failed to prove that one of these is actually necessary, and you failed to prove it for a good reason: it's not necessary! A little experimentation would show, for example, that a 3-by-8 board can be tiled.

DanZ
2010-06-15 21:09:45

Let's go through both parts of this problem carefully.

Let's go through both parts of this problem carefully.

DanZ
2010-06-15 21:09:50

Part 1: Finding the necessary conditions

Part 1: Finding the necessary conditions

DanZ
2010-06-15 21:09:57

DanZ
2010-06-15 21:10:19

It turns out that there's a further requirement, that MN must be divisible by 8, but seeing why is somewhat challenging. Can anyone make a suggestion?

It turns out that there's a further requirement, that MN must be divisible by 8, but seeing why is somewhat challenging. Can anyone make a suggestion?

ziv
2010-06-15 21:11:29

we are covering the board in pairs of dominoes: one horizontal and one vertical

we are covering the board in pairs of dominoes: one horizontal and one vertical

ziv
2010-06-15 21:11:29

then color the board in columns....

then color the board in columns....

Shortgeek
2010-06-15 21:11:29

let's paint the board in pretty colors

let's paint the board in pretty colors

ziv
2010-06-15 21:11:29

two colors of columns, alternating... horzontal cover one of each, but verticals cover 2 of the same

two colors of columns, alternating... horzontal cover one of each, but verticals cover 2 of the same

aaronlandesman
2010-06-15 21:11:29

use a "coloring" arguement

use a "coloring" arguement

smartkid11235813
2010-06-15 21:11:31

shade board into rows of black and white

shade board into rows of black and white

DanZ
2010-06-15 21:11:38

kevin7
2010-06-15 21:12:57

one white, one black.

one white, one black.

smartkid11235813
2010-06-15 21:12:57

one of each

one of each

Titandrake
2010-06-15 21:12:57

whtie and black

whtie and black

Great Spheres
2010-06-15 21:12:57

one of each color

one of each color

Iamerror
2010-06-15 21:12:57

one of each color

one of each color

nwalton125
2010-06-15 21:12:57

one black, one white

one black, one white

aaronlandesman
2010-06-15 21:12:57

one white, one black

one white, one black

Shortgeek
2010-06-15 21:12:57

one white and one black -- so this means that MN/8 squares are both white and covered by vertical dominoes -- so this means 8 | MN.

one white and one black -- so this means that MN/8 squares are both white and covered by vertical dominoes -- so this means 8 | MN.

Arouet
2010-06-15 21:12:57

1 white 1 black

1 white 1 black

L2gB
2010-06-15 21:12:57

one black and one white?

one black and one white?

MJStone
2010-06-15 21:12:57

Both.

Both.

DanZ
2010-06-15 21:12:59

Each vertical tile covers one black square and one white square. How many black squares are left?

Each vertical tile covers one black square and one white square. How many black squares are left?

hcs
2010-06-15 21:13:46

MN/4

MN/4

nwalton125
2010-06-15 21:13:46

MN/4

MN/4

kevin7
2010-06-15 21:13:46

MN/4 of each color.

MN/4 of each color.

MJStone
2010-06-15 21:13:46

MN/4

MN/4

Titandrake
2010-06-15 21:13:46

there are MN/4 vertical dominoes, so MN/4 of each

there are MN/4 vertical dominoes, so MN/4 of each

DanZ
2010-06-15 21:13:50

DanZ
2010-06-15 21:13:59

Now, what color squares does each horizontal tile cover?

Now, what color squares does each horizontal tile cover?

Great Spheres
2010-06-15 21:14:46

two of black or two of white

two of black or two of white

DanielC
2010-06-15 21:14:46

either 2 black or 2 white

either 2 black or 2 white

quadraticfanatic
2010-06-15 21:14:46

two black or two white

two black or two white

Shortgeek
2010-06-15 21:14:46

either both black or both white

either both black or both white

hcs
2010-06-15 21:14:46

two of the same

two of the same

Iamerror
2010-06-15 21:14:46

either 2 black or 2 white

either 2 black or 2 white

Peter92
2010-06-15 21:14:46

two of the same

two of the same

L2gB
2010-06-15 21:14:46

2 black or 2 white

2 black or 2 white

ziv
2010-06-15 21:14:46

2 of either black or white

2 of either black or white

kevin7
2010-06-15 21:14:46

2 of one color...so MN/4 must be divisible by 2, and MN must be divisible by 8!

2 of one color...so MN/4 must be divisible by 2, and MN must be divisible by 8!

professordad
2010-06-15 21:14:46

either 2 black or 2 white

either 2 black or 2 white

Titandrake
2010-06-15 21:14:46

2 black or 2 white

2 black or 2 white

MJStone
2010-06-15 21:14:46

2 of either color

2 of either color

stevenyu10a
2010-06-15 21:14:46

2 blacks or 2 whites

2 blacks or 2 whites

smartkid11235813
2010-06-15 21:14:55

2 white or 2 black

2 white or 2 black

quadraticfanatic
2010-06-15 21:14:55

DanZ
2010-06-15 21:15:03

It covers either two black or two white squares. What does this tell us about MN/4?

It covers either two black or two white squares. What does this tell us about MN/4?

Arouet
2010-06-15 21:15:25

even

even

Iamerror
2010-06-15 21:15:25

it must be divisible by 2

it must be divisible by 2

quadraticfanatic
2010-06-15 21:15:25

it is even

it is even

stevenyu10a
2010-06-15 21:15:25

it must be even

it must be even

DanielC
2010-06-15 21:15:25

it must be een

it must be een

Shortgeek
2010-06-15 21:15:25

it is covered in groups of two, so it is divisible by two

it is covered in groups of two, so it is divisible by two

Saphira 7
2010-06-15 21:15:33

divisible by 8

divisible by 8

professordad
2010-06-15 21:15:33

its divisible by 2

its divisible by 2

smartkid11235813
2010-06-15 21:15:33

MN/4 is even

MN/4 is even

DanielC
2010-06-15 21:15:33

*even

*even

ziv
2010-06-15 21:15:33

must be even

must be even

DanZ
2010-06-15 21:15:34

It must be even, because MN/4 black squares are covered by horizontal tiles, each of which covers two black squares. So MN is divisible by 8.

It must be even, because MN/4 black squares are covered by horizontal tiles, each of which covers two black squares. So MN is divisible by 8.

DanZ
2010-06-15 21:15:39

Part 2: Proving that those conditions are sufficient

Part 2: Proving that those conditions are sufficient

DanZ
2010-06-15 21:15:43

Now we need to show that, for any board where each of M and N are at least 2 and MN is divisible by 8, there's a way to tile it as given. Let's do the easy case: what if both M and N are even? How do you tile the board?

Now we need to show that, for any board where each of M and N are at least 2 and MN is divisible by 8, there's a way to tile it as given. Let's do the easy case: what if both M and N are even? How do you tile the board?

Great Spheres
2010-06-15 21:16:32

2x2 squares

2x2 squares

hcs
2010-06-15 21:16:32

divide it into 2x2 squares

divide it into 2x2 squares

MJStone
2010-06-15 21:16:32

Squares

Squares

Peter92
2010-06-15 21:16:32

use 2x4 blocks

use 2x4 blocks

Arouet
2010-06-15 21:16:32

split into 2 by 2 sections

split into 2 by 2 sections

Iamerror
2010-06-15 21:16:32

an equal number of squares of two horizontal or verticle

an equal number of squares of two horizontal or verticle

DanielC
2010-06-15 21:16:32

split it into 2 by 2 squares

split it into 2 by 2 squares

Shortgeek
2010-06-15 21:16:32

the way you showcased at the start -- divide it up into an even number of simple boxes, make half of them covered in vertical and the other half horizontal

the way you showcased at the start -- divide it up into an even number of simple boxes, make half of them covered in vertical and the other half horizontal

ziv
2010-06-15 21:16:32

you can use a number of 2x4 "big dominoes"

you can use a number of 2x4 "big dominoes"

DanZ
2010-06-15 21:16:36

quadraticfanatic
2010-06-15 21:16:38

in squares of 2x2, alternating two horizontal and two vertical

in squares of 2x2, alternating two horizontal and two vertical

DanZ
2010-06-15 21:16:48

DanZ
2010-06-15 21:17:10

Since we have shown that our conditions are both necessary and sufficient, we have completed the problem.

Since we have shown that our conditions are both necessary and sufficient, we have completed the problem.

DanZ
2010-06-15 21:17:30

Ok. We are troopers. One problem remaining. Questions on this one?

Ok. We are troopers. One problem remaining. Questions on this one?

Shortgeek
2010-06-15 21:18:05

what if they're triominoes?

what if they're triominoes?

DanZ
2010-06-15 21:18:14

You love extending these problems. I'm afraid that again, I haven't considered it!

You love extending these problems. I'm afraid that again, I haven't considered it!

DanZ
2010-06-15 21:18:38

The truth is that I spent a

The truth is that I spent a

*lot*of time looking specifically at these versions of the problems, first in writing and then in solving and then in reviewing your solutions. :)
DanZ
2010-06-15 21:18:51

It's a good question, though!

It's a good question, though!

DanZ
2010-06-15 21:19:15

Problem 8: Higher-Dimensional Checkerboard

Problem 8: Higher-Dimensional Checkerboard

DanZ
2010-06-15 21:19:23

If we tile the plane with black and white squares in a regular checkerboard pattern, then every square has an equal number (four) of black and white neighbors. (Two squares are considered neighbors if they are not the same but have at least one common point; squares that touch just at a vertex count as neighbors.) But if we try the analogous pattern of cubes in 3-dimensional space, it no longer works this way.

If we tile the plane with black and white squares in a regular checkerboard pattern, then every square has an equal number (four) of black and white neighbors. (Two squares are considered neighbors if they are not the same but have at least one common point; squares that touch just at a vertex count as neighbors.) But if we try the analogous pattern of cubes in 3-dimensional space, it no longer works this way.

DanZ
2010-06-15 21:19:34

(a) How many neighbors of each color does a white cube have?

(a) How many neighbors of each color does a white cube have?

DanZ
2010-06-15 21:19:39

This basically involves visualizing. What is the answer?

This basically involves visualizing. What is the answer?

ziv
2010-06-15 21:20:35

12

12

Iamerror
2010-06-15 21:20:35

12

12

Great Spheres
2010-06-15 21:20:35

12

12

gh625
2010-06-15 21:20:35

12W 14B

12W 14B

L2gB
2010-06-15 21:20:35

14 black cubes and 12 white cubes

14 black cubes and 12 white cubes

kevin7
2010-06-15 21:20:35

14 black, 12 white

14 black, 12 white

DanielC
2010-06-15 21:20:35

no... 14 black and 12 white

no... 14 black and 12 white

Peter92
2010-06-15 21:20:35

14 black 12 white

14 black 12 white

math911
2010-06-15 21:20:35

14 black, 12 white?

14 black, 12 white?

Shortgeek
2010-06-15 21:20:35

14 black and 12 white -- a very diverse neighborhood, but not good enough

14 black and 12 white -- a very diverse neighborhood, but not good enough

visheshk
2010-06-15 21:20:35

14 black and 12 white

14 black and 12 white

smartkid11235813
2010-06-15 21:20:35

12

12

Iamerror
2010-06-15 21:20:35

*of white and 14 of black

*of white and 14 of black

stevenyu10a
2010-06-15 21:20:35

12/14

12/14

DanZ
2010-06-15 21:20:49

It is 12 white, 14 black. To see this, consider one plane of cubes on the same level as your center white cube; another plane above it, reversed; and another plane below it, also reversed. On the same level, you have four white neighbors as stated in the problem. One level above, you also have four white cubes, and one level below, you also have four white cubes. Giving twelve total.

It is 12 white, 14 black. To see this, consider one plane of cubes on the same level as your center white cube; another plane above it, reversed; and another plane below it, also reversed. On the same level, you have four white neighbors as stated in the problem. One level above, you also have four white cubes, and one level below, you also have four white cubes. Giving twelve total.

DanZ
2010-06-15 21:21:09

You can do the same visualization with black, of course, or subtract from 26 total neighbors.

You can do the same visualization with black, of course, or subtract from 26 total neighbors.

DanZ
2010-06-15 21:21:18

(b) Find a coloring pattern for a grid of cubes in 3-dimensional space so that every cube, whether black or white, has an equal number of black and white neighbors.

(b) Find a coloring pattern for a grid of cubes in 3-dimensional space so that every cube, whether black or white, has an equal number of black and white neighbors.

DanZ
2010-06-15 21:21:26

Go ahead and post your coloring patterns; I'll pass them on. (If you can describe them easily.)

Go ahead and post your coloring patterns; I'll pass them on. (If you can describe them easily.)

DanZ
2010-06-15 21:22:00

(I'll give you a quick minute. You may also want to prep anything you want to say for part (c). I realize you may not all have time to write up your solutions, so I apologize, but there isn't really a way around it.)

(I'll give you a quick minute. You may also want to prep anything you want to say for part (c). I realize you may not all have time to write up your solutions, so I apologize, but there isn't really a way around it.)

DanielC
2010-06-15 21:23:19

tile with 2 by 1 by 1 blocks of each color

tile with 2 by 1 by 1 blocks of each color

Iamerror
2010-06-15 21:23:19

(BBWW) repeat

(BBWW) repeat

sachiroo
2010-06-15 21:23:19

I used a double checkerboard- so 2x1 black and white rectangles tiling the plane.

I used a double checkerboard- so 2x1 black and white rectangles tiling the plane.

L2gB
2010-06-15 21:23:19

alternate colors vertically only every other time

alternate colors vertically only every other time

kevin7
2010-06-15 21:23:19

Instead of with the checkerboard, inverting it every level (like 101010...) invert it every other level (11001100...).

Instead of with the checkerboard, inverting it every level (like 101010...) invert it every other level (11001100...).

visheshk
2010-06-15 21:23:19

we extend the chess board so that each column has the same colour of cubes

we extend the chess board so that each column has the same colour of cubes

Shortgeek
2010-06-15 21:23:19

2x2x2 cubes in a checkerboard pattern

2x2x2 cubes in a checkerboard pattern

abcak
2010-06-15 21:23:19

"rows" 1, 4, 5, 8 checkerboard, 2, 3, 6, 7 reverse checkerboard, etc.

"rows" 1, 4, 5, 8 checkerboard, 2, 3, 6, 7 reverse checkerboard, etc.

Arouet
2010-06-15 21:23:19

build up layers by shifting every second subsequent layer such that each cube have a different coloured cube either right above or below it (but nor both)

build up layers by shifting every second subsequent layer such that each cube have a different coloured cube either right above or below it (but nor both)

visheshk
2010-06-15 21:23:19

and then we change the colours of each cube in every 2nd and third "sheet"

and then we change the colours of each cube in every 2nd and third "sheet"

gh625
2010-06-15 21:23:19

BWBW/BWBW/WBWB/WBWB (the things after the slashes are separate lines)

BWBW/BWBW/WBWB/WBWB (the things after the slashes are separate lines)

soccer22
2010-06-15 21:23:19

checkerboard patterns layered on top of each other so that a stack of cubes going straight up goes white-white-black-black...

checkerboard patterns layered on top of each other so that a stack of cubes going straight up goes white-white-black-black...

aaronlandesman
2010-06-15 21:23:19

In order to color a grid of cubes 3-dimensional space so that every cube

has an equal number of black and white neighbors simply fill space with 2

by 2 by 2 cubes of white and black in the checkerboard patter described in

the problem. Except, instead of 1 by 1 by 1 cubes, they are 2 by 2 by 2. If

we take any cube it will have 7 neighbors of its color in its 2 by 2 by 2 cube.

Additionally are three

In order to color a grid of cubes 3-dimensional space so that every cube

has an equal number of black and white neighbors simply fill space with 2

by 2 by 2 cubes of white and black in the checkerboard patter described in

the problem. Except, instead of 1 by 1 by 1 cubes, they are 2 by 2 by 2. If

we take any cube it will have 7 neighbors of its color in its 2 by 2 by 2 cube.

Additionally are three

MJStone
2010-06-15 21:23:19

Sorry, grouping them in 2. Should have solutions here :P

Sorry, grouping them in 2. Should have solutions here :P

Titandrake
2010-06-15 21:23:19

Divide the space into planes. Designate a center point for each plane. Each plane is a checkerboard pattern. The centers alternate black, black, white, white. The proof might take too long to type here...

Divide the space into planes. Designate a center point for each plane. Each plane is a checkerboard pattern. The centers alternate black, black, white, white. The proof might take too long to type here...

ziv
2010-06-15 21:23:19

We start with a pattern that gives us an equal number of black and white neighbors for a 2-dimensional grid. We can make the same pattern with a grid of cubes that has a height of 1. (Another way to think about it is ”thickening” the 2-dimensional grid into 3 dimensions.) Call this a layer. Layers should be arranged such that each layer is an inversion of the one 2 above or below itself.

We start with a pattern that gives us an equal number of black and white neighbors for a 2-dimensional grid. We can make the same pattern with a grid of cubes that has a height of 1. (Another way to think about it is ”thickening” the 2-dimensional grid into 3 dimensions.) Call this a layer. Layers should be arranged such that each layer is an inversion of the one 2 above or below itself.

MJStone
2010-06-15 21:23:25

Invert every other group of two planes. So, moving through parallel planes, you have IINNII

Invert every other group of two planes. So, moving through parallel planes, you have IINNII

avec_une_h
2010-06-15 21:23:49

checker larger (2 by 2 by 2) cubes made up of 4 cubes of the same color

checker larger (2 by 2 by 2) cubes made up of 4 cubes of the same color

abcak
2010-06-15 21:23:49

with C, you can make "rows" 1, 4, 5, and 8 a successful coloring pattern in the lower demension, etc...

with C, you can make "rows" 1, 4, 5, and 8 a successful coloring pattern in the lower demension, etc...

DanZ
2010-06-15 21:23:52

DanZ
2010-06-15 21:24:09

To see this, observe that each cube is at the corner point of eight such larger 2-cubes (corresponding to the eight octants of 3-dimensional space). Suppose the cube is white. Then it has 7 white neighbors within its own 2-cube. It shares a face with three black 2-cubes that contribute nothing; it shares an edge with three white 2-cubes, each contributing 2 more white cubes in adjacency each, and it shares a vertex with a black 2-cube contributing nothing. Thus in total we have 7+6 = 13 white cubes that are adjacent. That is half of 26 adjacent cubes, so the remaining 13 are black as required. Because this setup is symmetric in black and white, black cubes also have 13 white and 13 black adjacent cubes.

To see this, observe that each cube is at the corner point of eight such larger 2-cubes (corresponding to the eight octants of 3-dimensional space). Suppose the cube is white. Then it has 7 white neighbors within its own 2-cube. It shares a face with three black 2-cubes that contribute nothing; it shares an edge with three white 2-cubes, each contributing 2 more white cubes in adjacency each, and it shares a vertex with a black 2-cube contributing nothing. Thus in total we have 7+6 = 13 white cubes that are adjacent. That is half of 26 adjacent cubes, so the remaining 13 are black as required. Because this setup is symmetric in black and white, black cubes also have 13 white and 13 black adjacent cubes.

DanZ
2010-06-15 21:24:42

Ok, that's (b).

Ok, that's (b).

DanZ
2010-06-15 21:24:50

(c) What happens in $n$-dimensional space for $n>3$? Is it still possible to find a color pattern for a grid of hypercubes, so that every hypercube, whether black or white, has an equal number of black and white neighbors?

(c) What happens in $n$-dimensional space for $n>3$? Is it still possible to find a color pattern for a grid of hypercubes, so that every hypercube, whether black or white, has an equal number of black and white neighbors?

DanZ
2010-06-15 21:24:56

Ack, that wasn't LaTeXed.

Ack, that wasn't LaTeXed.

DanZ
2010-06-15 21:25:03

DanZ
2010-06-15 21:25:17

So, is it?

So, is it?

hcs
2010-06-15 21:26:29

basically, for even dimension you can do checkerboard, and for odd you can do the way you described but higher dimensional

basically, for even dimension you can do checkerboard, and for odd you can do the way you described but higher dimensional

DanielC
2010-06-15 21:26:29

yes, use the a tiling if n is even and the b tiling if n is odd

yes, use the a tiling if n is even and the b tiling if n is odd

kevin7
2010-06-15 21:26:29

I think so, but it's hard to visualize

I think so, but it's hard to visualize

Iamerror
2010-06-15 21:26:29

yes

yes

hcs
2010-06-15 21:26:29

so yes

so yes

Shortgeek
2010-06-15 21:26:29

2x2x2x2.... hypercubes in a checkerboard pattern, analagously

2x2x2x2.... hypercubes in a checkerboard pattern, analagously

soccer22
2010-06-15 21:26:29

yes!

yes!

aaronlandesman
2010-06-15 21:26:29

i think it is possible once again by making hyper cubes of side legnth 2

i think it is possible once again by making hyper cubes of side legnth 2

Arouet
2010-06-15 21:26:29

yes, juxtapose every second layer of the lower dimension as slices such that an arbitrary hypercube can find an equal number of neighbors of each colour among it’s own layer, one more of the opposite colour on the juxtaposed layer and one more of its own colour on the unshifted layer.

yes, juxtapose every second layer of the lower dimension as slices such that an arbitrary hypercube can find an equal number of neighbors of each colour among it’s own layer, one more of the opposite colour on the juxtaposed layer and one more of its own colour on the unshifted layer.

sachiroo
2010-06-15 21:26:29

For even dimensions the original checkerboard extends, and for odd dimensions, the new one works.

For even dimensions the original checkerboard extends, and for odd dimensions, the new one works.

hcs
2010-06-15 21:26:29

if I understand your tiling correctly

if I understand your tiling correctly

Titandrake
2010-06-15 21:26:29

Yes

Yes

gh625
2010-06-15 21:26:29

Let A_n be an arbitrary n-dimensional tiling which works, and let A'_n be the reverse of that tiling. Then, stack two A_n on top of each other and two A'_n on top of that. Repeat this pattern infinitely in the n+1 dimension.

Let A_n be an arbitrary n-dimensional tiling which works, and let A'_n be the reverse of that tiling. Then, stack two A_n on top of each other and two A'_n on top of that. Repeat this pattern infinitely in the n+1 dimension.

L2gB
2010-06-15 21:26:29

when n is even, follow a reglar checkered pattern. when n is odd, only alternate colors in the nth dimension layers every other time.

when n is even, follow a reglar checkered pattern. when n is odd, only alternate colors in the nth dimension layers every other time.

math911
2010-06-15 21:26:29

If you can find such a universe with greater than 3 dimensions, I'm guessing yes?

If you can find such a universe with greater than 3 dimensions, I'm guessing yes?

turak
2010-06-15 21:26:29

yes

yes

DanZ
2010-06-15 21:26:40

It is indeed still possible. Feel free to contribute your tiling if you like.

It is indeed still possible. Feel free to contribute your tiling if you like.

DanZ
2010-06-15 21:26:47

I'll pause another moment, then show you my tiling and prove that my tiling works.

I'll pause another moment, then show you my tiling and prove that my tiling works.

Shortgeek
2010-06-15 21:27:36

interestingly enough, actually, if you take any pattern that works in n-1 dimensions and double it up invertedly in the nth a la what MJStone was saying (IINNIINN...), the resulting n-dimensional pattern works as well.

interestingly enough, actually, if you take any pattern that works in n-1 dimensions and double it up invertedly in the nth a la what MJStone was saying (IINNIINN...), the resulting n-dimensional pattern works as well.

soccer22
2010-06-15 21:27:36

just use a plain old checkboard pattern except in 4 dimensions

just use a plain old checkboard pattern except in 4 dimensions

Titandrake
2010-06-15 21:27:42

I did the same split into planes idea, but with multiple dimensions each hypercube splits into 3^(n-2) planes, and it gets really messy

I did the same split into planes idea, but with multiple dimensions each hypercube splits into 3^(n-2) planes, and it gets really messy

DanZ
2010-06-15 21:27:45

DanZ
2010-06-15 21:27:54

Let's prove it twice.

Let's prove it twice.

DanZ
2010-06-15 21:27:58

I want to do both proofs because I think it helps show you the different techniques you can use, but the first proof is much easier.

I want to do both proofs because I think it helps show you the different techniques you can use, but the first proof is much easier.

ziv
2010-06-15 21:28:13

assume you can do it for n-1, then alternate that like AABBAABB into n dimensions; within its own layer, a cube has an equal number of neighbors of each color by assumption. The two adjacent layers are opposites, so it will have an equal number of neighbors of each color overall.

assume you can do it for n-1, then alternate that like AABBAABB into n dimensions; within its own layer, a cube has an equal number of neighbors of each color by assumption. The two adjacent layers are opposites, so it will have an equal number of neighbors of each color overall.

DanZ
2010-06-15 21:28:22

This is the basic idea of my first proof, although you have to be careful about one detail.

This is the basic idea of my first proof, although you have to be careful about one detail.

DanZ
2010-06-15 21:28:23

So, the first proof is inductive. Consider the way to create an n-dimensional checkerboard. You layer one checkboard on top of another, reversing the colors of every two layers. We assume that we have proved that the statement holds for the (n-1)-dimensional pattern.

So, the first proof is inductive. Consider the way to create an n-dimensional checkerboard. You layer one checkboard on top of another, reversing the colors of every two layers. We assume that we have proved that the statement holds for the (n-1)-dimensional pattern.

DanZ
2010-06-15 21:28:33

Consider now our n-dimensional case. We have layers of our (n-1)-dimensional pattern which change every *two* layers (giving larger cubes of side-length 2). Given any particular cube, we only need to consider three layers: the layer containing the cube, the layer above, and the layer below.

Consider now our n-dimensional case. We have layers of our (n-1)-dimensional pattern which change every *two* layers (giving larger cubes of side-length 2). Given any particular cube, we only need to consider three layers: the layer containing the cube, the layer above, and the layer below.

DanZ
2010-06-15 21:28:45

In the layer containing the cube, there are an equal number of white and black adjacent cubes by assumption.

In the layer containing the cube, there are an equal number of white and black adjacent cubes by assumption.

DanZ
2010-06-15 21:28:51

For the layers directly above and below the central cube: the cubes adjacent to the central cube consist of the two cubes directly above or below the central cube, plus all cubes adjacent to them on the (n-1)-dimensional plane.

For the layers directly above and below the central cube: the cubes adjacent to the central cube consist of the two cubes directly above or below the central cube, plus all cubes adjacent to them on the (n-1)-dimensional plane.

DanZ
2010-06-15 21:29:06

Suppose without loss of generality that the layer directly above the central cube has the same coloring as the layer containing the central cube. Then we have an equal number of black and white adjacent cubes, plus the cube directly above the central cube which is the same color as the central cube.

Suppose without loss of generality that the layer directly above the central cube has the same coloring as the layer containing the central cube. Then we have an equal number of black and white adjacent cubes, plus the cube directly above the central cube which is the same color as the central cube.

DanZ
2010-06-15 21:29:37

(Sorry, there are a lot of pronouns here. In retrospect, I could have and should have cleaned this text up a bit more!)

(Sorry, there are a lot of pronouns here. In retrospect, I could have and should have cleaned this text up a bit more!)

DanZ
2010-06-15 21:29:45

(In my defense, it was late last night when I was writing it. :))

(In my defense, it was late last night when I was writing it. :))

DanZ
2010-06-15 21:29:46

Then the layer directly below the central cube will have the reversed coloring as the layer containing the central cube. That gives an equal number of black and white adjacent cubes, plus the cube directly below the central cube which is the opposite of the color of the central cube.

Then the layer directly below the central cube will have the reversed coloring as the layer containing the central cube. That gives an equal number of black and white adjacent cubes, plus the cube directly below the central cube which is the opposite of the color of the central cube.

DanZ
2010-06-15 21:30:01

Thus we have an equal number of black and white adjacent cubes!

Thus we have an equal number of black and white adjacent cubes!

DanZ
2010-06-15 21:30:10

Any questions about that proof? Does that make sense?

Any questions about that proof? Does that make sense?

DanZ
2010-06-15 21:30:45

A longer way to do this is with coordinates, and there are many more ways yet. But if you have trouble with visualizing, being able to fall back on coordinates can be very helpful.

A longer way to do this is with coordinates, and there are many more ways yet. But if you have trouble with visualizing, being able to fall back on coordinates can be very helpful.

DanZ
2010-06-15 21:30:49

Sadly, coordinates are also painful.

Sadly, coordinates are also painful.

DanZ
2010-06-15 21:30:58

First we define how to find the coordinates for any cube. Let the coordinates of a cube be given by taking the vertex of the cube that has the smallest Cartesian coordinates. We'll begin with the cube with vertices at (0,0,0,...,0), (1,0,0,...,0), (0,1,0,...,0), etc.; its coordinates are given as (0,0,0,...,0) by this rule.

First we define how to find the coordinates for any cube. Let the coordinates of a cube be given by taking the vertex of the cube that has the smallest Cartesian coordinates. We'll begin with the cube with vertices at (0,0,0,...,0), (1,0,0,...,0), (0,1,0,...,0), etc.; its coordinates are given as (0,0,0,...,0) by this rule.

DanZ
2010-06-15 21:31:08

To figure out the color of any particular cube: take its coordinates; divide each coordinate by 2; take the greatest integer less than each coordinate; add them. If the result is even, color it white; otherwise, color it black.

To figure out the color of any particular cube: take its coordinates; divide each coordinate by 2; take the greatest integer less than each coordinate; add them. If the result is even, color it white; otherwise, color it black.

DanZ
2010-06-15 21:31:19

This matches the coloring I described with words: by dividing by 2 and taking the floor, we break things up into cubes of side-length 2 that will all have the same color. Then the even/odd sum gives exactly a checkerboard color: move over across the n-face of one 2-cube and we change color because parity changes; move over another and we change back

This matches the coloring I described with words: by dividing by 2 and taking the floor, we break things up into cubes of side-length 2 that will all have the same color. Then the even/odd sum gives exactly a checkerboard color: move over across the n-face of one 2-cube and we change color because parity changes; move over another and we change back

DanZ
2010-06-15 21:31:38

What color is the cube with coordinates (0,0,0,...,0)?

What color is the cube with coordinates (0,0,0,...,0)?

Saphira 7
2010-06-15 21:32:27

white

white

visheshk
2010-06-15 21:32:27

white?

white?

turak
2010-06-15 21:32:27

white

white

Iamerror
2010-06-15 21:32:27

white

white

Great Spheres
2010-06-15 21:32:27

white

white

professordad
2010-06-15 21:32:27

white

white

DanZ
2010-06-15 21:32:29

It's white: dividing by 2 gives the same coordinates, summing it gives an even result.

It's white: dividing by 2 gives the same coordinates, summing it gives an even result.

DanZ
2010-06-15 21:32:33

Now we can study its neighbors. Since this cube is generic (we could have centered our coordinate system anywhere, and replacing white with black doesn't change anything), proving that this cube has an equal number of white and black neighbors proves it for all cubes.

Now we can study its neighbors. Since this cube is generic (we could have centered our coordinate system anywhere, and replacing white with black doesn't change anything), proving that this cube has an equal number of white and black neighbors proves it for all cubes.

DanZ
2010-06-15 21:32:49

How many neighbors total does it have?

How many neighbors total does it have?

DanZ
2010-06-15 21:33:21

Hey guys: n dimensions. :)

Hey guys: n dimensions. :)

DanZ
2010-06-15 21:33:49

(Welcome... to the n-th dimension!!! Ahem.)

(Welcome... to the n-th dimension!!! Ahem.)

smartkid11235813
2010-06-15 21:34:04

3^n-1

3^n-1

turak
2010-06-15 21:34:04

3^n-1 where there are n dimensions

3^n-1 where there are n dimensions

Great Spheres
2010-06-15 21:34:04

3^n-1

3^n-1

Arouet
2010-06-15 21:34:04

3^n - 1

3^n - 1

Shortgeek
2010-06-15 21:34:04

3^n - 1

3^n - 1

soccer22
2010-06-15 21:34:04

3^n -1

3^n -1

L2gB
2010-06-15 21:34:04

3^n-1

3^n-1

hcs
2010-06-15 21:34:04

3^n -1

3^n -1

kevin7
2010-06-15 21:34:04

3^n - 1

3^n - 1

howru
2010-06-15 21:34:04

3^n-1

3^n-1

visheshk
2010-06-15 21:34:08

3^n -1

3^n -1

DanZ
2010-06-15 21:34:12

DanZ
2010-06-15 21:34:22

How do we tell, using coordinates, if a cube is its neighbor?

How do we tell, using coordinates, if a cube is its neighbor?

visheshk
2010-06-15 21:35:08

to 0, 1 -1

to 0, 1 -1

kevin7
2010-06-15 21:35:08

Coordinates must be -1, 0, or 1, and they can't all be 0.

Coordinates must be -1, 0, or 1, and they can't all be 0.

MJStone
2010-06-15 21:35:08

All coordinates are in the range -1 to 1

All coordinates are in the range -1 to 1

smartkid11235813
2010-06-15 21:35:08

every coordinate is 1,0,or-1

every coordinate is 1,0,or-1

Great Spheres
2010-06-15 21:35:08

if every coordinate is either the same as, one above, or one below as the central cube's

if every coordinate is either the same as, one above, or one below as the central cube's

Shortgeek
2010-06-15 21:35:08

more usefully, if the maximum coordinate difference is 1

more usefully, if the maximum coordinate difference is 1

Iamerror
2010-06-15 21:35:08

it cannot have any coordinate higher than 1 or lower than -1

it cannot have any coordinate higher than 1 or lower than -1

Arouet
2010-06-15 21:35:08

none of the coordinates vary by more than 1

none of the coordinates vary by more than 1

DanZ
2010-06-15 21:35:10

DanielC
2010-06-15 21:35:11

if it has coordinates which are + or - 1 for any dimention

if it has coordinates which are + or - 1 for any dimention

visheshk
2010-06-15 21:35:16

+1, -1, or 0 onthe co-ordinates

+1, -1, or 0 onthe co-ordinates

DanZ
2010-06-15 21:35:20

Can anyone give me an easy way to tell a black cube from a white cube among the cubes with -1, 0, or 1 as all their coordinates?

Can anyone give me an easy way to tell a black cube from a white cube among the cubes with -1, 0, or 1 as all their coordinates?

DanZ
2010-06-15 21:36:25

A lot of you are counting zero or non-zero coordinates, but that's not quite right.

A lot of you are counting zero or non-zero coordinates, but that's not quite right.

DanZ
2010-06-15 21:36:36

Remember our coloring.

Remember our coloring.

visheshk
2010-06-15 21:36:57

if a change is applied to an odd number of cubes

if a change is applied to an odd number of cubes

visheshk
2010-06-15 21:36:57

the color should change

the color should change

visheshk
2010-06-15 21:36:57

otherwise it shouldn't

otherwise it shouldn't

Great Spheres
2010-06-15 21:36:57

using the algorithm, 0 and 1 don't contribute to the parity; -1/2 floor is -1, so that contributes.

using the algorithm, 0 and 1 don't contribute to the parity; -1/2 floor is -1, so that contributes.

Great Spheres
2010-06-15 21:36:57

So it's based on the parity of the number of -1s

So it's based on the parity of the number of -1s

turak
2010-06-15 21:37:01

count number of -1's

count number of -1's

DanZ
2010-06-15 21:37:08

DanZ
2010-06-15 21:37:17

DanZ
2010-06-15 21:37:48

(This is the key to our proof: we need this to be half the total number of neighbors, in which case exactly half the neighbor cubes are black.)

(This is the key to our proof: we need this to be half the total number of neighbors, in which case exactly half the neighbor cubes are black.)

DanielC
2010-06-15 21:38:51

half of all of them

half of all of them

Shortgeek
2010-06-15 21:38:51

sigma from k = 0 to floor(n/2) of nC2k * 2^(n-2k)

sigma from k = 0 to floor(n/2) of nC2k * 2^(n-2k)

DanZ
2010-06-15 21:38:55

DanZ
2010-06-15 21:39:03

Does anyone know an easy way to find this sum? (Just the overall idea, I'll do the details.)

Does anyone know an easy way to find this sum? (Just the overall idea, I'll do the details.)

DanielC
2010-06-15 21:40:03

binomial expansion

binomial expansion

Shortgeek
2010-06-15 21:40:03

swap nC0 with nCn... that is, k with n - k

swap nC0 with nCn... that is, k with n - k

DanZ
2010-06-15 21:40:06

DanZ
2010-06-15 21:40:17

Shortgeek
2010-06-15 21:41:09

counted ourself, egotistical jerk that we are

counted ourself, egotistical jerk that we are

Peter92
2010-06-15 21:41:09

we counted the cube we were referencing to?

we counted the cube we were referencing to?

hcs
2010-06-15 21:41:09

are you counting the cube that you're choosing the neighbors from?

are you counting the cube that you're choosing the neighbors from?

Iamerror
2010-06-15 21:41:09

we counted the center cube?

we counted the center cube?

smartkid11235813
2010-06-15 21:41:09

counted the center with coordinates 0,0,0,0,0.....

counted the center with coordinates 0,0,0,0,0.....

kevin7
2010-06-15 21:41:09

you're counting the (0,0,0...) cube

you're counting the (0,0,0...) cube

Great Spheres
2010-06-15 21:41:09

You need to take out the central cube]

You need to take out the central cube]

chhan92
2010-06-15 21:41:09

forgot to exclude the very center cube (0,0,...,0)

forgot to exclude the very center cube (0,0,...,0)

avec_une_h
2010-06-15 21:41:12

we counted the white cube in the center

we counted the white cube in the center

DanZ
2010-06-15 21:41:15

caffeineboy
2010-06-15 21:41:24

Yay.

Yay.

DanZ
2010-06-15 21:41:41

Yeah, I do kind-of have to apologize that the final proof there was a bit messy. But I wanted to show you several ways of doing it, and this one is really precise.

Yeah, I do kind-of have to apologize that the final proof there was a bit messy. But I wanted to show you several ways of doing it, and this one is really precise.

DanZ
2010-06-15 21:41:50

It also shows how to bring in many different mathematical techniques from your toolset.

It also shows how to bring in many different mathematical techniques from your toolset.

Great Spheres
2010-06-15 21:41:52

I actually like this solution better

I actually like this solution better

MJStone
2010-06-15 21:41:52

Very nice solution

Very nice solution

DanZ
2010-06-15 21:41:55

Thank you!

Thank you!

MJStone
2010-06-15 21:42:00

A little messy, but the other one is inevitably too wordy

A little messy, but the other one is inevitably too wordy

DanZ
2010-06-15 21:42:02

Hehe.

Hehe.

DanZ
2010-06-15 21:42:06

So, questions on problem 8?

So, questions on problem 8?

Great Spheres
2010-06-15 21:42:31

n colors?

n colors?

Great Spheres
2010-06-15 21:42:31

or, sorry, use a different variable for that, maybe r

or, sorry, use a different variable for that, maybe r

DanZ
2010-06-15 21:42:36

Oh goodness... I have no idea.

Oh goodness... I have no idea.

DanZ
2010-06-15 21:42:38

Oh, wait!

Oh, wait!

DanZ
2010-06-15 21:42:46

I forgot. I did get a comment from the person who read most of these with his feedback.

I forgot. I did get a comment from the person who read most of these with his feedback.

DanZ
2010-06-15 21:42:56

Literally about half an hour ago --- he asked me if it was "too late" to contribute to the Math Jam.

Literally about half an hour ago --- he asked me if it was "too late" to contribute to the Math Jam.

DanZ
2010-06-15 21:43:17

He wrote:

He wrote:

DanZ
2010-06-15 21:43:18

This is one thing I would like to tell students: don't extrapolate

from two data points (à la http://xkcd.com/605/) unless you can see a

specific reason in the structure of the problem why this would work

(in which case, you basically have a proof by induction, so go ahead).

This is one thing I would like to tell students: don't extrapolate

from two data points (à la http://xkcd.com/605/) unless you can see a

specific reason in the structure of the problem why this would work

(in which case, you basically have a proof by induction, so go ahead).

Peter92
2010-06-15 21:43:34

can you explain how the binomial theorem simplification was done?

can you explain how the binomial theorem simplification was done?

DanZ
2010-06-15 21:43:44

The signs caused every-other-term in the expansion to cancel.

The signs caused every-other-term in the expansion to cancel.

DanZ
2010-06-15 21:43:48

From the (-1)^n.

From the (-1)^n.

DanZ
2010-06-15 21:43:58

The others were added twice with positive coefficients, so we had to divide by 2.

The others were added twice with positive coefficients, so we had to divide by 2.

Shortgeek
2010-06-15 21:44:05

what was your favorite approach you didn't anticipate?

what was your favorite approach you didn't anticipate?

DanZ
2010-06-15 21:44:33

I mostly looked at question 4, and I think the approaches were generally similar. But the inclusion/exclusion solution where you subtract of 2^d for each d dividing n, then add back in, etc.... I was really impressed when it worked.

I mostly looked at question 4, and I think the approaches were generally similar. But the inclusion/exclusion solution where you subtract of 2^d for each d dividing n, then add back in, etc.... I was really impressed when it worked.

L2gB
2010-06-15 21:44:38

so, were there a lot of possible answers?

so, were there a lot of possible answers?

DanZ
2010-06-15 21:44:40

Always.

Always.

Great Spheres
2010-06-15 21:44:50

It's very similar to the idea of the exponential expansion of the trig functions, where you get every other term to cancel

It's very similar to the idea of the exponential expansion of the trig functions, where you get every other term to cancel

DanZ
2010-06-15 21:44:53

*nod*

*nod*

DanZ
2010-06-15 21:44:56

Any more overall questions?

Any more overall questions?

professordad
2010-06-15 21:45:06

which problem did you like the most

which problem did you like the most

DanZ
2010-06-15 21:45:32

I don't know... I enjoyed many of them. I think I particularly enjoyed 3 and 8.

I don't know... I enjoyed many of them. I think I particularly enjoyed 3 and 8.

DanZ
2010-06-15 21:45:37

(Correction to the above: I graded 5, not 4.)

(Correction to the above: I graded 5, not 4.)

hcs
2010-06-15 21:45:44

do you have any advice in general for people who didn't get in?

do you have any advice in general for people who didn't get in?

hcs
2010-06-15 21:45:44

specifically regarding the quiz

specifically regarding the quiz

DanZ
2010-06-15 21:45:59

First of all, MC is ridiculously competitive and there are lots of very good options out there. We especially got a lot of applications this year.

First of all, MC is ridiculously competitive and there are lots of very good options out there. We especially got a lot of applications this year.

DanZ
2010-06-15 21:46:16

Take a look over your solutions and see how they compare to here. What did you leave out that I included? Where did you forget important details to the problem?

Take a look over your solutions and see how they compare to here. What did you leave out that I included? Where did you forget important details to the problem?

DanZ
2010-06-15 21:46:40

Then think about those for next year. And in general, be relaxed --- like I said, there are so many good things to do, MC is very special, but there are many very special opportunities.

Then think about those for next year. And in general, be relaxed --- like I said, there are so many good things to do, MC is very special, but there are many very special opportunities.

ziv
2010-06-15 21:46:42

that's why servers were down :)

that's why servers were down :)

DanZ
2010-06-15 21:47:10

Yeah, so that's kind-of funny. It turns out that if you copy/paste from a Word document, some of the special characters turn into database queries that extract some huge amount of data and basically make the database many many megabytes in size.

Yeah, so that's kind-of funny. It turns out that if you copy/paste from a Word document, some of the special characters turn into database queries that extract some huge amount of data and basically make the database many many megabytes in size.

DanZ
2010-06-15 21:47:13

We're going to fix that for next year.

We're going to fix that for next year.

DanZ
2010-06-15 21:47:15

*sigh*

*sigh*

DanZ
2010-06-15 21:47:19

(We thought we'd fixed it for this year!)

(We thought we'd fixed it for this year!)

MJStone
2010-06-15 21:47:22

Where will the transcript be?

Where will the transcript be?

DanZ
2010-06-15 21:47:35

I will both link it from the Mathcamp forum and it'll be linked on the list of all AoPS Math Jam transcripts.

I will both link it from the Mathcamp forum and it'll be linked on the list of all AoPS Math Jam transcripts.

Shortgeek
2010-06-15 21:47:44

how careful is too careful, in terms of how much detail to include in a proof?

how careful is too careful, in terms of how much detail to include in a proof?

DanZ
2010-06-15 21:48:05

I'd look at the samples I gave here. They gave the right amount of detail.

I'd look at the samples I gave here. They gave the right amount of detail.

DanZ
2010-06-15 21:48:22

You don't need to include calculations; we don't really care. But you do need to show us any step that someone couldn't easily figure out and explain your reasoning.

You don't need to include calculations; we don't really care. But you do need to show us any step that someone couldn't easily figure out and explain your reasoning.

hcs
2010-06-15 21:48:34

sanatize your input

sanatize your input

DanZ
2010-06-15 21:48:35

Yes, true.

Yes, true.

MJStone
2010-06-15 21:48:38

(Also, http://xkcd.com/327/ )

(Also, http://xkcd.com/327/ )

avec_une_h
2010-06-15 21:49:02

Will we go over these problems again at MathCamp?

Will we go over these problems again at MathCamp?

DanZ
2010-06-15 21:49:12

Some people will present their solutions at a colloquium --- we'll organize that at camp.

Some people will present their solutions at a colloquium --- we'll organize that at camp.

DanZ
2010-06-15 21:49:20

(Unless everyone at camp was already here, who knows. We'll improvise!)

(Unless everyone at camp was already here, who knows. We'll improvise!)

caffeineboy
2010-06-15 21:49:42

Some people meaning students

Some people meaning students

DanZ
2010-06-15 21:49:48

Yes yes --- students do the presentations.

Yes yes --- students do the presentations.

sachiroo
2010-06-15 21:50:08

What did you think about this year's quiz vs other quizes from other years?

What did you think about this year's quiz vs other quizes from other years?

DanZ
2010-06-15 21:50:21

I don't know, but in some sense it doesn't matter: we don't compare overall results, just results as compared to other students.

I don't know, but in some sense it doesn't matter: we don't compare overall results, just results as compared to other students.

smartkid11235813
2010-06-15 21:50:26

what was the hardest problem in your opinion

what was the hardest problem in your opinion

DanZ
2010-06-15 21:50:37

I don't know, because sometimes I saw earlier versions first, etc., so I didn't have the chance to solve them straight through.

I don't know, because sometimes I saw earlier versions first, etc., so I didn't have the chance to solve them straight through.

DanZ
2010-06-15 21:50:55

All right, then! Thank you all for coming. I hope you learned a lot about solving challenging math problems and that you enjoyed yourself. Stay in touch, and I hope you all consider applying next year!

All right, then! Thank you all for coming. I hope you learned a lot about solving challenging math problems and that you enjoyed yourself. Stay in touch, and I hope you all consider applying next year!

DanZ
2010-06-15 21:51:20

I'm looking forward to meeting many of you at camp or elsewhere!

I'm looking forward to meeting many of you at camp or elsewhere!