Math Jams

DanZ 2010-06-15 19:31:48
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.

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

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!

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 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).

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.

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?

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.)

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.

DanZ 2010-06-15 19:33:40
So feel free to contribute to problems.

sachiroo 2010-06-15 19:34:10
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. :)

mathwiz172 2010-06-15 19:34:42
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.

DanZ 2010-06-15 19:35:00
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?

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.

hcs 2010-06-15 19:35:39
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.

gh625 2010-06-15 19:36:08
Did you give partial credit?

DanZ 2010-06-15 19:36:11
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?

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.

DanZ 2010-06-15 19:36:41
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!

DanZ 2010-06-15 19:36:50
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!

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.)

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.

DanZ 2010-06-15 19:37:27
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.

DanZ 2010-06-15 19:37:50
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$

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.

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.

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.

DanZ 2010-06-15 19:40:07

DanZ 2010-06-15 19:40:34

gh625 2010-06-15 19:41:03
Induction

hcs 2010-06-15 19:41:03
induction

Shortgeek 2010-06-15 19:41:03
induction? Or is there a cleverer way?

DanielC 2010-06-15 19:41:03
induction

MJStone 2010-06-15 19:41:03
And induction

kevin7 2010-06-15 19:41:03
Induction?

Iamerror 2010-06-15 19:41:03
induction

Arouet 2010-06-15 19:41:17
by induction

smartkid11235813 2010-06-15 19:41:17
induction

math911 2010-06-15 19:41:17
Induction.

DanZ 2010-06-15 19:41:18
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):

hcs 2010-06-15 19:42:02
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):

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

MJStone 2010-06-15 19:43:41
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.

L2gB 2010-06-15 19:43:41
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

hcs 2010-06-15 19:43:41
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

gh625 2010-06-15 19:43:41
S(n)=3S(n-1)+2

DanielC 2010-06-15 19:43:41
S(n)= 3S(n-1) +2

professordad 2010-06-15 19:43:41
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.

.cpp 2010-06-15 19:43:41
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?

MJStone 2010-06-15 19:44:41
U(N-1)

Shortgeek 2010-06-15 19:44:41
S(n-1)

smartkid11235813 2010-06-15 19:44:41
S(n-1)

Arouet 2010-06-15 19:44:41
s(n-1)

gh625 2010-06-15 19:44:41
S(n-1)

DanielC 2010-06-15 19:44:41
S(n-1)

ziv 2010-06-15 19:44:41
Move top $n-1$ discs from A to C ($S(n-1) moves)

kevin7 2010-06-15 19:44:41
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?

Shortgeek 2010-06-15 19:45:41
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.

L2gB 2010-06-15 19:45:41
move them back again

vwu9 2010-06-15 19:45:41
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

smartkid11235813 2010-06-15 19:45:41
Move n-1 stack back from A to C

Arouet 2010-06-15 19:45:41
move all the rest to c

gh625 2010-06-15 19:45:41
Move the rest of the discs back to peg C.

peefthepur1 2010-06-15 19:45:41
S(n-1) again

abhinand 2010-06-15 19:45:48
then do S(n-1) again

PurpleEnigma 2010-06-15 19:45:48
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

hcs 2010-06-15 19:45:48
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

L2gB 2010-06-15 19:46:48
so (S(n-1))3+2?

PurpleEnigma 2010-06-15 19:46:48
3S(n-1)+2

gh625 2010-06-15 19:46:48
S(n)=3S(n-1)+2

DanielC 2010-06-15 19:46:48
3s(n-1)+2

Iamerror 2010-06-15 19:46:48
3S(n-1)+2

kevin7 2010-06-15 19:46:48
3s(n-1) + 2

Arouet 2010-06-15 19:46:48
3S(n-1)+2

avec_une_h 2010-06-15 19:46:48
3S(n-1) + 2

smartkid11235813 2010-06-15 19:46:48
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

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!

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.)

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?

DanZ 2010-06-15 19:47:51
If you were solving this for the first time?

Great Spheres 2010-06-15 19:48:31
Get S(1)

gh625 2010-06-15 19:48:31
Write out a few terms

Titandrake 2010-06-15 19:48:31
List values for n = 1,2,3, etc...

Iamerror 2010-06-15 19:48:31
plug in values and see if it worked

MJStone 2010-06-15 19:48:31
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

soccer22 2010-06-15 19:48:31
calculate the first few terms of S(n)

digitsman 2010-06-15 19:48:31
digitsman, out!

Arouet 2010-06-15 19:48:31
work out beginning values and look for a pattern

blabla4198 2010-06-15 19:48:31
plug in n and s

DanZ 2010-06-15 19:48:35

gh625 2010-06-15 19:49:09
Same as before

hcs 2010-06-15 19:49:09
induction now

PowerOfPi 2010-06-15 19:49:09
induction!

professordad 2010-06-15 19:49:09
induction again

smartkid11235813 2010-06-15 19:49:09
Induction!

lvdrlvr55 2010-06-15 19:49:09
check it with both n and n-1

bixiazheng 2010-06-15 19:49:09
induction

avec_une_h 2010-06-15 19:49:09
induction

Titandrake 2010-06-15 19:49:09
induction

Arouet 2010-06-15 19:49:09
induction again

Shortgeek 2010-06-15 19:49:09
defining Q(n) = S(n) + 1, and observing that Q(n) = 3 * Q(n-1)

Iamerror 2010-06-15 19:49:09
induction again

stevenyu10a 2010-06-15 19:49:09
induction

DanielC 2010-06-15 19:49:09
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

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.

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:

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?

DanZ 2010-06-15 19:50:58
(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.

DanZ 2010-06-15 19:51:52

DanZ 2010-06-15 19:51:55
What's different here?

DanZ 2010-06-15 19:53:14
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.

DanZ 2010-06-15 19:53:29
You have to prove it!

Great Spheres 2010-06-15 19:53:31
The largest disc only needs to move once

bixiazheng 2010-06-15 19:53:31
you have to use C as the extra peg

Iamerror 2010-06-15 19:53:31
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

ziv 2010-06-15 19:53:31
we're moving to the middle peg, and the problem isn't symmetrical

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

avec_une_h 2010-06-15 19:53:31
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

professordad 2010-06-15 19:53:31
we move from peg A to peg B

mathwiz172 2010-06-15 19:53:31
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.

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.

DanZ 2010-06-15 19:53:54
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!

Shortgeek 2010-06-15 19:55:20
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)$

DanielC 2010-06-15 19:55:20
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

MeowmixOX;D 2010-06-15 19:55:20
P(n)= S(n)+1+P(n-1)

smartkid11235813 2010-06-15 19:55:20
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

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?

Shortgeek 2010-06-15 19:56:07
put in values, find a pattern, find a formula, induct or be clever

DanielC 2010-06-15 19:56:07
look at values

Great Spheres 2010-06-15 19:56:07
Find P(1)!

smartkid11235813 2010-06-15 19:56:07
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?

peregrinefalcon88 2010-06-15 19:56:41
its a sum of powers of three

kevin7 2010-06-15 19:56:42
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

Shortgeek 2010-06-15 19:56:42
compare it to S(n)?

mathwiz172 2010-06-15 19:56:42
multiply all the answers by 2

ksun48 2010-06-15 19:56:46
1, 1+3, 1+3+9, ... so we

smartkid11235813 2010-06-15 19:56:50
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.

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)

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).

DanZ 2010-06-15 19:57:54
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:

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.

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!

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.

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.

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.

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.

DanZ 2010-06-15 19:59:00

DanZ 2010-06-15 19:59:32
Problem 2: The 100-Game

DanZ 2010-06-15 19:59:36
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?

ziv 2010-06-15 20:00:53
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

mathwiz172 2010-06-15 20:00:53
you can always make it add up to 11

Arouet 2010-06-15 20:00:53
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.

MJStone 2010-06-15 20:00:53
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.

smartkid11235813 2010-06-15 20:00:53
you can always pick the oppisite number as your opponent

mathwiz172 2010-06-15 20:00:53
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

mathwiz172 2010-06-15 20:00:53
or 4 more than a multiple of 11

Titandrake 2010-06-15 20:00:53
aka 4+7 always equals 11

sachiroo 2010-06-15 20:01:01
11's!

DanielC 2010-06-15 20:01:08
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

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.

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!

DanZ 2010-06-15 20:01:29
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

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

turak 2010-06-15 20:02:19
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

turak 2010-06-15 20:02:19
400, 700

smartkid11235813 2010-06-15 20:02:19
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

quadraticfanatic 2010-06-15 20:02:19
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

gh625 2010-06-15 20:02:19
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

sachiroo 2010-06-15 20:02:19
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!

DanZ 2010-06-15 20:02:37
Does this suggest a better strategy for either player?

gh625 2010-06-15 20:03:01
Go first

Arouet 2010-06-15 20:03:01
start with the 4

smartkid11235813 2010-06-15 20:03:01
Go first and start with 4

forthewinalcumus 2010-06-15 20:03:01
yes, the 1st player can control the game

lvdrlvr55 2010-06-15 20:03:01
Yes, start with 4 and then alternate.

bixiazheng 2010-06-15 20:03:01
1st

PowerOfPi 2010-06-15 20:03:01
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.

MJStone 2010-06-15 20:03:08
First player starts with 4, then always plays opposite of the opponent

peefthepur1 2010-06-15 20:03:08
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
...

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.

DanZ 2010-06-15 20:03:25
Does this work?

DanielC 2010-06-15 20:03:57
yes\

bixiazheng 2010-06-15 20:03:57
yes

forthewinalcumus 2010-06-15 20:03:57
so the 1st player wins, right?

abhinand 2010-06-15 20:03:57
YES

ziv 2010-06-15 20:03:57
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

L2gB 2010-06-15 20:03:57
yes

Arouet 2010-06-15 20:03:57
should

quadraticfanatic 2010-06-15 20:03:57
yes

Shortgeek 2010-06-15 20:03:57
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.

avec_une_h 2010-06-15 20:03:57
yes

kevin7 2010-06-15 20:03:57
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?

ziv 2010-06-15 20:04:34
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

forthewinalcumus 2010-06-15 20:04:34
PROVE IT

PurpleEnigma 2010-06-15 20:04:34
prove it?

L2gB 2010-06-15 20:04:34
prove player 2 cant win before hand

Great Spheres 2010-06-15 20:04:34
Block counter-strategies

Iamerror 2010-06-15 20:04:34
proof that it works every time

Shortgeek 2010-06-15 20:04:34
make sure they don't hit 100, 200, or 300

professordad 2010-06-15 20:04:34
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

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.

DanielC 2010-06-15 20:04:37
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

DanZ 2010-06-15 20:04:45
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.)

DanZ 2010-06-15 20:04:51
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:

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.

DanZ 2010-06-15 20:05:27
Any questions about that problem?

Shortgeek 2010-06-15 20:05:47
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. :)

fortenforge 2010-06-15 20:06:04
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.

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.)

DanZ 2010-06-15 20:07:18
Problem 3: One-to-one and Onto

DanZ 2010-06-15 20:07:22
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

kevin7 2010-06-15 20:08:54
1+5 = 6

nwalton125 2010-06-15 20:08:54
6

bixiazheng 2010-06-15 20:08:54
6

Titandrake 2010-06-15 20:08:54
6

math911 2010-06-15 20:08:54
1+r

.cpp 2010-06-15 20:08:54
1+5=6

professordad 2010-06-15 20:08:54

DanielC 2010-06-15 20:08:54
6

hcs 2010-06-15 20:08:54
it can't be -8 because then it would be negative

avec_une_h 2010-06-15 20:08:54
6

Shortgeek 2010-06-15 20:08:54
6 because it can't be -7 because it only goes to positive integers

quadraticfanatic 2010-06-15 20:08:54
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, ...}.

DanZ 2010-06-15 20:09:05

DanielC 2010-06-15 20:09:33
7

MJStone 2010-06-15 20:09:33
7

Iamerror 2010-06-15 20:09:33
7

nwalton125 2010-06-15 20:09:33
7

avec_une_h 2010-06-15 20:09:33
7

quadraticfanatic 2010-06-15 20:09:33
seven

Shortgeek 2010-06-15 20:09:33
7 similarly

abhinand 2010-06-15 20:09:33
7

hcs 2010-06-15 20:09:33
the same reasoning applies, we must add

professordad 2010-06-15 20:09:33

lvdrlvr55 2010-06-15 20:09:33
7

L2gB 2010-06-15 20:09:33
7

Arouet 2010-06-15 20:09:33
7

Great Spheres 2010-06-15 20:09:33
Same logic applies to give 7.

roflmao14723 2010-06-15 20:09:33
7

math911 2010-06-15 20:09:33
2+r=7

stevenyu10a 2010-06-15 20:09:33
7

.cpp 2010-06-15 20:09:33
2+5=7

smartkid11235813 2010-06-15 20:09:33
7 cant be -6

kevin7 2010-06-15 20:09:33
7, and so on until F(9)

DanZ 2010-06-15 20:09:35
For the same reason, it's 7.

DanZ 2010-06-15 20:09:38
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

math911 2010-06-15 20:10:00
9

MJStone 2010-06-15 20:10:00
9

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

Iamerror 2010-06-15 20:10:00
at nine

Titandrake 2010-06-15 20:10:00
at F(9)

forthewinalcumus 2010-06-15 20:10:00
when you get up to 9

stevenyu10a 2010-06-15 20:10:00
f(6)

PowerOfPi 2010-06-15 20:10:00
at F(9)

hcs 2010-06-15 20:10:00
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

nwalton125 2010-06-15 20:10:00
f(9)

peefthepur1 2010-06-15 20:10:00
n>8?

bixiazheng 2010-06-15 20:10:00
F(9)

lvdrlvr55 2010-06-15 20:10:00
F(9)

Arouet 2010-06-15 20:10:00
at 9

quadraticfanatic 2010-06-15 20:10:00
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.

Titandrake 2010-06-15 20:10:40
F(9) has to equal 1

smartkid11235813 2010-06-15 20:10:40
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

Titandrake 2010-06-15 20:10:41
or else not onto

MJStone 2010-06-15 20:10:41
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.

quadraticfanatic 2010-06-15 20:10:41
1.

Arouet 2010-06-15 20:10:41
1

bixiazheng 2010-06-15 20:10:41
9-8

stevenyu10a 2010-06-15 20:10:41
1

forthewinalcumus 2010-06-15 20:10:41
1,

MJStone 2010-06-15 20:10:41
To be 1

smartkid11235813 2010-06-15 20:10:41
1 have to have a 1

DanielC 2010-06-15 20:10:41
1 because f(x) is onto

kevin7 2010-06-15 20:10:41
the latter, since we need f(n) = 1 for some n

L2gB 2010-06-15 20:10:41
1

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

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

ziv 2010-06-15 20:10:41
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

PowerOfPi 2010-06-15 20:10:41
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

nwalton125 2010-06-15 20:10:43
1, otherwise F(n) can never equal one

roflmao14723 2010-06-15 20:10:43
1

Great Spheres 2010-06-15 20:10:45
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?

math911 2010-06-15 20:11:59
mod 13

Shortgeek 2010-06-15 20:11:59
in intervals of 13, F(n) - n repeats

forthewinalcumus 2010-06-15 20:11:59
it continues in cycles

kevin7 2010-06-15 20:11:59
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

avec_une_h 2010-06-15 20:11:59
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

stevenyu10a 2010-06-15 20:11:59
period of 13

Great Spheres 2010-06-15 20:11:59
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

abhinand 2010-06-15 20:11:59
cyclic

roflmao14723 2010-06-15 20:11:59
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)

bixiazheng 2010-06-15 20:11:59
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

blabla4198 2010-06-15 20:11:59
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, ...

Titandrake 2010-06-15 20:11:59
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

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.

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.

ziv 2010-06-15 20:12:27
i.e. F(n + 13) = F(n) + 13

DanZ 2010-06-15 20:12:32
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?

blabla4198 2010-06-15 20:14:07
give proof

smartkid11235813 2010-06-15 20:14:07
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.

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?

quadraticfanatic 2010-06-15 20:15:44
since 2010 is 8(mod 13), F(2010)=2015

smartkid11235813 2010-06-15 20:15:44
2010=8 (mod 13)

L2gB 2010-06-15 20:15:44
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

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

PowerOfPi 2010-06-15 20:15:44
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?

DanielC 2010-06-15 20:15:44
2010 = 8 (mod13) = F(2010) = 2010 +5 = 2015

smartkid11235813 2010-06-15 20:15:44
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

kevin7 2010-06-15 20:15:45
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

DanZ 2010-06-15 20:15:52

DanZ 2010-06-15 20:16:05
Now for part (b):

DanZ 2010-06-15 20:16:18
What's the first thing we do?

DanZ 2010-06-15 20:16:20
Ack, wait.

DanZ 2010-06-15 20:16:53
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?

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.

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?

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.

MJStone 2010-06-15 20:18:45
Perhaps test it with the r and s given in part a.

quadraticfanatic 2010-06-15 20:18:45
experiment with small numbers

forthewinalcumus 2010-06-15 20:18:57
use our known equations -- u know, the ones we derived in part a

DanZ 2010-06-15 20:18:59
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

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

quadraticfanatic 2010-06-15 20:20:49
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

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.

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

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.

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

kevin7 2010-06-15 20:23:14
(r+s) / GCF (r, s)

forthewinalcumus 2010-06-15 20:23:14
LCM (r, r plus s)

aaronlandesman 2010-06-15 20:23:14
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?

quadraticfanatic 2010-06-15 20:25:05
it ugly

hcs 2010-06-15 20:25:05
it looks ugly

ziv 2010-06-15 20:25:05
it's a multiple of r divided by r

Iamerror 2010-06-15 20:25:05
lcm(r,anyhting) divides by r

smartkid11235813 2010-06-15 20:25:05
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.)

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!

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!

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

DanZ 2010-06-15 20:26:10
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.

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?

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.

DanZ 2010-06-15 20:28:01
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

MJStone 2010-06-15 20:28:42
Their product is 10^n

kevin7 2010-06-15 20:28:42
2^n * 5^n = 10^n

gh625 2010-06-15 20:28:42
They multiply to give 10^n

Titandrake 2010-06-15 20:28:42
2^n * 5^n = 10^n

peregrinefalcon88 2010-06-15 20:28:42
product is 10

sachiroo 2010-06-15 20:28:42
They multiply to equal 10^n.

DanielC 2010-06-15 20:28:42
their product is 10^n

Great Spheres 2010-06-15 20:28:42
2^n times 5^n is 10^n

L2gB 2010-06-15 20:28:42
when multiplied together, you get 10^n

nwalton125 2010-06-15 20:28:47
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 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:

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?

DanZ 2010-06-15 20:31:32
Wait, that was the wrong question.

DanZ 2010-06-15 20:31:40
What can you tell me about the parity of k + p?

DanZ 2010-06-15 20:32:10
And can anyone tell me why?

smartkid11235813 2010-06-15 20:32:59
odd

Shortgeek 2010-06-15 20:32:59
must be odd, not sure why

avec_une_h 2010-06-15 20:32:59
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

kevin7 2010-06-15 20:32:59
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.)

DanZ 2010-06-15 20:33:14

L2gB 2010-06-15 20:34:47
they are 31...

Shortgeek 2010-06-15 20:34:47
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)!

.cpp 2010-06-15 20:34:47
Must be around the square root of 10.

Titandrake 2010-06-15 20:34:47
same as the first ten digits of root 10

smartkid11235813 2010-06-15 20:34:47
must be the digits of sqrt(10) 3162277660

Arouet 2010-06-15 20:34:47
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.

DanZ 2010-06-15 20:35:05
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.

L2gB 2010-06-15 20:35:48
how about the extra?

smartkid11235813 2010-06-15 20:35:48
are we going to do the extra bonus part

aaronlandesman 2010-06-15 20:35:48
can you explain 4 extra?

DanZ 2010-06-15 20:35:54
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.

DanZ 2010-06-15 20:36:07
Sorry about that. :(

Great Spheres 2010-06-15 20:36:36
Is it possible to prove that it exists, though?

DanZ 2010-06-15 20:36:39
Yes, it is.

MJStone 2010-06-15 20:36:42
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.

DanZ 2010-06-15 20:36:58
Ok, let us press forwards!

DanZ 2010-06-15 20:37:05
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?

Shortgeek 2010-06-15 20:38:04
ayup

Titandrake 2010-06-15 20:38:04
yes

ziv 2010-06-15 20:38:04
yup! :)

Iamerror 2010-06-15 20:38:04
yes

kevin7 2010-06-15 20:38:04
yes

gh625 2010-06-15 20:38:04
yes

MJStone 2010-06-15 20:38:04
Yes

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

lvdrlvr55 2010-06-15 20:38:04
yes

L2gB 2010-06-15 20:38:04
yes

gh625 2010-06-15 20:38:04
use strong induction

DanielC 2010-06-15 20:38:04
yes

aaronlandesman 2010-06-15 20:38:04
indeed i believe it is

DanZ 2010-06-15 20:38:06
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?

MJStone 2010-06-15 20:38:46
2^n

Shortgeek 2010-06-15 20:38:46
2^n

kevin7 2010-06-15 20:38:46
2^n

avec_une_h 2010-06-15 20:38:46
2^n

Titandrake 2010-06-15 20:38:46
2^n

ziv 2010-06-15 20:38:46

sachiroo 2010-06-15 20:38:46
2^n

L2gB 2010-06-15 20:38:46
2^n

Great Spheres 2010-06-15 20:38:46
2^n

nwalton125 2010-06-15 20:38:46
2^n

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

Arouet 2010-06-15 20:38:46
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?

MJStone 2010-06-15 20:40:20
Factors of n

hcs 2010-06-15 20:40:20
all of the ones of length dividing n

sachiroo 2010-06-15 20:40:20
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.

smartkid11235813 2010-06-15 20:40:20
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,

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.

MJStone 2010-06-15 20:40:20
Well, sequences of lengths that are factors of n

Arouet 2010-06-15 20:40:20
factors of n

Shortgeek 2010-06-15 20:40:20
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

DanZ 2010-06-15 20:40:27

DanZ 2010-06-15 20:40:34

MJStone 2010-06-15 20:41:52
a(d)

Shortgeek 2010-06-15 20:41:52
a_d, because you can only subtract ones that themselves don't repeat smaller ones

L2gB 2010-06-15 20:41:52
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

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

smartkid11235813 2010-06-15 20:41:52
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.

Titandrake 2010-06-15 20:41:52
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 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?

gh625 2010-06-15 20:43:28
use strong induction

hcs 2010-06-15 20:43:28
complete induction

DanielC 2010-06-15 20:43:28
induction

ziv 2010-06-15 20:43:28
ohhh strong induction! (I did the inclusion/exclusion thing)

Great Spheres 2010-06-15 20:43:28
But we split it into parity-cases

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

smartkid11235813 2010-06-15 20:43:28
prove all n are divisable by 6, strong induction

Titandrake 2010-06-15 20:43:28
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

L2gB 2010-06-15 20:43:28
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

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.

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

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.

DanZ 2010-06-15 20:43:49
Case 1: n odd

DanZ 2010-06-15 20:43:54

kevin7 2010-06-15 20:44:30
2

DanielC 2010-06-15 20:44:31
2

Shortgeek 2010-06-15 20:44:31
2! (which equals 2 if you are less happy)

smartkid11235813 2010-06-15 20:44:31
2

MJStone 2010-06-15 20:44:31
2

professordad 2010-06-15 20:44:31
two

Iamerror 2010-06-15 20:44:31
2

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

Titandrake 2010-06-15 20:44:31
2

Great Spheres 2010-06-15 20:44:33
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

Shortgeek 2010-06-15 20:45:12
2 as well

Iamerror 2010-06-15 20:45:12
2

Great Spheres 2010-06-15 20:45:12
a1=2, so we subtract 2 there

smartkid11235813 2010-06-15 20:45:12
2

DanielC 2010-06-15 20:45:12
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.

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.

MJStone 2010-06-15 20:45:58
Only factors where d>=3

Iamerror 2010-06-15 20:45:58
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

DanZ 2010-06-15 20:46:03

ziv 2010-06-15 20:46:05
a bunch of multiples of 6

DanZ 2010-06-15 20:46:10
Case 2: n even

DanZ 2010-06-15 20:46:16

professordad 2010-06-15 20:47:05
a_2

kevin7 2010-06-15 20:47:05
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

Iamerror 2010-06-15 20:47:05
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

DanielC 2010-06-15 20:47:05
we must subtract a_2 = 2

Titandrake 2010-06-15 20:47:05
subtract a1 and a2

MJStone 2010-06-15 20:47:05
Whoops, a_2

aaronlandesman 2010-06-15 20:47:10
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

MJStone 2010-06-15 20:47:10
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)

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).

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.

DanZ 2010-06-15 20:47:34
That's part (a).

DanZ 2010-06-15 20:47:42
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

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

ziv 2010-06-15 20:49:19

ziv 2010-06-15 20:49:19
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

DanZ 2010-06-15 20:49:30
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?

smartkid11235813 2010-06-15 20:50:52
d<=n/2

MJStone 2010-06-15 20:50:52
1 through n/2

Titandrake 2010-06-15 20:50:52
d less or equal to n / 2

Shortgeek 2010-06-15 20:50:52
(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.)

Great Spheres 2010-06-15 20:51:44
2^d

MJStone 2010-06-15 20:51:44
2^d

Great Spheres 2010-06-15 20:51:44
or, 2^floor n/2

Shortgeek 2010-06-15 20:51:44
2^d

MJStone 2010-06-15 20:51:44
Because we don't need to be any more precise really

smartkid11235813 2010-06-15 20:51:44
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

aaronlandesman 2010-06-15 20:51:44
2^d

Iamerror 2010-06-15 20:51:47
2^(n/2)

DanZ 2010-06-15 20:51:49

DanZ 2010-06-15 20:52:18
(If so, to what?)

MJStone 2010-06-15 20:53:07
Assume n/2 is an integer, then geometric series

smartkid11235813 2010-06-15 20:53:07
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

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.

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.

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.

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!

DanZ 2010-06-15 20:54:36
Thus, l'Hopital is not so helpful here.

DanZ 2010-06-15 20:54:40
Anyway, questions about this problem?

DanZ 2010-06-15 20:55:44
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)?

hcs 2010-06-15 20:56:38
it's geometric

ziv 2010-06-15 20:56:38
geometric

gh625 2010-06-15 20:56:38
geometric

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

Arouet 2010-06-15 20:56:38
geometric(ish)

professordad 2010-06-15 20:56:38
geometric

kevin7 2010-06-15 20:56:38
A geometric? but the 1-x thing messes it up...

smartkid11235813 2010-06-15 20:56:38
geometric?

Shortgeek 2010-06-15 20:56:38
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.

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.

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!

DanZ 2010-06-15 20:57:55
Anyway, how would we get the first sum?

Shortgeek 2010-06-15 20:58:51
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

Shortgeek 2010-06-15 20:58:51
(N-1) - [(1-x^N)/(1-x)]

smartkid11235813 2010-06-15 20:58:51
split it up into 1 and -x^n

DanielC 2010-06-15 20:58:54
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

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}.

DanZ 2010-06-15 21:00:06
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

MJStone 2010-06-15 21:00:41
1

Iamerror 2010-06-15 21:00:41
1

quadraticfanatic 2010-06-15 21:00:41
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

Iamerror 2010-06-15 21:01:50
0

ziv 2010-06-15 21:01:50
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.

chhan92 2010-06-15 21:01:52
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

DanielC 2010-06-15 21:03:19
*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

DanZ 2010-06-15 21:03:24

DanZ 2010-06-15 21:03:30
(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

MJStone 2010-06-15 21:04:39
It's 2010

Shortgeek 2010-06-15 21:04:39
N = 2010

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

smartkid11235813 2010-06-15 21:04:45
N=2010

DanZ 2010-06-15 21:04:48

Great Spheres 2010-06-15 21:05:45
x^2010=1/2

MJStone 2010-06-15 21:05:45
2x^2010 = 1

DanielC 2010-06-15 21:05:45
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))

ziv 2010-06-15 21:05:48

aaronlandesman 2010-06-15 21:05:50
just put in N=2010 and solve for x

smartkid11235813 2010-06-15 21:05:52
x^n=1/2

DanZ 2010-06-15 21:05:57

DanZ 2010-06-15 21:06:12
Questions?/

Shortgeek 2010-06-15 21:07:42
why would you inflict such a monstrosity of algebra upon us?

DanZ 2010-06-15 21:07:45
Hrm.

DanZ 2010-06-15 21:07:47
Sorry. :(

DanZ 2010-06-15 21:08:56
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!

DanZ 2010-06-15 21:09:06
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!

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.

DanZ 2010-06-15 21:09:45
Let's go through both parts of this problem carefully.

DanZ 2010-06-15 21:09:50
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?

ziv 2010-06-15 21:11:29
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....

Shortgeek 2010-06-15 21:11:29
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

aaronlandesman 2010-06-15 21:11:29
use a "coloring" arguement

smartkid11235813 2010-06-15 21:11:31
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.

smartkid11235813 2010-06-15 21:12:57
one of each

Titandrake 2010-06-15 21:12:57
whtie and black

Great Spheres 2010-06-15 21:12:57
one of each color

Iamerror 2010-06-15 21:12:57
one of each color

nwalton125 2010-06-15 21:12:57
one black, one white

aaronlandesman 2010-06-15 21:12:57
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.

Arouet 2010-06-15 21:12:57
1 white 1 black

L2gB 2010-06-15 21:12:57
one black and one white?

MJStone 2010-06-15 21:12:57
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?

hcs 2010-06-15 21:13:46
MN/4

nwalton125 2010-06-15 21:13:46
MN/4

kevin7 2010-06-15 21:13:46
MN/4 of each color.

MJStone 2010-06-15 21:13:46
MN/4

Titandrake 2010-06-15 21:13:46
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?

Great Spheres 2010-06-15 21:14:46
two of black or two of white

DanielC 2010-06-15 21:14:46
either 2 black or 2 white

quadraticfanatic 2010-06-15 21:14:46
two black or two white

Shortgeek 2010-06-15 21:14:46
either both black or both white

hcs 2010-06-15 21:14:46
two of the same

Iamerror 2010-06-15 21:14:46
either 2 black or 2 white

Peter92 2010-06-15 21:14:46
two of the same

L2gB 2010-06-15 21:14:46
2 black or 2 white

ziv 2010-06-15 21:14:46
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!

professordad 2010-06-15 21:14:46
either 2 black or 2 white

Titandrake 2010-06-15 21:14:46
2 black or 2 white

MJStone 2010-06-15 21:14:46
2 of either color

stevenyu10a 2010-06-15 21:14:46
2 blacks or 2 whites

smartkid11235813 2010-06-15 21:14:55
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?

Arouet 2010-06-15 21:15:25
even

Iamerror 2010-06-15 21:15:25
it must be divisible by 2

quadraticfanatic 2010-06-15 21:15:25
it is even

stevenyu10a 2010-06-15 21:15:25
it must be even

DanielC 2010-06-15 21:15:25
it must be een

Shortgeek 2010-06-15 21:15:25
it is covered in groups of two, so it is divisible by two

Saphira 7 2010-06-15 21:15:33
divisible by 8

professordad 2010-06-15 21:15:33
its divisible by 2

smartkid11235813 2010-06-15 21:15:33
MN/4 is even

DanielC 2010-06-15 21:15:33
*even

ziv 2010-06-15 21:15:33
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.

DanZ 2010-06-15 21:15:39
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?

Great Spheres 2010-06-15 21:16:32
2x2 squares

hcs 2010-06-15 21:16:32
divide it into 2x2 squares

MJStone 2010-06-15 21:16:32
Squares

Peter92 2010-06-15 21:16:32
use 2x4 blocks

Arouet 2010-06-15 21:16:32
split into 2 by 2 sections

Iamerror 2010-06-15 21:16:32
an equal number of squares of two horizontal or verticle

DanielC 2010-06-15 21:16:32
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

ziv 2010-06-15 21:16:32
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

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.

DanZ 2010-06-15 21:17:30
Ok. We are troopers. One problem remaining. Questions on this one?

Shortgeek 2010-06-15 21:18:05
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!

DanZ 2010-06-15 21:18:38
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!

DanZ 2010-06-15 21:19:15
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.

DanZ 2010-06-15 21:19:34
(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?

ziv 2010-06-15 21:20:35
12

Iamerror 2010-06-15 21:20:35
12

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

gh625 2010-06-15 21:20:35
12W 14B

L2gB 2010-06-15 21:20:35
14 black cubes and 12 white cubes

kevin7 2010-06-15 21:20:35
14 black, 12 white

DanielC 2010-06-15 21:20:35
no... 14 black and 12 white

Peter92 2010-06-15 21:20:35
14 black 12 white

math911 2010-06-15 21:20:35
14 black, 12 white?

Shortgeek 2010-06-15 21:20:35
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

smartkid11235813 2010-06-15 21:20:35
12

Iamerror 2010-06-15 21:20:35
*of white and 14 of black

stevenyu10a 2010-06-15 21:20:35
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.

DanZ 2010-06-15 21:21:09
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.

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.)

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.)

DanielC 2010-06-15 21:23:19
tile with 2 by 1 by 1 blocks of each color

Iamerror 2010-06-15 21:23:19
(BBWW) repeat

sachiroo 2010-06-15 21:23:19
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

kevin7 2010-06-15 21:23:19
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

Shortgeek 2010-06-15 21:23:19
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.

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)

visheshk 2010-06-15 21:23:19
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)

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...

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

MJStone 2010-06-15 21:23:19
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...

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.

MJStone 2010-06-15 21:23:25
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

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...

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.

DanZ 2010-06-15 21:24:42
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?

DanZ 2010-06-15 21:24:56
Ack, that wasn't LaTeXed.

DanZ 2010-06-15 21:25:03

DanZ 2010-06-15 21:25:17
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

DanielC 2010-06-15 21:26:29
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

Iamerror 2010-06-15 21:26:29
yes

hcs 2010-06-15 21:26:29
so yes

Shortgeek 2010-06-15 21:26:29
2x2x2x2.... hypercubes in a checkerboard pattern, analagously

soccer22 2010-06-15 21:26:29
yes!

aaronlandesman 2010-06-15 21:26:29
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.

sachiroo 2010-06-15 21:26:29
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

Titandrake 2010-06-15 21:26:29
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.

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.

math911 2010-06-15 21:26:29
If you can find such a universe with greater than 3 dimensions, I'm guessing yes?

turak 2010-06-15 21:26:29
yes

DanZ 2010-06-15 21:26:40
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.

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.

soccer22 2010-06-15 21:27:36
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

DanZ 2010-06-15 21:27:45

DanZ 2010-06-15 21:27:54
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.

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.

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.

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.

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.

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.

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.

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.

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!)

DanZ 2010-06-15 21:29:45
(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.

DanZ 2010-06-15 21:30:01
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?

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.

DanZ 2010-06-15 21:30:49
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.

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.

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

DanZ 2010-06-15 21:31:38
What color is the cube with coordinates (0,0,0,...,0)?

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

visheshk 2010-06-15 21:32:27
white?

turak 2010-06-15 21:32:27
white

Iamerror 2010-06-15 21:32:27
white

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

professordad 2010-06-15 21:32:27
white

DanZ 2010-06-15 21:32:29
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.

DanZ 2010-06-15 21:32:49
How many neighbors total does it have?

DanZ 2010-06-15 21:33:21
Hey guys: n dimensions. :)

DanZ 2010-06-15 21:33:49
(Welcome... to the n-th dimension!!! Ahem.)

smartkid11235813 2010-06-15 21:34:04
3^n-1

turak 2010-06-15 21:34:04
3^n-1 where there are n dimensions

Great Spheres 2010-06-15 21:34:04
3^n-1

Arouet 2010-06-15 21:34:04
3^n - 1

Shortgeek 2010-06-15 21:34:04
3^n - 1

soccer22 2010-06-15 21:34:04
3^n -1

L2gB 2010-06-15 21:34:04
3^n-1

hcs 2010-06-15 21:34:04
3^n -1

kevin7 2010-06-15 21:34:04
3^n - 1

howru 2010-06-15 21:34:04
3^n-1

visheshk 2010-06-15 21:34:08
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?

visheshk 2010-06-15 21:35:08
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.

MJStone 2010-06-15 21:35:08
All coordinates are in the range -1 to 1

smartkid11235813 2010-06-15 21:35:08
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

Shortgeek 2010-06-15 21:35:08
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

Arouet 2010-06-15 21:35:08
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

visheshk 2010-06-15 21:35:16
+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?

DanZ 2010-06-15 21:36:25
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.

visheshk 2010-06-15 21:36:57
if a change is applied to an odd number of cubes

visheshk 2010-06-15 21:36:57
the color should change

visheshk 2010-06-15 21:36:57
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.

Great Spheres 2010-06-15 21:36:57
So it's based on the parity of the number of -1s

turak 2010-06-15 21:37:01
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.)

DanielC 2010-06-15 21:38:51
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)

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.)

DanielC 2010-06-15 21:40:03
binomial expansion

Shortgeek 2010-06-15 21:40:03
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

Peter92 2010-06-15 21:41:09
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?

Iamerror 2010-06-15 21:41:09
we counted the center cube?

smartkid11235813 2010-06-15 21:41:09
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

Great Spheres 2010-06-15 21:41:09
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)

avec_une_h 2010-06-15 21:41:12
we counted the white cube in the center

DanZ 2010-06-15 21:41:15

caffeineboy 2010-06-15 21:41:24
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.

DanZ 2010-06-15 21:41:50
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

MJStone 2010-06-15 21:41:52
Very nice solution

DanZ 2010-06-15 21:41:55
Thank you!

MJStone 2010-06-15 21:42:00
A little messy, but the other one is inevitably too wordy

DanZ 2010-06-15 21:42:02
Hehe.

DanZ 2010-06-15 21:42:06
So, questions on problem 8?

Great Spheres 2010-06-15 21:42:31
n colors?

Great Spheres 2010-06-15 21:42:31
or, sorry, use a different variable for that, maybe r

DanZ 2010-06-15 21:42:36
Oh goodness... I have no idea.

DanZ 2010-06-15 21:42:38
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.

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.

DanZ 2010-06-15 21:43:17
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).

Peter92 2010-06-15 21:43:34
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.

DanZ 2010-06-15 21:43:48
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.

Shortgeek 2010-06-15 21:44:05
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.

L2gB 2010-06-15 21:44:38
so, were there a lot of possible answers?

DanZ 2010-06-15 21:44:40
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

DanZ 2010-06-15 21:44:53
*nod*

DanZ 2010-06-15 21:44:56
Any more overall questions?

professordad 2010-06-15 21:45:06
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.

DanZ 2010-06-15 21:45:37
(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?

hcs 2010-06-15 21:45:44
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.

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?

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.

ziv 2010-06-15 21:46:42
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.

DanZ 2010-06-15 21:47:13
We're going to fix that for next year.

DanZ 2010-06-15 21:47:15
*sigh*

DanZ 2010-06-15 21:47:19
(We thought we'd fixed it for this year!)

MJStone 2010-06-15 21:47:22
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.

Shortgeek 2010-06-15 21:47:44
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.

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.

hcs 2010-06-15 21:48:34
sanatize your input

DanZ 2010-06-15 21:48:35
Yes, true.

MJStone 2010-06-15 21:48:38
(Also, http://xkcd.com/327/ )

avec_une_h 2010-06-15 21:49:02
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.

DanZ 2010-06-15 21:49:20
(Unless everyone at camp was already here, who knows. We'll improvise!)

caffeineboy 2010-06-15 21:49:42
Some people meaning students

DanZ 2010-06-15 21:49:48
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?

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.

smartkid11235813 2010-06-15 21:50:26
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.

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!

DanZ 2010-06-15 21:51:20
I'm looking forward to meeting many of you at camp or elsewhere!

Canada/USA MathCamp Qualifying Quiz

Facilitator: Dan Zaharopol