Canada/USA Mathcamp Qualifying Quiz Math Jam, Part 1
Go back to the Math Jam ArchiveMathcamp instructors discuss problems #3, #5, and #6 from the 2015 Mathcamp Qualifying Quiz.
Copyright © 2024 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.
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
hi
Eugenis
2015-06-23 19:22:27
Hi LauraZed!
Hi LauraZed!
Bonami2014
2015-06-23 19:22:27
hi
hi
hunter117
2015-06-23 19:22:27
hello!
hello!
LauraZed
2015-06-23 19:22:31
Hello!
Hello!
calculus_riju
2015-06-23 19:22:38
This is my first math jam so is there any rules for this?
This is my first math jam so is there any rules for this?
qwerty733
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.
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.
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.
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?
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).
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?
how hard is this mathjam going to be?
quartzgirl
2015-06-23 19:27:14
are we going to be solving problems?
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!
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?
What is Mathcamp?
farmerboy
2015-06-23 19:29:49
where is this camp?
where is this camp?
lkarhat
2015-06-23 19:29:49
Also where is mathcamp
Also where is mathcamp
chezbgone
2015-06-23 19:30:00
Where can we find the problems?
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.
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
Qualifying Quiz: http://mathcamp.org/prospectiveapplicants/quiz/index.php
LauraZed
2015-06-23 19:31:40
Let's get this Math Jam started!
Let's get this Math Jam started!
mihirb
2015-06-23 19:31:49
YAY!
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.
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.
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.
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!
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!
I'll turn the room over to Alex now!
khanh93
2015-06-23 19:32:59
Thanks Laura!
Thanks Laura!
Eugenis
2015-06-23 19:33:08
Hi Alex!
Hi Alex!
Eugenis
2015-06-23 19:33:10
Hi Gravity!
Hi Gravity!
hunter117
2015-06-23 19:33:13
Hello!!
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.)
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.
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.
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!)
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.
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.
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
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.
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.)
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
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!
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.
Let's start with problem 3, which is short and sweet.
khanh93
2015-06-23 19:35:51
Problem 3
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$.
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?
First, what is the answer?
Longhair343
2015-06-23 19:36:32
The answer is yes, right?... please tell me it is yes!
The answer is yes, right?... please tell me it is yes!
yank2601
2015-06-23 19:36:33
Yes
Yes
Jaksaf
2015-06-23 19:36:35
Yes it is enough.
Yes it is enough.
calculus_riju
2015-06-23 19:36:36
yes
yes
khanh93
2015-06-23 19:36:45
(Yes, that does give us enough information!)
(Yes, that does give us enough information!)
khanh93
2015-06-23 19:36:50
How do we prove it?
How do we prove it?
yulanzhang
2015-06-23 19:37:07
Contradiction?
Contradiction?
qwerty733
2015-06-23 19:37:12
Find a pattern in P(n)
Find a pattern in P(n)
crosbykane
2015-06-23 19:37:12
Take a few examples
Take a few examples
mihirb
2015-06-23 19:37:31
contradiction seems good
contradiction seems good
limelego
2015-06-23 19:37:33
factor out p(n)?
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$.
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
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
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}}$
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
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
Some of you have the correct formula for P_n
khanh93
2015-06-23 19:39:20
Let's see why.
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.
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*}
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}$.
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!
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.
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}$.
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$
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$.
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.
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.
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$.
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$.
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*}
\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!
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?
what about perfect squares?
mihirb
2015-06-23 19:43:24
is there a different way to prove it
is there a different way to prove it
mihirb
2015-06-23 19:43:34
just using a pattern or logic?
just using a pattern or logic?
khanh93
2015-06-23 19:43:45
Our formula for P_n applies to perfect squares,
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
Perfect squares are fine, just the number of factors is odd
khanh93
2015-06-23 19:44:16
Thanks, scottistrue!
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
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...
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
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$.
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
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
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?
err do you mean $m \le n$ so contradiction?
khanh93
2015-06-23 19:46:11
Good catch, briantix
Good catch, briantix
khanh93
2015-06-23 19:46:49
Okay, let's move on to problem 5, then.
Okay, let's move on to problem 5, then.
khanh93
2015-06-23 19:46:54
Problem 5
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?
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
ok
khanh93
2015-06-23 19:47:53
Oh, it seems hsin1030 has it right
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$
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
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.
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).
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?
Let's start with (a). How many dots are there of each color?
tmathman
2015-06-23 19:50:49
32
32
Longhair343
2015-06-23 19:50:49
a) 32
a) 32
mathgenius64
2015-06-23 19:50:49
32
32
opireader
2015-06-23 19:50:49
Umm... there are 32 dots of each color, I believe!
Umm... there are 32 dots of each color, I believe!
dustin8559
2015-06-23 19:50:49
32
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.
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.)
(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.
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.
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
Exactly, opireader
khanh93
2015-06-23 19:52:28
Now we move on to part (b).
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.
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
some variation of pigeonhole
Longhair343
2015-06-23 19:52:52
pigeonhole principle!!!
pigeonhole principle!!!
I_--__--_I
2015-06-23 19:52:52
pigeonhole principle
pigeonhole principle
yank2601
2015-06-23 19:52:58
pigeon's hole?
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.
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?
dirichlet's box principle?
mihirb
2015-06-23 19:53:25
also called dirichlet's principle
also called dirichlet's principle
khanh93
2015-06-23 19:53:39
The pigeonhole principle has many names, apparently
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.[
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?
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?
since all the cards have at least one dot?
khanh93
2015-06-23 19:54:11
That's true, yulanzhang
That's true, yulanzhang
khanh93
2015-06-23 19:54:25
What happens if the complementary card of a set of cards is blank?
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
it's already a proset
flyingsledge
2015-06-23 19:54:35
It's already a proset
It's already a proset
calculus_riju
2015-06-23 19:54:38
its already a proset
its already a proset
khanh93
2015-06-23 19:54:44
Indeed!
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.
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?
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
it is already a proset
I_--__--_I
2015-06-23 19:55:36
yes
yes
farmerboy
2015-06-23 19:55:36
yes
yes
Longhair343
2015-06-23 19:55:36
yes!
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.
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?
(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.
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.)
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
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.
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?
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
Remove both
yank2601
2015-06-23 19:57:10
take the card out entirely
take the card out entirely
khanh93
2015-06-23 19:57:16
(Yes, just remove both copies--this leaves the number of dots even.)
(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.)
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?
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!
intersection!
calculus_riju
2015-06-23 19:58:50
of two sets
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.
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
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
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.
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?
How many different complementary cards can there be?
yank2601
2015-06-23 20:00:28
63
63
scottistrue
2015-06-23 20:00:28
63
63
yank2601
2015-06-23 20:00:28
64
64
scottistrue
2015-06-23 20:00:42
Not 63, since it can be blank
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.
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
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.
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
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!
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).
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
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.
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).
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?
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?
Can we form any prosets with one or two cards?
heron
2015-06-23 20:03:28
no
no
Hydroxide
2015-06-23 20:03:28
no
no
rt03
2015-06-23 20:03:28
no
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.)
(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?
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?
complementary card?
Rmehtany
2015-06-23 20:04:10
1
1
flyingsledge
2015-06-23 20:04:10
1
1
yank2601
2015-06-23 20:04:10
1
1
khanh93
2015-06-23 20:04:18
($1$, the complementary card of the two-card set)
($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}$.
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.
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?
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 !
56 !
Hydroxide
2015-06-23 20:05:30
56
56
mathgenius64
2015-06-23 20:05:30
56
56
Longhair343
2015-06-23 20:05:30
Right? 64-2^3 or 56
Right? 64-2^3 or 56
khanh93
2015-06-23 20:05:42
($56$)
($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?
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
no
rt03
2015-06-23 20:06:05
no
no
mathgenius64
2015-06-23 20:06:05
no otherwise there is already a proset there
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.)
(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.
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?
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
56/60* 60/61 = 56/61
amburger66
2015-06-23 20:07:49
56/61?
56/61?
khanh93
2015-06-23 20:08:03
$\left(\frac{56}{61}\right)$
$\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.
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?
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
48/59
Rmehtany
2015-06-23 20:09:22
48/60
48/60
rt03
2015-06-23 20:09:22
47/61
47/61
calculus_riju
2015-06-23 20:09:22
48/61
48/61
Longhair343
2015-06-23 20:09:22
48/59
48/59
khanh93
2015-06-23 20:09:33
Looks like we've got some confusion in our denominators.
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.
We've already chosen four cards, and started with 63.
Longhair343
2015-06-23 20:09:52
err... there are 59 cards left...
err... there are 59 cards left...
flyingsledge
2015-06-23 20:09:52
You only have 59 cards left to choose from
You only have 59 cards left to choose from
cedarwax
2015-06-23 20:10:26
48/59
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.
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
48/59
khanh93
2015-06-23 20:10:32
$\left(\frac{48}{59}\right)$
$\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.
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?
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)
64 - 2^3 = 63 - (2^3 - 1)
calculus_riju
2015-06-23 20:11:33
how r u getting that 2 power thing?
how r u getting that 2 power thing?
khanh93
2015-06-23 20:11:43
Ah. Let's step back a little.
Ah. Let's step back a little.
khanh93
2015-06-23 20:12:09
There are 2^4 subsets of our four card set.
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|}$
number of subsets of a set $A$ is 2^{|A|}$
Smartwhiz
2015-06-23 20:12:21
2^4=16
2^4=16
khanh93
2015-06-23 20:12:31
Each of them have different complementary cards.
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)
(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?
yeah the empty set though?
calculus_riju
2015-06-23 20:13:04
yes,,so u r subtracting to eliminate them?
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
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
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,
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
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?)
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?
If it was then there would already be a proset?
khanh93
2015-06-23 20:15:09
Right.
Right.
khanh93
2015-06-23 20:15:29
So when i write 64 - 2^4, I might as well write 63 - (2^4 - 1),
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.
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.
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?
How about with $6$ cards?
rt03
2015-06-23 20:17:23
16/29
16/29
quartzgirl
2015-06-23 20:17:23
63 - (2^6 - 1)
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}$)
(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}$.
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
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.
I don't know of any nice closed-form expression for them.
khanh93
2015-06-23 20:18:15
Finally, what about 7 cards?
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!
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!
Calm down... starting at 7 cards, the probability is 1 of course!
Rmehtany
2015-06-23 20:18:25
100%
100%
Hydroxide
2015-06-23 20:18:25
0
0
opireader
2015-06-23 20:18:29
THE PROBABILITY IS 1 BY PART (b).
THE PROBABILITY IS 1 BY PART (b).
khanh93
2015-06-23 20:18:34
(We always get a proset)
(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.
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.
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.
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.
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?
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.
33.
Hydroxide
2015-06-23 20:21:02
the set of all cards having an odd number of dots on them
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
set of all cards containing red dots
Longhair343
2015-06-23 20:21:02
or blue dots
or blue dots
DavidUsa
2015-06-23 20:21:02
The set that alternates?
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)
(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.
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?
What's the problem with red dots?
khanh93
2015-06-23 20:22:14
We could have picked any number
We could have picked any number
khanh93
2015-06-23 20:22:23
Er, I mean color
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
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.
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
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
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?
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.
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?
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?)
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.)
(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.
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.
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
3 card proset
Hydroxide
2015-06-23 20:27:44
err you mean 3-card proset
err you mean 3-card proset
khanh93
2015-06-23 20:27:49
Right, yeah.
Right, yeah.
khanh93
2015-06-23 20:28:12
We've only got 30ish minutes left, so let's get on to problem 6
We've only got 30ish minutes left, so let's get on to problem 6
khanh93
2015-06-23 20:28:19
Problem 6
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).
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.
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.
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.)
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?
Does this strategy force Alfonso to give any bags of gold?
dsqwerty
2015-06-23 20:29:44
no
no
Longhair343
2015-06-23 20:29:44
No... not one!
No... not one!
khanh93
2015-06-23 20:29:49
(No.)
(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.
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.)
(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:
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.
(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.)
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?
can there be no black hats, only white ones?
khanh93
2015-06-23 20:31:16
Any assignment of hats is valid, yeah
Any assignment of hats is valid, yeah
Longhair343
2015-06-23 20:31:26
2^2 ?
2^2 ?
mssmath
2015-06-23 20:31:26
4
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
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
4 strategies, seeing white can lead to guessing either color, the with black
quartzgirl
2015-06-23 20:31:38
4
4
khanh93
2015-06-23 20:31:46
($2^2 = 4$.)
($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.
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
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?
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".
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?
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
Alfonso can just pick the opposite color
Ramanan369
2015-06-23 20:33:06
different color
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]
(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
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?
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
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".)
(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
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
He assigns hats after he hears her strategy
khanh93
2015-06-23 20:34:09
Thanks, flyingsledge
Thanks, flyingsledge
skys
2015-06-23 20:34:26
So the king puts the hats on them after they strategize?
So the king puts the hats on them after they strategize?
khanh93
2015-06-23 20:34:30
Yes.
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.
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
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.
Right on, mathtastic.
khanh93
2015-06-23 20:35:13
I'll say the same thing mathtastic said without the function notation
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.
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.
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.
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
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.
(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?
Let's start with $n = 3$. What's a strategy that works here?
Rmehtany
2015-06-23 20:36:42
guess to your left
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!
"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”
“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
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
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.")
("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.
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.
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.
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.
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.
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.
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.
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$?
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?
whats the strategy?
khanh93
2015-06-23 20:38:58
Our strategy is "Guess the hat color of the person to your left."
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.
("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
No bc he could alternate hats
yank2601
2015-06-23 20:39:07
could be alternating colors
could be alternating colors
mssmath
2015-06-23 20:39:07
no
no
flyingsledge
2015-06-23 20:39:07
The king can just make the players alternate hat colors
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.)
(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.
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?
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?
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
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
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
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
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.
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.
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:
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."
"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.
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.")
("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.
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.)
(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."
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.
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.
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?
Does that cover every case?
khanh93
2015-06-23 20:45:24
Er, when I said "distinct pairs", I meant "nonoverlapping pairs".
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
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
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
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.)
(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.
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
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.
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.
This covers all the cases.
masad24
2015-06-23 20:47:02
yay!
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."
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.
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.
(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.
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
n/2
FlakeLCR
2015-06-23 20:48:39
$\left\lfloor\dfrac{n-1}2\right\rfloor$ is a bound.
$\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
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)
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.
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).)
(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.
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.
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.
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.
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.
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.
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.
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)
(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!
Aha! Sarah sees the same thing!
calculus_riju
2015-06-23 20:50:32
so for every wrong theres a right
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.
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.
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.
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?
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
2^n-1 * n
Longhair343
2015-06-23 20:51:50
n times 2^(n-1)
n times 2^(n-1)
mathtastic
2015-06-23 20:52:32
based on the bound it should be $\frac{n}{2} (2^n)$
based on the bound it should be $\frac{n}{2} (2^n)$
quartzgirl
2015-06-23 20:52:32
n * 2^(n-1)
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)$$
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$.
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.
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)
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}) $$
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?
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.
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.
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?
n*(2^n-1) once again?
LaTeX_turtle
2015-06-23 20:55:05
2^n-1 * n
2^n-1 * n
rt03
2015-06-23 20:55:05
$n(2^(n-1))$
$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?
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
n/2
LaTeX_turtle
2015-06-23 20:55:37
n/2
n/2
rt03
2015-06-23 20:55:37
n/2
n/2
khanh93
2015-06-23 20:55:41
($\frac{n 2^{n-1}}{2^n} = \frac n2$ bags of gold.)
($\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.
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?
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.
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.
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?
But for the even case?
LaTeX_turtle
2015-06-23 20:56:59
But what about evens? Can one invent a counterexample for event?
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$
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.
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
consider all hats being monochromatic
khanh93
2015-06-23 20:57:22
(No.)
(No.)
khanh93
2015-06-23 20:57:26
Consider a hat assignment where every player has the same hat color.
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.
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.
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.
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
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
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$.
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
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?
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.
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.
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.)
(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
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?
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;
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.
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.
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.
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?
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!
That's certainly his goal!
khanh93
2015-06-23 21:03:21
Okay, we've hit our soft deadline of 9 PM
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
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
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.
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.
(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
That would be appreciated
amburger66
2015-06-23 21:04:29
yes please!
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
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!!!!
coool!!!!
khanh93
2015-06-23 21:04:38
Seems like enthusiasm is high.
Seems like enthusiasm is high.
khanh93
2015-06-23 21:04:52
Before, we start, Laura has a quick survey question
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?
How many of you applied to Mathcamp this year?
scottistrue
2015-06-23 21:06:06
I did
I did
heron
2015-06-23 21:06:06
I applied
I applied
dsqwerty
2015-06-23 21:06:06
Me!
Me!
praha2
2015-06-23 21:06:06
me
me
Hydroxide
2015-06-23 21:06:06
me
me
danusv
2015-06-23 21:06:06
me
me
flyingsledge
2015-06-23 21:06:06
I did
I did
opireader
2015-06-23 21:06:06
I did!
I did!
CherryCream
2015-06-23 21:06:06
I did
I did
LauraZed
2015-06-23 21:06:14
Lots of applicants!
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?
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!
Ooh; me!
LauraZed
2015-06-23 21:07:57
Haha
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!
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!
Thanks, Laura!
Gravity
2015-06-23 21:08:46
quick note:
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.
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.
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!
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.
(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.)
(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?
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
induction
Longhair343
2015-06-23 21:12:28
mathematical induction?
mathematical induction?
mathtastic
2015-06-23 21:12:31
induction but good luck with that
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$.
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
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."
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!)
(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:
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.
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.
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
cant do that
Longhair343
2015-06-23 21:14:54
you mean 0!
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
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)
(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
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
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?
And how does the lefties and righties help?
khanh93
2015-06-23 21:16:00
Everybody knows their own handedness
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?
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
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
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.
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!
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
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.)
(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.
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.
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
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.
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$.
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
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?
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.
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
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
Yeah; that works
khanh93
2015-06-23 21:19:37
I'm going to take it in a slightly different direction, though.
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?
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
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
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.
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...
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!
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
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.)
(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.
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).
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.
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?
First: how can we get players into pairs?
mathtastic
2015-06-23 21:22:40
opposite each other
opposite each other
Hydroxide
2015-06-23 21:22:40
have every person look at opposite person
have every person look at opposite person
scottistrue
2015-06-23 21:22:40
Opposite in the circle
Opposite in the circle
yulanzhang
2015-06-23 21:22:40
across from each other?
across from each other?
heron
2015-06-23 21:22:40
opposite players pair up?
opposite players pair up?
Longhair343
2015-06-23 21:22:40
opposite?
opposite?
khanh93
2015-06-23 21:23:13
Some suggested looking at the person next to you,
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.
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.
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.
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?
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.
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?
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
"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.
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.
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
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...
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.
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.
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...
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
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?
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
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.
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.)
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.
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
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.
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.)
(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?
Who's with me so far?
khanh93
2015-06-23 21:29:12
Okay; let's push forward.
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.
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?
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?
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.
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?
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.
The two pairs are identical.
mathwrite
2015-06-23 21:30:36
it means both halves are the same
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!
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.
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?
What should our strategy tell Elizabeth and Maya to do?
LaTeX_turtle
2015-06-23 21:31:35
Guess same color.
Guess same color.
yank2601
2015-06-23 21:31:35
choose the color of the other person
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
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.)
(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.
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?
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?
alternating?
khanh93
2015-06-23 21:32:22
An alternating pattern has this property. So does a monochromatic one.
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.
Angela gets rich that's what.
khanh93
2015-06-23 21:32:35
(Everyone guesses correctly.)
(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.
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?
Now, what if exactly one pair has two different colors?
yulanzhang
2015-06-23 21:33:41
everyone else will pick a special side
everyone else will pick a special side
Hydroxide
2015-06-23 21:33:41
every pair has a special half except that one pair
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
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.
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
2^k-1 -1
khanh93
2015-06-23 21:33:56
($\frac n2 -1$ guess correctly.)
($\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$
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.
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.
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". )
(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.
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?
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?
everyone picks a special side?
scottistrue
2015-06-23 21:35:56
Everyone can split up, so half guess correctly
Everyone can split up, so half guess correctly
khanh93
2015-06-23 21:36:09
($\frac n2$ people guess correctly.)
($\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.
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
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$
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.
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.
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!
Thanks so much for sticking around, everybody!
khanh93
2015-06-23 21:38:16
Next week, we'll cover problems 1,2,4.
Next week, we'll cover problems 1,2,4.
quartzgirl
2015-06-23 21:38:25
I learned a lot!
I learned a lot!
quartzgirl
2015-06-23 21:38:29
thanks!!
thanks!!
InCtrl
2015-06-23 21:38:35
wow awesome ja
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?
you mean, there is a strategy giving floor((n-1)/2) bags for any n?
rt03
2015-06-23 21:38:39
thanks
thanks
yulanzhang
2015-06-23 21:38:39
Thank you!
Thank you!
scottistrue
2015-06-23 21:38:40
Thanks everyone
Thanks everyone
quartzgirl
2015-06-23 21:38:45
bye!
bye!
khanh93
2015-06-23 21:38:46
Yes, heron
Yes, heron
heron
2015-06-23 21:38:50
thanks!
thanks!
mathwrite
2015-06-23 21:39:29
goodbye thanks so much!
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
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
Thanks
Longhair343
2015-06-23 21:40:08
See you all at mathcamp!
See you all at mathcamp!
Copyright © 2024 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.
