Canada/USA Mathcamp Qualifying Quiz Math Jam, Part 1

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: Alex Stark


LauraZed 2015-06-23 19:11:43
This classroom is moderated. All messages you type will be sent to the moderators for review, and they will decide which messages to post to the main classroom window.
BVKMisc 2015-06-23 19:22:27
hi
Eugenis 2015-06-23 19:22:27
Hi LauraZed!
Bonami2014 2015-06-23 19:22:27
hi
hunter117 2015-06-23 19:22:27
hello!
LauraZed 2015-06-23 19:22:31
Hello!
calculus_riju 2015-06-23 19:22:38
This is my first math jam so is there any rules for this?
AK3141592 2015-06-23 19:23:12
Hello, I'm wondering if this MathJam is for question purposes only or if we'll learn some material from the class.
khanh93 2015-06-23 19:23:31
We'll be presenting full solutions to problems from the Quiz.
LauraZed 2015-06-23 19:23:32
Just type in questions/answers/comments like you just did, we'll either answer them privately (instructors can whisper or private message) or post it to the classroom.
Eugenis 2015-06-23 19:24:02
Did this start yet?
LauraZed 2015-06-23 19:24:11
This Math Jam will start in about 5 minutes (7:30 ET, 4:30 PT).
hunter117 2015-06-23 19:27:14
how hard is this mathjam going to be?
quartzgirl 2015-06-23 19:27:14
are we going to be solving problems?
LauraZed 2015-06-23 19:27:38
These problems are roughly AIME level, if I had to guess. And yes, we'll be solving problems!
TurtlePie 2015-06-23 19:27:58
What is Mathcamp?
LauraZed 2015-06-23 19:28:07
You can read more about Mathcamp here: http://mathcamp.org/
farmerboy 2015-06-23 19:29:49
where is this camp?
lkarhat 2015-06-23 19:29:49
Also where is mathcamp
chezbgone2 2015-06-23 19:30:00
Where can we find the problems?
LauraZed 2015-06-23 19:30:06
This summer, it's at University of Puget Sound, but it moves around.
LauraZed 2015-06-23 19:30:22
Qualifying Quiz: http://mathcamp.org/prospectiveapplicants/quiz/index.php
LauraZed 2015-06-23 19:31:40
Let's get this Math Jam started!
mihirb 2015-06-23 19:31:49
YAY!
LauraZed 2015-06-23 19:31:53
I'm Laura Zehender; I work at AoPS and attended Mathcamp in '07, '08, and '09. I'll mainly be here in case anyone needs help using the classroom.
LauraZed 2015-06-23 19:32:06
Canada/USA Mathcamp is a five-week residential summer program for mathematically talented high school students. Many AoPS instructors, assistants, and students are alumni of Mathcamp, including me! Tonight, we have a member of the Mathcamp admission committee here to discuss problems #3, #5, and #6 from the qualifying quiz for this outstanding program.
LauraZed 2015-06-23 19:32:15
Alex (khanh93) is a rising junior at Caltech studying mathematics. This summer will be Alex’s second as a Mathcamp staff, and this fall he is organizing the Caltech Harvey Mudd Math Competition.
LauraZed 2015-06-23 19:32:24
Some other Mathcamp staff might drop by as well -- Halimeda (Gravity) is the Assistant Director for External Affairs and Marisa (MarisaD) is the Program Director. Feel free to say hi to them if you spot them in the classroom!
LauraZed 2015-06-23 19:32:33
I'll turn the room over to Alex now!
khanh93 2015-06-23 19:32:59
Thanks Laura!
Eugenis 2015-06-23 19:33:08
Hi Alex!
Eugenis 2015-06-23 19:33:10
Hi Gravity!
hunter117 2015-06-23 19:33:13
Hello!!
khanh93 2015-06-23 19:33:22
As Laura mentioned, I'm Alex -- though if you come to Mathcamp, you'll know me as Jalex. (Traditionally, we avoid having multiple staffs of the same name at the same time.)
khanh93 2015-06-23 19:33:30
I wrote and graded problem 6 on the Quiz, which may or may not be reflected in our treatment of it in this session.
khanh93 2015-06-23 19:33:38
Also hanging out here is Halimeda, another admissions committee member. Halimeda graded problem 4 and will be running the second part of the Jam next week.
khanh93 2015-06-23 19:34:00
Full disclosure before we start: I have never taught an AoPS class before, so please bear with me as I learn the ropes. (Also, if I know you, but wouldn't recognize you from your username, please introduce yourself!)
khanh93 2015-06-23 19:34:11
I'll be going over the solutions to the Mathcamp Qualifying Quiz, an untimed set of (hard) problems that 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. The Quiz is not the only factor that affects your admission to Mathcamp, but it is the most important one.
khanh93 2015-06-23 19:34:27
This chat room is moderated. That means your messages go only to me, and I will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time.
khanh93 2015-06-23 19:34:39
But if you have questions about how we select problems or how we grade solutions, please save them and I'll try to leave time for them at the end of the Math Jam. If I don't end up getting to your questions, feel free to post them on the Mathcamp forum on AoPS at http://www.artofproblemsolving.com/Forum/viewforum.php?f=314
khanh93 2015-06-23 19:34:51
My goal is to get through problems 3, 5, and 6 on the quiz, in about 90 minutes.
khanh93 2015-06-23 19:34:57
I'll try to show you not just the correct answers, but how you might come up with those answers, and how to write them in a way that really communicates the mathematics you're doing. 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. (This is how a lot of actual math talks work too.)
khanh93 2015-06-23 19:35:15
To follow along, you should all have the quiz open in another window: http://www.mathcamp.org/prospectiveapplicants/quiz/index.php
khanh93 2015-06-23 19:35:27
And if you applied this year, I recommend having your solutions open too. That way, you can reply more quickly to the questions I ask of the room. I like to teach interactively, so I'm expecting you all to pitch in to the solutions!
khanh93 2015-06-23 19:35:36
Let's start with problem 3, which is short and sweet.
khanh93 2015-06-23 19:35:51
Problem 3
khanh93 2015-06-23 19:35:54
For a positive integer $n$, let $P_n$ be the product of all the positive integer divisors of $n$ (including $n$ itself). For example, if $n=10$, then $P_n = 100$, because $1 \cdot 2\cdot 5\cdot 10 = 100$. Suppose I'm thinking of an integer $n$, but I only tell you $P_n$. Does this always give you enough information to figure out what $n$ is? If so, prove it. If not, find a counterexample: a pair of integers $m$ and $k$ such that $P_m = P_k$.
khanh93 2015-06-23 19:36:14
First, what is the answer?
Longhair343 2015-06-23 19:36:32
The answer is yes, right?... please tell me it is yes!
yank2601 2015-06-23 19:36:33
Yes
Jaksaf 2015-06-23 19:36:35
Yes it is enough.
calculus_riju 2015-06-23 19:36:36
yes
khanh93 2015-06-23 19:36:45
(Yes, that does give us enough information!)
khanh93 2015-06-23 19:36:50
How do we prove it?
yulanzhang 2015-06-23 19:37:07
Contradiction?
AK3141592 2015-06-23 19:37:12
Find a pattern in P(n)
crosbykane 2015-06-23 19:37:12
Take a few examples
mihirb 2015-06-23 19:37:31
contradiction seems good
limelego 2015-06-23 19:37:33
factor out p(n)?
khanh93 2015-06-23 19:37:59
Yes, we will eventually use a contradiction argument. First though, let's learn a bit more about $P_n$.
scottistrue 2015-06-23 19:38:19
I started w/ values of n that aren't perfect squares, so P(n) is a power of n, but that got pretty messy
quartzgirl 2015-06-23 19:38:34
for example, 9, 1*3*3*9 = 9^2, and after more examples, we realize that the product, P_n = n^2
mihirb 2015-06-23 19:38:47
Observation: if $n$ is not a perfect square then $P_n = n^{\frac{d(n)}{2}}$
dustin8559 2015-06-23 19:38:55
Pn is equal to n to power of number of factors divided by 2
khanh93 2015-06-23 19:39:10
Some of you have the correct formula for P_n
khanh93 2015-06-23 19:39:20
Let's see why.
khanh93 2015-06-23 19:39:25
Say $n$ has $k$ factors, $d_1,d_2,\ldots,d_k$. We can notice that $n/d_1,n/d_2,\ldots,n/d_k$ are also the $k$ divisors of $n$, in a different order.
khanh93 2015-06-23 19:39:40
So,
\begin{align*}(P_n)^2&=(d_1\cdots d_k)\left(\frac{n}{d_1} \cdots \frac{n}{d_k}\right)\\
     &=n^k\end{align*}
khanh93 2015-06-23 19:40:00
From this we see that $P_n=n^{k/2}$.
khanh93 2015-06-23 19:40:15
Alright, now we are ready to set up the contradiction!
khanh93 2015-06-23 19:40:26
Let's take two numbers $n<m$ and assume that $P_n=P_m$. Let's say that $n$ has $k$ factors as before, and $m$ has $j$ factors.
khanh93 2015-06-23 19:40:41
So, by our previous argument, $n^{k/2} =m^{j/2}$.
khanh93 2015-06-23 19:40:53
To simplify our exponents, let's square both sides. $n^k =m^j$
khanh93 2015-06-23 19:41:02
Since $n<m$, we can conclude that $k>j$.
khanh93 2015-06-23 19:41:15
At this point, we need to think about the prime factorizations of $n$ and $m$. We got solutions that uses the prime factorization in several different ways. Let's go over one way that we can use it.
khanh93 2015-06-23 19:41:28
Since $n^k=m^j$, $n$ and $m$ have to have the same prime factors, just with different exponents.
khanh93 2015-06-23 19:42:01
Let $p_1^{a_1} \dots p_r^{a_r}$ be the prime factorization of $n$.
khanh93 2015-06-23 19:42:09
This means that $p_1,\ldots,p_r$ are distinct primes, $p_i^{a_i}$ divides $n$ and $p_i^{a_i+1}$ does not divide $n$.
khanh93 2015-06-23 19:42:23
\begin{align*} m^j &= n^k = p_1^{ka_1} \dots p_r^{ka_r} \\m &= p_1^{ka_1/j} \dots p_r^{ka_r/j} \end{align*}
khanh93 2015-06-23 19:42:51
Since $k>j$, $ka_i/j>a_i$, so $m$ divides $n$. Thus $m\ge n$ and we have our contradiction!
quartzgirl 2015-06-23 19:43:24
what about perfect squares?
mihirb 2015-06-23 19:43:24
is there a different way to prove it
mihirb 2015-06-23 19:43:34
just using a pattern or logic?
khanh93 2015-06-23 19:43:45
Our formula for P_n applies to perfect squares,
scottistrue 2015-06-23 19:44:03
Perfect squares are fine, just the number of factors is odd
khanh93 2015-06-23 19:44:16
Thanks, scottistrue!
Longhair343 2015-06-23 19:44:29
I didn't see the n^d(n) thing and just bashed out using prime factorization
Longhair343 2015-06-23 19:44:31
Turned out pretty neat too, though...
khanh93 2015-06-23 19:44:54
There are multiple ways to phrase it, but I think most of the arguments boil down to the same idea
opireader 2015-06-23 19:45:10
Let me get this straight. Let $M_n$ be $\sqrt{n}$ if $n$ is a perfect square and $n$ if $n$ is not a perfect square. Then $P_n=M_n^k$ for some $k$.
khanh93 2015-06-23 19:45:20
I think that's true, opireader
khanh93 2015-06-23 19:45:39
and k is a function of the number of divisors of n
briantix 2015-06-23 19:45:55
err do you mean $m \le n$ so contradiction?
khanh93 2015-06-23 19:46:11
Good catch, briantix
khanh93 2015-06-23 19:46:49
Okay, let's move on to problem 5, then.
khanh93 2015-06-23 19:46:54
Problem 5
skys 2015-06-23 19:47:07
Why does m divide n? Doesn't n divide m since its exponents of powers are smaller?
mihirb 2015-06-23 19:47:07
ok
khanh93 2015-06-23 19:47:53
Oh, it seems hsin1030 has it right
khanh93 2015-06-23 19:48:16
We started by assuming $ m< n$, and then we found that $n$ divides $m$
khanh93 2015-06-23 19:49:56
Okay; I think we're all set on problem 3
khanh93 2015-06-23 19:50:01
The game of ProSet is played with a deck of $63$ cards. One of the cards has six dots of six different colors. Each of the other cards has some of the dots but is missing others. All the cards are different and each card has at least one dot. A proset is a set of cards that together contain an even number of dots of each color.
khanh93 2015-06-23 19:50:15
a) Prove that the entire ProSet deck is itself a proset (i.e. the total number of dots of each color is even).
khanh93 2015-06-23 19:50:31
Let's start with (a). How many dots are there of each color?
tmathman 2015-06-23 19:50:49
32
Longhair343 2015-06-23 19:50:49
a) 32
mathgenius64 2015-06-23 19:50:49
32
opireader 2015-06-23 19:50:49
Umm... there are 32 dots of each color, I believe!
dustin8559 2015-06-23 19:50:49
32
Jaksaf 2015-06-23 19:51:22
2^5 since there are 5 spots left after you choose a particular color. Then you can choose to incorporate each of the colors or not.
khanh93 2015-06-23 19:51:32
(32.)
khanh93 2015-06-23 19:51:35
If a card has a red dot, then each other dot can either be present or absent meaning that there are $2^5=32$ possibilities for the other dots. Similarly, for any other color, there are $32$ cards with that color dot. So there are an even number of dots of each color.
opireader 2015-06-23 19:52:03
Therefore, each color occurs an even number of times, which satisfies the requirements of a ProSet.
khanh93 2015-06-23 19:52:23
Exactly, opireader
khanh93 2015-06-23 19:52:28
Now we move on to part (b).
khanh93 2015-06-23 19:52:37
b) Prove that any set of seven cards is guaranteed to contain a proset.
mihirb 2015-06-23 19:52:52
some variation of pigeonhole
Longhair343 2015-06-23 19:52:52
pigeonhole principle!!!
I_--__--_I 2015-06-23 19:52:52
pigeonhole principle
yank2601 2015-06-23 19:52:58
pigeon's hole?
khanh93 2015-06-23 19:53:15
A useful observation is that for any set of cards, there is exactly one card (possibly blank, and possibly already in the set) that can be added to it to make a proset. Let's call this the "complementary card" of the set.
heron 2015-06-23 19:53:25
dirichlet's box principle?
mihirb 2015-06-23 19:53:25
also called dirichlet's principle
khanh93 2015-06-23 19:53:39
The pigeonhole principle has many names, apparently
Jaksaf 2015-06-23 19:53:48
Pigeonhole Principle: the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item.[
yulanzhang 2015-06-23 19:53:57
Isn't it impossible to have a blank card?
yulanzhang 2015-06-23 19:53:59
since all the cards have at least one dot?
khanh93 2015-06-23 19:54:11
That's true, yulanzhang
khanh93 2015-06-23 19:54:25
What happens if the complementary card of a set of cards is blank?
amburger66 2015-06-23 19:54:35
it's already a proset
flyingsledge 2015-06-23 19:54:35
It's already a proset
calculus_riju 2015-06-23 19:54:38
its already a proset
khanh93 2015-06-23 19:54:44
Indeed!
khanh93 2015-06-23 19:54:52
Let's say our set has an even number of red dots. Then the complementary card will not have a red dot. If, on the other hand, our set has an odd number of red dots, then the complementary card will have a red dot, and so on for each color.
khanh93 2015-06-23 19:55:10
If we know that two subsets have the same complementary card, can we use that information to find a proset?
lcalvert99 2015-06-23 19:55:36
it is already a proset
I_--__--_I 2015-06-23 19:55:36
yes
farmerboy 2015-06-23 19:55:36
yes
Longhair343 2015-06-23 19:55:36
yes!
Jaksaf 2015-06-23 19:55:43
We can take the union of those 2 subsets minus their intersection and that should be a proset.
khanh93 2015-06-23 19:55:49
(Yes, combine the two sets.) Why does this work?
khanh93 2015-06-23 19:55:58
If the complementary card has an orange dot, then both original sets have an odd number of orange dots, so together they have an even number of orange dots. If the complementary card does not have an orange dot, then both original sets have an even number of orange dots and together they have an even number of orange dots, and so on for each color.
opireader 2015-06-23 19:56:09
If two subsets have the same complementary card, each color has matching parities, so all the cards in there form a ProSet. (Remove duplicates, and it still holds.)
yank2601 2015-06-23 19:56:11
the odds cancel each other out
khanh93 2015-06-23 19:56:25
If two subsets have the same complementary card, then when we combine them, we get an even number of dots of each color.
khanh93 2015-06-23 19:56:50
Of course, if they overlap, then we might end up with two copies of the same card. Is there a way to fix this?
scottistrue 2015-06-23 19:57:01
Remove both
yank2601 2015-06-23 19:57:10
take the card out entirely
khanh93 2015-06-23 19:57:16
(Yes, just remove both copies--this leaves the number of dots even.)
khanh93 2015-06-23 19:57:30
So, if we take all of the cards that are in exactly one of the two subsets, we will get a proset. (This is called the symmetric difference of the two subsets.)
khanh93 2015-06-23 19:57:47
Now lets say we have an arbitrary hand of $7$ cards. Can we show that two of the possible subsets of this hand must have the same complementary card?
calculus_riju 2015-06-23 19:58:50
intersection!
calculus_riju 2015-06-23 19:58:50
of two sets
opireader 2015-06-23 19:58:50
khanh93: Just take a ProSet (which exists as we've seen), and it has at least 3 cards, so partition it into two nonempty parts, it's that easy.
scottistrue 2015-06-23 19:58:50
7 cards means 2^7=128 subsets
Longhair343 2015-06-23 19:59:08
Assume that they don't, then, you have to have 2^7 unique subsets
khanh93 2015-06-23 19:59:35
The 2^7 subsets are unique since our deck doesn't contain any duplicates.
khanh93 2015-06-23 20:00:15
How many different complementary cards can there be?
yank2601 2015-06-23 20:00:28
63
scottistrue 2015-06-23 20:00:28
63
yank2601 2015-06-23 20:00:28
64
scottistrue 2015-06-23 20:00:42
Not 63, since it can be blank
khanh93 2015-06-23 20:01:21
When we talk about the possible complementary card of a subset, we included blank as a possibility.
amburger66 2015-06-23 20:01:27
blank is the same as all 6 dots
khanh93 2015-06-23 20:01:39
Blank is 0 dots; there is a card in the deck with 6 dots.
heron 2015-06-23 20:01:47
well, if there is a blank complementary card, we know that there is a proset even if no two complementary cards are the same. So really we only care about 63 complements
khanh93 2015-06-23 20:01:52
Good observation, heron!
khanh93 2015-06-23 20:02:03
So we have shown that there are more subsets than complementary cards. By the pigeonhole principle, there must be two subsets with the same complementary card. Taking the symmetric difference of those two sets gives us a proset. We have now proved part (b).
gurev 2015-06-23 20:02:32
linear algebra over $\mathbb{F}_2$ though
khanh93 2015-06-23 20:02:34
For those of you who know something about linear algebra, it is also possible to prove part (b) by arguing that any $7$ vectors in a $6$-dimensional vector space must be linearly dependent. If that comment doesn't make sense to you, don't worry, we won't need it for anything else in the problem.
khanh93 2015-06-23 20:02:46
Now for part (c).
khanh93 2015-06-23 20:02:53
c) For $n < 7$, what is the probability that a random set of n cards contains a proset?
khanh93 2015-06-23 20:03:06
Can we form any prosets with one or two cards?
heron 2015-06-23 20:03:28
no
Hydroxide 2015-06-23 20:03:28
no
rt03 2015-06-23 20:03:28
no
khanh93 2015-06-23 20:03:36
(No. With one card which is not empty, it has a dot of some color and thus an odd number of dots of that color. With two cards, in order to have an even number of each color the two cards would have to be the same, and there are no identical cards in the deck.)
khanh93 2015-06-23 20:03:47
Now let's suppose that we have chosen two cards. How many ways are there for the third card to form a proset with the first two?
tedwang 2015-06-23 20:04:10
complementary card?
Rmehtany 2015-06-23 20:04:10
1
flyingsledge 2015-06-23 20:04:10
1
yank2601 2015-06-23 20:04:10
1
khanh93 2015-06-23 20:04:18
($1$, the complementary card of the two-card set)
khanh93 2015-06-23 20:04:25
There are $61$ cards to choose from, so the probability of having a proset
from $3$ randomly chosen cards is $\frac1{61}$.
khanh93 2015-06-23 20:04:38
Now let's move on to the case $n=4$. From this point onward, it's a bit simpler to compute the probability of not getting a proset, so we will do that and then subtract from $1$ to get the probability of having a proset.
khanh93 2015-06-23 20:04:52
We already know that the probability that the first 3 cards don't form a
proset is $1-\frac1{61}=\frac{60}{61}$. So we just need to figure out the probability that the first $4$ cards don't form a proset given that the first $3$ don't. Of the $60$ remaining cards, how many don't form a proset with the sum of the first three?
Longhair343 2015-06-23 20:05:30
56 !
Hydroxide 2015-06-23 20:05:30
56
mathgenius64 2015-06-23 20:05:30
56
Longhair343 2015-06-23 20:05:30
Right? 64-2^3 or 56
khanh93 2015-06-23 20:05:42
($56$)
khanh93 2015-06-23 20:05:46
Each of the $7$ nonempty subsets of the $3$-card set has a complementary card associated to it. Can any of the complementary cards be the same?
Rmehtany 2015-06-23 20:06:05
no
rt03 2015-06-23 20:06:05
no
mathgenius64 2015-06-23 20:06:05
no otherwise there is already a proset there
khanh93 2015-06-23 20:06:14
(No, we showed in part b that if any of these were the same, then we would have a proset.)
khanh93 2015-06-23 20:06:28
So, of the $63$ cards, there are $7$ that would form a proset with the $3$ cards that have already been chosen. (Three of these seven are the already chosen cards.) That leaves $56$ that we can choose without forming any prosets.
khanh93 2015-06-23 20:06:55
So what is the probability of choosing $4$ cards and not getting any prosets?
Hydroxide 2015-06-23 20:07:49
56/60* 60/61 = 56/61
amburger66 2015-06-23 20:07:49
56/61?
khanh93 2015-06-23 20:08:03
$\left(\frac{56}{61}\right)$
khanh93 2015-06-23 20:08:07
There is a $\frac{60}{61}$ probability that the first $3$ cards do not form a proset, and after that, there is a $\frac{56}{60}$ probability that the fourth card does not form a proset with any of the remaining three. So the probability is $\frac{60}{61}\cdot\frac{56}{60} = \frac{56}{61} $. That leaves a $\frac5{61}$ probability of having a proset.
khanh93 2015-06-23 20:08:33
We can use the same idea for the cases of $5$ and $6$ cards. Given $4$ cards that don't contain any prosets, what is the probability that the fifth card drawn won't form a proset with any subset of the first four?
Hydroxide 2015-06-23 20:09:22
48/59
Rmehtany 2015-06-23 20:09:22
48/60
rt03 2015-06-23 20:09:22
47/61
calculus_riju 2015-06-23 20:09:22
48/61
Longhair343 2015-06-23 20:09:22
48/59
khanh93 2015-06-23 20:09:33
Looks like we've got some confusion in our denominators.
khanh93 2015-06-23 20:09:47
We've already chosen four cards, and started with 63.
Longhair343 2015-06-23 20:09:52
err... there are 59 cards left...
flyingsledge 2015-06-23 20:09:52
You only have 59 cards left to choose from
cedarwax 2015-06-23 20:10:26
48/59
opireader 2015-06-23 20:10:26
Given 5 cards, the probability that there's no ProSet among the first four is 56/61, as we've seen. Given that there's no ProSet among the first four, we wish to find the probability that there's no ProSet among the five, which is 48/59.
calculus_riju 2015-06-23 20:10:26
48/59
khanh93 2015-06-23 20:10:32
$\left(\frac{48}{59}\right)$
khanh93 2015-06-23 20:10:37
There are $64-2^4=48$ cards that won't give us a proset out of $64-4-1=59$. So the probability that the fifth card doesn't give us a proset, given that the first four didn't, is $\frac{48}{59}$. The probability of not getting a proset with five cards is then $\frac{56}{61}\cdot\frac{48}{59} = \frac{2688}{3599}$. That leaves a $\frac{911}{3599}$ chance of having at least one proset.
yulanzhang 2015-06-23 20:10:58
Wait for the 4 card case why was it 64 - 2^3? Why did we include the empty set?
khanh93 2015-06-23 20:11:26
64 - 2^3 = 63 - (2^3 - 1)
calculus_riju 2015-06-23 20:11:33
how r u getting that 2 power thing?
khanh93 2015-06-23 20:11:43
Ah. Let's step back a little.
khanh93 2015-06-23 20:12:09
There are 2^4 subsets of our four card set.
mihirb 2015-06-23 20:12:21
number of subsets of a set $A$ is 2^{|A|}$
Smartwhiz 2015-06-23 20:12:21
2^4=16
khanh93 2015-06-23 20:12:31
Each of them have different complementary cards.
khanh93 2015-06-23 20:12:43
(If any were the same, we'd already have a proset among the first four)
mihirb 2015-06-23 20:13:04
yeah the empty set though?
calculus_riju 2015-06-23 20:13:04
yes,,so u r subtracting to eliminate them?
khanh93 2015-06-23 20:13:31
We want to count the number of cards we can add without forming a proset
khanh93 2015-06-23 20:13:41
If we add in any of the complementary cards, we'll form a proset
khanh93 2015-06-23 20:14:12
The empty set isn't a card in our deck,
yank2601 2015-06-23 20:14:19
so your taking out the complementary cards so it's not a proset
khanh93 2015-06-23 20:14:41
It's also not the complementary card of any of our subsets (why?)
yulanzhang 2015-06-23 20:15:05
If it was then there would already be a proset?
khanh93 2015-06-23 20:15:09
Right.
khanh93 2015-06-23 20:15:29
So when i write 64 - 2^4, I might as well write 63 - (2^4 - 1),
khanh93 2015-06-23 20:15:42
where 63 is the number of cards in the deck and 2^4 - 1 is the number of those cards that form prosets.
khanh93 2015-06-23 20:16:19
The same argument generalizes to say that given a set of $n$ cards, $64 - 2^n$ of those remaining will form a proset with it.
khanh93 2015-06-23 20:16:37
How about with $6$ cards?
rt03 2015-06-23 20:17:23
16/29
quartzgirl 2015-06-23 20:17:23
63 - (2^6 - 1)
khanh93 2015-06-23 20:17:25
(Conditional probability $\frac{32}{58}$, probability of not getting proset $\frac{43008}{104371}$, probability of getting proset $\frac{61363}{104371}$)
khanh93 2015-06-23 20:17:31
The probability of not getting a proset with 6 cards if the first 5 didn't give us a proset is $\frac{64-2^5}{64 - 5 - 1}=\frac{32}{58}$. The overall probability of not getting a proset with $6$ cards is $\frac{2688}{3599}\cdot\frac{32}{58}=\frac{43008}{104371}$, and the probability of getting a proset is $\frac{61363}{104371}$.
khanh93 2015-06-23 20:17:58
These numbers get big and kind of nasty
khanh93 2015-06-23 20:18:12
I don't know of any nice closed-form expression for them.
khanh93 2015-06-23 20:18:15
Finally, what about 7 cards?
Longhair343 2015-06-23 20:18:25
0, which is why the 7th card will have to form a proset with the 6 card set!
opireader 2015-06-23 20:18:25
Calm down... starting at 7 cards, the probability is 1 of course!
Rmehtany 2015-06-23 20:18:25
100%
Hydroxide 2015-06-23 20:18:25
0
opireader 2015-06-23 20:18:29
THE PROBABILITY IS 1 BY PART (b).
khanh93 2015-06-23 20:18:34
(We always get a proset)
khanh93 2015-06-23 20:18:39
If we have 6 cards with no prosets, then every one of the remaining cards in the deck will form a proset with some subset of the six. So with seven cards, we always get a proset. This is a way of proving part (b) without using the pigeonhole principle.
khanh93 2015-06-23 20:19:45
Let's move on.
khanh93 2015-06-23 20:19:46
d) Now suppose you play a different version of the game, in which you are only looking for prosets that have exactly three cards. Find, with proof, the smallest $n$ such that any set of $n$ cards is guaranteed to contain a three-card proset.
khanh93 2015-06-23 20:20:02
There are a few different things that we have to do here. We need to figure out what the value of n should be. Then we need to show that some set of n-1 cards does not contain a three-card proset, and that every set of n cards contains a three-card proset.
khanh93 2015-06-23 20:20:20
In these kinds of problems, there can be some trial and error in figuring out what n should be. Can anyone think of a large set of cards that doesn't contain a 3-card proset?
opireader 2015-06-23 20:21:02
33.
Hydroxide 2015-06-23 20:21:02
the set of all cards having an odd number of dots on them
Longhair343 2015-06-23 20:21:02
set of all cards containing red dots
Longhair343 2015-06-23 20:21:02
or blue dots
DavidUsa 2015-06-23 20:21:02
The set that alternates?
khanh93 2015-06-23 20:21:17
(All cards with a red dot/all cards with an odd number of dots)
khanh93 2015-06-23 20:21:31
If we take all of the cards with red dots, then any set of three of them will have an odd number of red dots, and hence will not be a proset. There are 32 such cards, so n must be at least 33.
DavidUsa 2015-06-23 20:22:06
What's the problem with red dots?
khanh93 2015-06-23 20:22:14
We could have picked any number
khanh93 2015-06-23 20:22:23
Er, I mean color
danusv 2015-06-23 20:23:20
32 definitely wont work because if u pick the 32 card set with all red dots then u cant make a proset. Thus try n=33
quartzgirl 2015-06-23 20:23:27
so n must be 33, because if there is one dot (the minimum) on each card, then 32, will not be a proset, so the answer is 33.
khanh93 2015-06-23 20:23:48
Recall that we want to find the smallest $n$ so that every set of size $n$ has a three-card proset
khanh93 2015-06-23 20:24:12
We just showed that $n$ must be bigger than $32$, since we found a 32 card set without any 3-card prosets in it
khanh93 2015-06-23 20:24:29
So now we need to determine whether 33 cards is enough to guarantee a three card proset. For this, we need to know a bit more about three-card prosets. Choose a card C. What can we say about the three-card prosets containing C?
quartzgirl 2015-06-23 20:25:55
If C has an odd number of dots, then exactly one of the other cards has to have an odd number of dots, if C has an even number, then both the other cards need to be either odd, or even.
yulanzhang 2015-06-23 20:26:00
there are 31 of them?
opireader 2015-06-23 20:26:06
Pick any card other than C (there are 62 of them), then the complementary card is in the other 61. However, if we claim the answer is 62, we've counted each proset twice, once for each other card. Therefore there are 31 three-card prosets containing C (right?)
khanh93 2015-06-23 20:26:21
(The remaining 62 cards can be split into 31 pairs that form a proset with C.)
khanh93 2015-06-23 20:26:39
For any choice of a second card, there is a unique third card that makes a proset with C and the second card. That means that we can split the remaining cards into pairs whose complementary card is C. There are 31 of these pairs.
khanh93 2015-06-23 20:27:02
If S is a set that contains C and at least 32 other cards, then there must be at least one pair whose members are both in S. Then this pair forms a three-card proset with C, and all three cards are in S. So any set of at least 33 cards contains a 33-card proset.
yulanzhang 2015-06-23 20:27:44
3 card proset
Hydroxide 2015-06-23 20:27:44
err you mean 3-card proset
khanh93 2015-06-23 20:27:49
Right, yeah.
khanh93 2015-06-23 20:28:12
We've only got 30ish minutes left, so let's get on to problem 6
khanh93 2015-06-23 20:28:19
Problem 6
khanh93 2015-06-23 20:28:21
King Alfonso devises a game to test the intelligence of his royal advisor, Angela. Alfonso tells Angela to gather n of her friends, each of whom will receive a black or white hat. Each friend will be able to see the color of everyone else’s hat, but not his or her own. The friends will then be asked to stand in a circle and guess their own hat colors by whispering them to the King. (The King decides the order in which they stand, and they do not hear each other’s guesses.) If k out of the n players guess correctly, Alfonso will give Angela and her friends k bags of gold (to divide among themselves as they choose).
khanh93 2015-06-23 20:28:37
Once the rules of the game are announced, the friends are not allowed to talk to each other, so they cannot devise a strategy. Angela (who is not one of the players) must devise a strategy for them: she must write them a letter that will be read aloud by the King. The letter may not give different instructions to different people; it must tell everyone the same thing, such as “Guess the color you see more of; if there’s a tie, guess black” or “If the hat to you left is the same as hat to your right, guess black; otherwise, guess white.” You may assume that Angela’s friends always follow her instructions correctly. Note that after reading the letter, King Alfonso knows Angela’s instructions to the players and can choose a hat color combination to exploit any weak points in her strategy.
khanh93 2015-06-23 20:28:59
Note that a strategy must be deterministic; in other words, it cannot include instructions like “guess randomly”. Otherwise, parts (a) and (c) become false.
khanh93 2015-06-23 20:29:13
First, we should get some intuition for this game. A plausible sounding strategy for Angela is "guess the color you see more of; if there's a tie, guess black". (The choice of black here is arbitrary, but consistent.)
khanh93 2015-06-23 20:29:28
Does this strategy force Alfonso to give any bags of gold?
dsqwerty 2015-06-23 20:29:44
no
Longhair343 2015-06-23 20:29:44
No... not one!
khanh93 2015-06-23 20:29:49
(No.)
khanh93 2015-06-23 20:29:52
If we have an even number of players and exactly half of them have black hats, then everybody will guess incorrectly.
khanh93 2015-06-23 20:29:59
(In fact, it's not very hard to show that *any* strategy that relies only on counting numbers of black and white hats fails to force any gold. I encourage you to try it as an exercise.)
khanh93 2015-06-23 20:30:08
In general, if we want to prove that a strategy is bad, all we have to do is find some hat assignment that makes it fail. Let's apply this observation to the first problem:
khanh93 2015-06-23 20:30:14
(a) Prove that if $n = 2$, Alfonso is not forced to give out any gold, regardless of Angela’s strategy.
khanh93 2015-06-23 20:30:23
One way to do this is to find all of Angela's possible strategies and prove that each one of them fails. This would be a bad idea if Angela had lots of strategies, so a good first question is: How many strategies does she have? (Notice that if two strategies give the same results on all hat configurations, then they're the same strategy, even if they're worded differently.)
calculus_riju 2015-06-23 20:31:09
can there be no black hats, only white ones?
khanh93 2015-06-23 20:31:16
Any assignment of hats is valid, yeah
Longhair343 2015-06-23 20:31:26
2^2 ?
mssmath 2015-06-23 20:31:26
4
flyingsledge 2015-06-23 20:31:26
Each strategy makes each person choose a color based on what they see, in this case, only the other person's hat color
scottistrue 2015-06-23 20:31:38
4 strategies, seeing white can lead to guessing either color, the with black
quartzgirl 2015-06-23 20:31:38
4
khanh93 2015-06-23 20:31:46
($2^2 = 4$.)
khanh93 2015-06-23 20:31:50
There are only 4 strategies, so a brute-force approach should be feasible. Let's find all of them. In the case of only 2 players, a strategy is a really simple object: it's a rule that looks at one hat color and guesses another hat color.
mathtastic 2015-06-23 20:32:04
We can think of each strategy as a function f(a,b) where a,b are either B or W
khanh93 2015-06-23 20:32:10
We can characterize such a strategy with two questions: What does the strategy guess when it sees white? What does it guess when it sees black?
khanh93 2015-06-23 20:32:18
Each of these questions have 2 possible answers, so there are $2^2=4$ possible strategies. We can describe them as: "Always guess black", "Always guess white", "Guess what you see", "Guess the opposite of what you see".
khanh93 2015-06-23 20:32:34
Alfonso needs a way to foil each of these strategies. How?
dustin8559 2015-06-23 20:33:06
Alfonso can just pick the opposite color
Ramanan369 2015-06-23 20:33:06
different color
opireader 2015-06-23 20:33:17
(a) Each friend can see the hat color of the other friend only. There are thus 4
strategies.
1. Guess black
2. Guess white
3. Guess the color the friend's wearing
4. Guess the color the friend isn't wearing
The King can get out of being beaten, in the cases of those respective strategies:
1. Put white hats on both
2. Put black hats on both
3. Put opposite color hats on them
4. Put the same color hat on each [could be either color]
flyingsledge 2015-06-23 20:33:17
Each of the always statements fails because the king can just assign the opposite color, and the opposite statements fail because he can just assign them the same color
DavidUsa 2015-06-23 20:33:17
If the strategy is one of the first 2 he can just do the opposite color, right?
yank2601 2015-06-23 20:33:17
2 white hats; 2 black hats; opposite colored hats; two of the same hats
khanh93 2015-06-23 20:33:32
(In the same order I wrote the strategies, here are hat assignments that foil them: "both hats white", "both hats black", "differently-colored hats", "same-colored hats".)
calculus_riju 2015-06-23 20:33:47
how will he foil? manipulate the instruction or change the hat combo
flyingsledge 2015-06-23 20:34:03
He assigns hats after he hears her strategy
khanh93 2015-06-23 20:34:09
Thanks, flyingsledge
skys 2015-06-23 20:34:26
So the king puts the hats on them after they strategize?
khanh93 2015-06-23 20:34:30
Yes.
khanh93 2015-06-23 20:34:33
Now even though we only had 4 strategies, the brute force approach seemed like a lot of effort. Instead, we could make a cleaner argument by contradiction.
mathtastic 2015-06-23 20:34:46
well everyone has to have the same strategy so you can determine f(B,B)=B and f(W,W)=W
khanh93 2015-06-23 20:34:57
Right on, mathtastic.
khanh93 2015-06-23 20:35:13
I'll say the same thing mathtastic said without the function notation
khanh93 2015-06-23 20:35:16
Assume that we have some strategy that Alfonso can't foil. Then for every assignment of hats Alfonso can make, our strategy has someone get a correct guess.
khanh93 2015-06-23 20:35:33
Consider the assignment where both hats are white. In order for somebody to guess correctly, our strategy must say to guess white when seeing white. Similarly, it must say to guess black when seeing black.
khanh93 2015-06-23 20:35:47
Then this strategy must fail when the hats are different colors, contradicting our original assumption.
khanh93 2015-06-23 20:35:59
Let's move on to b
khanh93 2015-06-23 20:36:00
(b) Prove that for $n > 2$, Angela can always force Alfonso to give out at least one bag of gold (assuming all her friends follow instructions correctly). In other words, Angela can devise a strategy in which at least one player is guaranteed to guess correctly, no matter what assignment of hats Alfonso chooses.
khanh93 2015-06-23 20:36:08
Let's start with $n = 3$. What's a strategy that works here?
Rmehtany 2015-06-23 20:36:42
guess to your left
opireader 2015-06-23 20:36:42
"If the $(n-2)$ hats directly to your right are all black, guess black; otherwise, guess white." I proved that Alfonso has to give out gold in this case!
Jaksaf 2015-06-23 20:36:42
“Always guess black unless you see that everyone else has a white hat or the person to your right is the only one you see with a black hat”
Hydroxide 2015-06-23 20:36:42
guess the color of the person to the right
FlakeLCR 2015-06-23 20:36:42
Guess the color of the person to your right
khanh93 2015-06-23 20:36:53
("Guess the hat color of the person to your left.")
khanh93 2015-06-23 20:36:58
This will work if there are two adjacent people with the same hat color -- the one on the right will guess correctly. If we have just three people, it's impossible to color them without having two adjacent people be the same color.
khanh93 2015-06-23 20:37:10
In fact, the same is true if we have any odd number of people in our circle. This fact is easy to see, but harder to formalize, so we didn't take points off if you stated it without proof. We'll prove it here, though.
khanh93 2015-06-23 20:37:24
Assume (towards a contradiction) you have a hat assignment on $2n+1$ people where no two adjacent players have the same hat color.
khanh93 2015-06-23 20:37:38
Pick a player; without loss of generality, say her hat color is white. Then the two people next to her have black hats.
khanh93 2015-06-23 20:37:50
Then the people two spaces to her left and two spaces to her right have white hats, since each is next to a person with a white hat.
khanh93 2015-06-23 20:38:03
In general, the person $k$ spaces to the left and $k$ spaces to the right have the same hat color as each other.
khanh93 2015-06-23 20:38:17
But the person $n$ spaces to the left is next to the person $n$ spaces to the right, contradicting our original assumption.
khanh93 2015-06-23 20:38:24
So now we have a strategy that forces one bag of gold for odd $n$. Does it apply for even $n$?
quartzgirl 2015-06-23 20:38:47
whats the strategy?
khanh93 2015-06-23 20:38:58
Our strategy is "Guess the hat color of the person to your left."
opireader 2015-06-23 20:39:07
("Guess the hat color of the person to your left.") Actually, that only works if there's an odd number of people! If there's an even number of people, the King could win by putting alternating colors B-W-B-W-... around the circle.
yulanzhang 2015-06-23 20:39:07
No bc he could alternate hats
yank2601 2015-06-23 20:39:07
could be alternating colors
mssmath 2015-06-23 20:39:07
no
flyingsledge 2015-06-23 20:39:07
The king can just make the players alternate hat colors
khanh93 2015-06-23 20:39:19
(It fails precisely when no two adjacent players have the same hat colors.)
khanh93 2015-06-23 20:39:29
This is a rigid constraint; there are only two hat assignments with this property. Since these make up a very small fraction of all possible hat colorings, it feels like we can fix it.
khanh93 2015-06-23 20:39:40
The key observation is that if the hats are arranged in this way, each player is going to see something very similar: an alternating sequence of hats that looks like either "black, white, black, white, ..." or "white, black, white, black, ..." What should our strategy be?
DavidUsa 2015-06-23 20:40:41
If there is an even number, can't the strategy be pick the color 2 to ur left?
mathtastic 2015-06-23 20:40:41
circumvent the issue, if there is an odd factor of n, call it ak, then guess the color n/k to your left
Longhair343 2015-06-23 20:40:41
if you see alternating, just guess the color that fits the alternating pattern
scottistrue 2015-06-23 20:40:41
If the pattern could be alternating, guess as if it is
yank2601 2015-06-23 20:40:41
if the two neighboring people are the same color, guess the opposite
khanh93 2015-06-23 20:40:59
We've got two proposed solutions here.
khanh93 2015-06-23 20:41:16
One of them is based on dividing the circle into subcircles of odd size.
khanh93 2015-06-23 20:41:50
We're not going to discuss it, but the following is a true statement that earned you a point of extra credit for part f:
khanh93 2015-06-23 20:42:19
"If there is a strategy that forces k bags of gold when playing with n people, there is a strategy that forces mk bags of gold when playing with mn people."
khanh93 2015-06-23 20:42:52
The other proposed solution is much simpler and applies to the case $n=2^k$, so we'll use that.
khanh93 2015-06-23 20:42:59
("Guess the color of the hat on your left, unless you see an alternating sequence of hats, in which case guess the opposite.")
khanh93 2015-06-23 20:43:51
Alright, let's get back on track and discuss a solution for part b.
khanh93 2015-06-23 20:44:01
(Sorry if I've confused some of you with this sidebar.)
khanh93 2015-06-23 20:44:16
Again, our strategy is "Guess the color of the hat on your left, unless you see an alternating sequence of hats, in which case guess the opposite."
khanh93 2015-06-23 20:44:33
For an alternating hat arrangment, everybody sees an alternating pattern and guesses correctly.
khanh93 2015-06-23 20:44:41
If there are at least two distinct pairs of adjacent people with the same hat color, then nobody sees an alternating pattern, so everybody uses our original strategy and somebody guesses correctly.
khanh93 2015-06-23 20:44:53
Does that cover every case?
khanh93 2015-06-23 20:45:24
Er, when I said "distinct pairs", I meant "nonoverlapping pairs".
Longhair343 2015-06-23 20:45:49
I think it might fail because what if, WBBBWBWB
scottistrue 2015-06-23 20:46:02
If one person sees alternating but he does not fit the pattern, his neighbor to the right will guess correctly
heron 2015-06-23 20:46:02
no, there is the case with an alternating pattern but one error
khanh93 2015-06-23 20:46:06
(No; take the alternating assignment and flip one person's hat.)
khanh93 2015-06-23 20:46:14
The player whose hat was flipped will see an alternating pattern and guess incorrectly.
heron 2015-06-23 20:46:23
fortunately the strategy still works in this case
khanh93 2015-06-23 20:46:25
However, the person to her right has the same hat color as her. They will not see an alternating pattern, so they will guess her hat color and be correct.
khanh93 2015-06-23 20:46:54
This covers all the cases.
masad24 2015-06-23 20:47:02
yay!
khanh93 2015-06-23 20:47:05
Before we move on, I'd like to note that there's a cleaner strategy that uses more or less the same idea, but in reverse: "Guess the opposite color of the person to your left, unless everyone you see has the same color hat."
khanh93 2015-06-23 20:47:21
Let's tackle problem (c) now.
khanh93 2015-06-23 20:47:47
(c) Find and prove an upper bound on the number of bags of gold that Alfonso can be forced to give out. For example, you might suspect that $n − 1$ is an upper bound; in other words, no matter what strategy Angela adopts, Alfonso can always find an arrangement of hats for which, if the players follow Angela’s strategy, at least one player will guess incorrectly. Either prove this bound or find a smaller one.
khanh93 2015-06-23 20:48:28
The proof of the bound $n-1$ is quite easy and not worth discussing. Several applicants also submitted a nice proof for the $n-2$ upper bound , but this bound turns out not to be tight.
DavidUsa 2015-06-23 20:48:39
n/2
FlakeLCR 2015-06-23 20:48:39
$\left\lfloor\dfrac{n-1}2\right\rfloor$ is a bound.
mathtastic 2015-06-23 20:48:39
i think part e kind of gave te bound away
Longhair343 2015-06-23 20:48:44
I'm going to make a BOLD GUESS and claim something like Floor of (n-1/2)
khanh93 2015-06-23 20:48:51
The upper bound we will prove is $\left\lfloor\frac{n-1}2\right\rfloor$. Stated differently, it's impossible for Angela to force Alfonso to give out $\frac n2$ bags of gold.
khanh93 2015-06-23 20:49:06
(Even if you didn't solve the problem, you might have guessed this bound based on the statement to part (d).)
khanh93 2015-06-23 20:49:17
For those of you familiar with probability theory, our solution can be summarized by the phrase "linearity of expectation". If those words aren't familiar to you, then don't worry; we won't use any heavy machinery here.
khanh93 2015-06-23 20:49:23
We want to prove that for every strategy, there is some way for Alfonso to arrange the hats so that he gives out strictly less than $\frac n2$ bags of gold. Our proof will be nonconstructive: we'll fix an arbitrary strategy and argue that there's some way for Alfonso to beat it without saying how.
khanh93 2015-06-23 20:49:36
This kind of proof isn't very useful if you're Alfonso, but it allows us to prove something about every possible strategy all at once.
khanh93 2015-06-23 20:49:45
Alright, let's begin.
khanh93 2015-06-23 20:49:47
Fix some strategy. Consider some particular hat assignment and some particular player -- call her Sarah. Sarah either guesses correctly or doesn't.
khanh93 2015-06-23 20:49:59
Now consider the hat assignment that we get by flipping Sarah's hat.
khanh93 2015-06-23 20:50:06
In this position, Sarah sees the same thing as before and therefore guesses the same thing as before. If she was incorrect before, she is correct now and vice versa.
khanh93 2015-06-23 20:50:23
(Other players might change their guesses, but we're just focused on Sarah for now)
LaTeX_turtle 2015-06-23 20:50:32
Aha! Sarah sees the same thing!
calculus_riju 2015-06-23 20:50:32
so for every wrong theres a right
khanh93 2015-06-23 20:50:40
We conclude that out of the $2^n$ possible hat assignments, Sarah guesses correctly in $2^{n-1}$ of them and incorrectly in the other $2^{n-1}$ of them.
khanh93 2015-06-23 20:50:51
Sarah isn't special, though; we can say the same thing for every player.
khanh93 2015-06-23 20:50:58
Now let's run an experiment. Alfonso and Angela play $2^n$ rounds of the game in which Angela uses the same strategy every time and Alfonso gives a different hat assignment every time.
khanh93 2015-06-23 20:51:06
How many bags of gold does Alfonso give out over the course of this experiment?
calculus_riju 2015-06-23 20:51:50
2^n-1 * n
Longhair343 2015-06-23 20:51:50
n times 2^(n-1)
mathtastic 2015-06-23 20:52:32
based on the bound it should be $\frac{n}{2} (2^n)$
quartzgirl 2015-06-23 20:52:32
n * 2^(n-1)
khanh93 2015-06-23 20:52:54
Alright, let's write out the number we want to calculate as a sum: $$\sum_{\text{hat assignments }h}\#(\text{players that guess correctly on assignment }h)$$
khanh93 2015-06-23 20:53:12
We can think of this as counting ordered pairs $(h,p)$ where $p$ is a player that guesses correctly on hat assignment $h$.
khanh93 2015-06-23 20:53:22
This number is the same as the number of ordered pairs $(p,h)$ where $h$ is a hat assignment in which player $p$ guesses correctly.
khanh93 2015-06-23 20:53:32
We'll use this to rewrite the sum. (This technique, switching the order of summation, has sometimes been dubbed The Most Powerful Proof Technique In All Of Mathematics)
khanh93 2015-06-23 20:53:50
We get $$ \sum_{\text{players } p}\#(\text{hat assignments that }p\text{ guesses correctly in}) $$
khanh93 2015-06-23 20:54:13
What's the value of this sum?
khanh93 2015-06-23 20:54:47
We know that the term on the inside is equal to $2^{n-1}$ for each player and that there are $n$ players, so we conclude that Alfonso gives out $n2^{n-1}$ bags of gold over the course of the experiment.
LaTeX_turtle 2015-06-23 20:55:05
I concur with Calculus. Each person will win 2^n-1 and there are n people.
InCtrl 2015-06-23 20:55:05
n*(2^n-1) once again?
LaTeX_turtle 2015-06-23 20:55:05
2^n-1 * n
rt03 2015-06-23 20:55:05
$n(2^(n-1))$
khanh93 2015-06-23 20:55:11
Then what is the average of number of bags of gold Alfonso has to give out in each round of the experiment?
Hydroxide 2015-06-23 20:55:37
n/2
LaTeX_turtle 2015-06-23 20:55:37
n/2
rt03 2015-06-23 20:55:37
n/2
khanh93 2015-06-23 20:55:41
($\frac{n 2^{n-1}}{2^n} = \frac n2$ bags of gold.)
khanh93 2015-06-23 20:55:50
The average of a sequence of numbers can't be larger than every number in that sequence, so there must be some assignment in which Alfonso gives out $\leq \frac n2 $ bags of gold.
khanh93 2015-06-23 20:55:57
But this is a little weaker than what we set out to prove: is it possible that Alfonso gives out exactly $\frac n2$ bags of gold in every hat assignment?
rt03 2015-06-23 20:56:32
No, for odd values of n, it doesn't work.
khanh93 2015-06-23 20:56:46
That's true; we've already finished the proof for the odd case.
khanh93 2015-06-23 20:56:50
But for the even case?
LaTeX_turtle 2015-06-23 20:56:59
But what about evens? Can one invent a counterexample for event?
mathtastic 2015-06-23 20:57:09
but $f(WWW\cdots WWW)=W$ and same for $f(BBB\cdot BBB)=B$
Jaksaf 2015-06-23 20:57:09
In the case that it is all white or all black Alfonso has to give everything or nothing as the players all guess the same thing.
mathtastic 2015-06-23 20:57:09
consider all hats being monochromatic
khanh93 2015-06-23 20:57:22
(No.)
khanh93 2015-06-23 20:57:26
Consider a hat assignment where every player has the same hat color.
khanh93 2015-06-23 20:57:39
Every player sees the same thing, so every player makes the same guess. Either they're all wrong or they're all right -- it's not possible for exactly half of them to be right, regardless of the strategy.
khanh93 2015-06-23 20:57:49
Now the average over all hat assignments of the number of bags of gold Alfonso has to give out is $\frac n2$, but not every hat assignment has $\frac n2$ exactly.
khanh93 2015-06-23 20:58:01
We conclude that there is some hat assignment in which Alfonso gives out strictly fewer than $\frac n2$ bags of gold.
quartzgirl 2015-06-23 20:58:26
so, it could be n/2, or more, or less
khanh93 2015-06-23 20:58:43
For any particular hat assignment, Alfonso gives out some number of bags of gold
khanh93 2015-06-23 20:59:17
The average over all hat assignments of the number of bags he has to give is $\frac n2$.
khanh93 2015-06-23 20:59:49
So for every hat assignment that performs really well, there are hat assignments that perform less well
LaTeX_turtle 2015-06-23 21:00:09
What I mean is, we proved that some assignments cannot be n/2 and some cannot be <n/2, but do those two sets intersect?
khanh93 2015-06-23 21:00:19
Alfonso gets to choose his hat assignment.
khanh93 2015-06-23 21:00:36
If any hat assignment exists where Alfonso doesn't need to give out $\frac n2$ bags of gold, he'll pick it.
khanh93 2015-06-23 21:00:51
(And indeed, we showed that such an assignment exists.)
khanh93 2015-06-23 21:01:07
Notice that this doesn't tell Alfonso how to find it
yulanzhang 2015-06-23 21:01:13
But if he gives out less than n/2 bags of gold in some and more in others how is this an upper bound?
khanh93 2015-06-23 21:01:33
He was giving out more in some when we were doing the experiment;
LaTeX_turtle 2015-06-23 21:01:57
He can adapt his strategy according to Angela's. If he's smart this is the upper bound.
khanh93 2015-06-23 21:02:09
In the experiment, he was forced to sometimes pick bad hat assignments.
khanh93 2015-06-23 21:02:13
When Angela and Alfonso play the game for real, he's going to pick the best hat assignment he can.
yulanzhang 2015-06-23 21:03:00
But what about when he is able to give out less than n/2?
khanh93 2015-06-23 21:03:07
That's certainly his goal!
khanh93 2015-06-23 21:03:21
Okay, we've hit our soft deadline of 9 PM
khanh93 2015-06-23 21:03:31
We've got one question left and it's going to take a long time
khanh93 2015-06-23 21:03:53
For anyone who's interested, I can stay and cover 6d
khanh93 2015-06-23 21:04:07
Otherwise, I don't want you to feel pressured to stay late.
khanh93 2015-06-23 21:04:14
(d) If $n = 2^k$, find a strategy that always forces Alfonso to give out at least $2^{k−1} − 1$ bags of gold.
scottistrue 2015-06-23 21:04:29
That would be appreciated
amburger66 2015-06-23 21:04:29
yes please!
mathtastic 2015-06-23 21:04:29
6d is the reason i even came to this mathjam i spent at least 20 hours on it and never got it
SreyaR 2015-06-23 21:04:29
coool!!!!
khanh93 2015-06-23 21:04:38
Seems like enthusiasm is high.
khanh93 2015-06-23 21:04:52
Before, we start, Laura has a quick survey question
LauraZed 2015-06-23 21:05:13
How many of you applied to Mathcamp this year?
scottistrue 2015-06-23 21:06:06
I did
heron 2015-06-23 21:06:06
I applied
dsqwerty 2015-06-23 21:06:06
Me!
praha2 2015-06-23 21:06:06
me
Hydroxide 2015-06-23 21:06:06
me
danusv 2015-06-23 21:06:06
me
flyingsledge 2015-06-23 21:06:06
I did
opireader 2015-06-23 21:06:06
I did!
CherryCream 2015-06-23 21:06:06
I did
LauraZed 2015-06-23 21:06:14
Lots of applicants!
LauraZed 2015-06-23 21:07:03
And because there are a lot of people that go to Mathcamp more than once (like me, haha), anyone here who has already attended Mathcamp in a previous summer?
khanh93 2015-06-23 21:07:37
Ooh; me!
LauraZed 2015-06-23 21:07:57
Haha
LauraZed 2015-06-23 21:08:33
It looks like we don't have any other past campers here, so now back to Alex so you guys can solve 6d!
khanh93 2015-06-23 21:08:45
Thanks, Laura!
Gravity 2015-06-23 21:08:46
quick note:
Gravity 2015-06-23 21:09:24
a lot of people mentioned cost in the questions I won't go into all the details here, but Mathcamp gives a lot of financial aid. We never want cost to be a reason someone can't come to mathcamp.
khanh93 2015-06-23 21:11:19
Okay; it looks like we've still got about 2/3 of our original crowd.
khanh93 2015-06-23 21:11:33
Thanks for sticking around guys; let's get to the math!
khanh93 2015-06-23 21:12:01
(d) If $n = 2^k$, find a strategy that always forces Alfonso to give out at least $2^{k-1}-1$  bags of gold.
khanh93 2015-06-23 21:12:05
(Notice that part (c) proves that this is the best we can do.)
khanh93 2015-06-23 21:12:11
The statement of the problem is asking us to prove a statement about all powers of $2$. What proof technique does this suggest?
heron 2015-06-23 21:12:28
induction
Longhair343 2015-06-23 21:12:28
mathematical induction?
mathtastic 2015-06-23 21:12:31
induction but good luck with that
khanh93 2015-06-23 21:13:01
This problem was meant to be solved by induction. However, it turns out that the argument we (the quiz-writing committee) used in the inductive step doesn't critically depend on $n$ being a power of $2$; rather, it can be modified to go through for all even $n$.
khanh93 2015-06-23 21:13:35
We also gave you a few points if you used induction to prove that you can get $2^{n-2}$ bags
khanh93 2015-06-23 21:13:48
So the statement we will prove is: "If $n = 2k$, there is a strategy that always forces Alfonso to give out at least $k-1$ bags of gold."
khanh93 2015-06-23 21:14:02
(We didn't know that this statement was true when we published the quiz -- we only learned of the proof that follows because several of you submitted it!)
khanh93 2015-06-23 21:14:15
Before we get to that, let's warm up with an easier problem:
khanh93 2015-06-23 21:14:16
Take the same setup as before, except that each player is either left-handed or right-handed. Each left-handed player is between two right-handed players and each right-handed player is between to left-handed players.
khanh93 2015-06-23 21:14:31
Let $n=2$ and devise a strategy that always forces Alfonso to give out $1$ bag of gold.
danusv 2015-06-23 21:14:54
cant do that
Longhair343 2015-06-23 21:14:54
you mean 0!
khanh93 2015-06-23 21:15:08
Part (a) would suggest we can't, but notice we have some additional information here
Longhair343 2015-06-23 21:15:12
(I meant 0, not 0!... which is 1 haha)
heron 2015-06-23 21:15:15
wait but how can they be between two right handed players if there is only one other player
khanh93 2015-06-23 21:15:36
Sorry; there's one left handed player and one right-handed
LaTeX_turtle 2015-06-23 21:15:47
And how does the lefties and righties help?
khanh93 2015-06-23 21:16:00
Everybody knows their own handedness
heron 2015-06-23 21:16:05
also, are they trying to guess their handedness, or do they still have hats?
khanh93 2015-06-23 21:16:11
And they're still trying to guess their hats
mathtastic 2015-06-23 21:16:29
no, you can, heres the strategy: have the lefties guess the color opposite them and the righties guess the color not opposite them
flyingsledge 2015-06-23 21:16:29
If you're left handed, guess that other person's color, If you're right handed, guess the opposite of their color.
khanh93 2015-06-23 21:16:41
Right!
mathtastic 2015-06-23 21:16:44
it half voids the restriction that everyone must have the same strategy, now every other person can have the same strategy
khanh93 2015-06-23 21:16:50
(The left-handed player guesses the same color as the hat they see and the right-handed player guesses the opposite color of the hat they see.)
khanh93 2015-06-23 21:16:57
The two players are making opposite assumptions about reality and exactly one of them is correct; the one who is guesses correctly.
LaTeX_turtle 2015-06-23 21:17:15
They break the symmetry don't they? Angela can refer to the left handed or right handed player in her instructions. The problem is now not isomorphic.
flyingsledge 2015-06-23 21:17:15
With the left and right handedness, you can give directions towards a more specific group of people instead of everyone
khanh93 2015-06-23 21:17:23
Good observations, indeed.
khanh93 2015-06-23 21:17:28
Now generalize to a strategy that always forces Alfonso to give out $\frac n2$ bags of gold for any $n$.
quartzgirl 2015-06-23 21:17:48
can angela pick her friends, such that one is left-handed and one is right-handed
calculus_riju 2015-06-23 21:17:48
wait...how do u knw the no. of lefties and righties? alfonso know their handedness?
khanh93 2015-06-23 21:17:58
The handedness is public knowledge here.
heron 2015-06-23 21:18:53
lefties guess there is an odd number of black hats, righties guess there is an even number
khanh93 2015-06-23 21:19:22
Yeah; that works
khanh93 2015-06-23 21:19:37
I'm going to take it in a slightly different direction, though.
LaTeX_turtle 2015-06-23 21:19:49
Can you explain a bit how that works?
khanh93 2015-06-23 21:20:04
The left handed players and right-handed players are making different assumptions about reality
khanh93 2015-06-23 21:20:19
those that make correct assumptions make correct guesses and those that make incorrect assumptions make incorrect guesses
khanh93 2015-06-23 21:20:38
If you guess that there are an even number of black hats, and you see an odd number, you know you must have a black hat yourself.
LaTeX_turtle 2015-06-23 21:20:44
Ay and one has to be correct...
LaTeX_turtle 2015-06-23 21:20:44
And you can use that assumption to get with absolute certanty your own hat!
khanh93 2015-06-23 21:21:00
I'm going to use a different set of assumptions about reality
khanh93 2015-06-23 21:21:03
(Each left-handed player guesses the same color as the player on their left and each right-handed player guesses the opposite color of the player on their right.)
khanh93 2015-06-23 21:21:16
This divides our $n$ players into $\frac n2$ pairs, and in each pair, exactly one guesses correctly.
khanh93 2015-06-23 21:21:22
Now we want to relate this back to our original problem. We shouldn't expect to apply exactly the same argument, since that would contradict what we proved in (c).
khanh93 2015-06-23 21:21:37
Instead, we'll break people into pairs and then guarantee that each pair has at least one person guessing correctly, except for at most one bad pair.
khanh93 2015-06-23 21:21:45
First: how can we get players into pairs?
mathtastic 2015-06-23 21:22:40
opposite each other
Hydroxide 2015-06-23 21:22:40
have every person look at opposite person
scottistrue 2015-06-23 21:22:40
Opposite in the circle
yulanzhang 2015-06-23 21:22:40
across from each other?
heron 2015-06-23 21:22:40
opposite players pair up?
Longhair343 2015-06-23 21:22:40
opposite?
khanh93 2015-06-23 21:23:13
Some suggested looking at the person next to you,
khanh93 2015-06-23 21:23:15
We can't just have each player look at the person to their left: consider the case where Alejandro is to the left of Billy is to the left of Claire. Claire thinks she's in a pair with Billy, but Billy thinks he's in a pair with Alejandro.
khanh93 2015-06-23 21:23:44
That's trouble! Our argument before relied on these pairs being the same from all perspectives.
khanh93 2015-06-23 21:23:57
But as a bunch of you suggested, each player can look at the person directly across from them. This works out: if Maya is directly across from Elizabeth, then Elizabeth is also directly across from Maya.
LaTeX_turtle 2015-06-23 21:24:07
But it's still symmetrical if you look at opposite how do you decide which partner makes which assumption?
khanh93 2015-06-23 21:24:16
Now we want some way for Elizabeth and Maya to agree on which of them should be left-handed and which of them should be right-handed.
khanh93 2015-06-23 21:24:26
The only tool they have to do this is their knowledge of everybody else's hat colors. How can they do it?
mathtastic 2015-06-23 21:24:58
"if there are more blacks to right than left, then you are a righty, if not then you are a lefty" ALMOST works but doesn't deal with there being an equal number
LaTeX_turtle 2015-06-23 21:24:58
Which is nearer to more black hats.
khanh93 2015-06-23 21:25:12
One thing they might do is divide the rest of the players up into halves, so that one half is to the left of Elizabeth and to the right of Maya, while the other half is to the left of Maya and to the right of Elizabeth.
quartzgirl 2015-06-23 21:25:25
if there are more black hats than white hats, then maya is left-handed, and if there are more white hats than black hats, then, Elizabeth is left-handed
LaTeX_turtle 2015-06-23 21:25:45
Equal # though...
khanh93 2015-06-23 21:25:50
Then all they need is some way to pick one half as more special than the other, and then say that their handedness is the side that has the special half.
khanh93 2015-06-23 21:26:12
We've been suggesting some ideas about counting numbers of black and white hats.
LaTeX_turtle 2015-06-23 21:26:19
And knowing Alfo he'll pick an equal # just to annoy them...
heron 2015-06-23 21:26:43
but it is possible for both halves to be exactly the same
khanh93 2015-06-23 21:27:08
Now, this isn't always possible. If the two halves are identical, we can't call one more special than the other. Excepting that case, what can they do?
Hydroxide 2015-06-23 21:27:19
prove that this can happen for at most one pair
khanh93 2015-06-23 21:27:28
One suggestion is to take the half with a larger number of black hats. This isn't quite as strong as we want, because two halves can have the same number of black hats without being identical.
khanh93 2015-06-23 21:27:41
Instead, let's interpret black hats as $0$s, white hats as $1$s, and each half as an $(\frac n2 -1)$-bit binary number. (The first hat from the left is the first bit and the second hat from the left is the second bit, etc.)
khanh93 2015-06-23 21:28:08
Take the one with smaller value as the special one.
heron 2015-06-23 21:28:16
we can just make a specialness ranking of all of the possible sides, it doesn't matter how we rank them
khanh93 2015-06-23 21:28:21
If you're not familiar with binary numbers, then the following is equivalent: write down an ordered list of all possible arrangments of $\frac n2 -1$ hats and say that one half is more special than the other if it appears earlier in the list.
khanh93 2015-06-23 21:28:35
(The binary number interpretation is just a particular list that's easy to compute.)
khanh93 2015-06-23 21:28:44
Who's with me so far?
khanh93 2015-06-23 21:29:12
Okay; let's push forward.
khanh93 2015-06-23 21:29:34
Notice that we haven't completely defined our strategy yet -- Elizabeth and Maya don't know what to do if they fail to pick a special half.
yulanzhang 2015-06-23 21:29:43
how do you know this will always give 2 distinct numbers?
LaTeX_turtle 2015-06-23 21:29:43
What if the binary #s are the same?
khanh93 2015-06-23 21:29:52
However, we can say that if every pair succeeds in picking a special half, then every pair has exactly one person guess correctly for a total of $\frac n2$ bags of gold.
khanh93 2015-06-23 21:30:09
Now what does it mean for Elizabeth and Maya to fail to pick a special pair?
LaTeX_turtle 2015-06-23 21:30:25
The two pairs are identical.
mathwrite 2015-06-23 21:30:36
it means both halves are the same
khanh93 2015-06-23 21:30:41
They fail iff the sequence of hat colors to Maya's left is the same as the sequence of hat colors to Elizabeth's left. Then the first person to Elizabeth's left is the first bit of the sequence and the first person to Maya's left is the first bit of the sequence, so those people have the same hat color. Notice that those two people form a pair!
khanh93 2015-06-23 21:31:02
If Maya and Elizabeth fail to find a special half, then all of the other pairs have two of the same hat color.
khanh93 2015-06-23 21:31:11
What should our strategy tell Elizabeth and Maya to do?
LaTeX_turtle 2015-06-23 21:31:35
Guess same color.
yank2601 2015-06-23 21:31:35
choose the color of the other person
scottistrue 2015-06-23 21:31:35
Guess each others hats, in case the entire arrangement is symmetrical
khanh93 2015-06-23 21:31:39
(It should tell them to guess that they have the same hat color.)
khanh93 2015-06-23 21:31:43
To prove this strategy works, we'll break our analysis into three cases. The first case should shed some light on the choice we just made.
khanh93 2015-06-23 21:31:49
First, assume that every pair has two of the same color in it. What happens under our strategy?
Longhair343 2015-06-23 21:32:08
alternating?
khanh93 2015-06-23 21:32:22
An alternating pattern has this property. So does a monochromatic one.
LaTeX_turtle 2015-06-23 21:32:27
Angela gets rich that's what.
khanh93 2015-06-23 21:32:35
(Everyone guesses correctly.)
khanh93 2015-06-23 21:32:45
Everyone fails to pick a special half, so everyone guesses that their pair has two of the same color, and they are all correct.
khanh93 2015-06-23 21:32:53
Now, what if exactly one pair has two different colors?
yulanzhang 2015-06-23 21:33:41
everyone else will pick a special side
Hydroxide 2015-06-23 21:33:41
every pair has a special half except that one pair
scottistrue 2015-06-23 21:33:41
They see symmetrical patterns and guess incorrectly, but all the other groups are able to pair off
LaTeX_turtle 2015-06-23 21:33:41
That pair guesses incorrect, but every other pair, one guesses correct. Angela retires.
calculus_riju 2015-06-23 21:33:41
2^k-1 -1
khanh93 2015-06-23 21:33:56
($\frac n2 -1$ guess correctly.)
khanh93 2015-06-23 21:34:20
Recall that we only need $n$ to be even for this strategy to work, not just a power of $2$
khanh93 2015-06-23 21:34:26
Again, let's call the pair that have different colors Elizabeth and Maya. They fail to pick a special half, so they guess that they're the same color. This is false, so both of them guess incorrectly.
khanh93 2015-06-23 21:34:34
However, every other pair can see that Elizabeth and Maya are different. Then for each other pair, their two halves will be different, so they can pick a special half.
khanh93 2015-06-23 21:34:43
(If you like, you can think of them as saying "if Elizabeth is closer on my left, then I'm left-handed, and if Elizabeth is closer on my right, then I'm right handed". )
khanh93 2015-06-23 21:34:51
In this case, we have $\frac n2 - 1$ people guess correctly: one in every pair except for Elizabeth and Maya.
khanh93 2015-06-23 21:35:09
Now for the last case: what if at least two pairs have different colors?
yulanzhang 2015-06-23 21:35:56
everyone picks a special side?
scottistrue 2015-06-23 21:35:56
Everyone can split up, so half guess correctly
khanh93 2015-06-23 21:36:09
($\frac n2$ people guess correctly.)
khanh93 2015-06-23 21:36:12
Each pair can see some other pair with different colors, so each pair successfully picks a special half.
khanh93 2015-06-23 21:36:50
And that's it! Those three cases are comprehensive
khanh93 2015-06-23 21:37:13
Fun theorem: it's true that there is a strategy that works for every $n$
LaTeX_turtle 2015-06-23 21:37:20
You know what I'm going to program a computer to run this kind of thing real quick and find out how much money Angela can expect. Anyone who's interested, I'll send the program to you tomorrow.
khanh93 2015-06-23 21:37:55
The only proof we know requires some involved graph theory; it was found by two people who almost applied to Mathcamp but instead went to other programs.
khanh93 2015-06-23 21:38:08
Thanks so much for sticking around, everybody!
khanh93 2015-06-23 21:38:16
Next week, we'll cover problems 1,2,4.
quartzgirl 2015-06-23 21:38:25
I learned a lot!
quartzgirl 2015-06-23 21:38:29
thanks!!
InCtrl 2015-06-23 21:38:35
wow awesome ja
heron 2015-06-23 21:38:37
you mean, there is a strategy giving floor((n-1)/2) bags for any n?
rt03 2015-06-23 21:38:39
thanks
yulanzhang 2015-06-23 21:38:39
Thank you!
scottistrue 2015-06-23 21:38:40
Thanks everyone
quartzgirl 2015-06-23 21:38:45
bye!
khanh93 2015-06-23 21:38:46
Yes, heron
heron 2015-06-23 21:38:50
thanks!
mathwrite 2015-06-23 21:39:29
goodbye thanks so much!
LauraZed 2015-06-23 21:39:34
Hey all! I'm closing the classroom at 6:40 PT. If you have extra questions, you can post them on our Mathcamp forum, http://artofproblemsolving.com/community/c135_mathcamp, or contact Mathcamp here: http://www.mathcamp.org/contact.php
dsqwerty 2015-06-23 21:39:36
Thanks
Longhair343 2015-06-23 21:40:08
See you all at mathcamp!

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.

ACS WASC
ACCREDITED
SCHOOL

Stay Connected

Subscribe to get news and
updates from AoPS, or Contact Us.
© 2017
AoPS Incorporated
Invalid username
Login to AoPS