Canada/USA Mathcamp Qualifying Quiz Math Jam, Part 2
Go back to the Math Jam ArchiveMathcamp instructors discuss problems #1, #2, and #4 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: Halimeda Glickman-Hoch
LauraZed
2015-06-29 19:21:26
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.
farmerboy
2015-06-29 19:23:41
hello
hello
twistor9
2015-06-29 19:24:46
hello!
hello!
pretzel
2015-06-29 19:24:46
hello
hello
LauraZed
2015-06-29 19:24:48
Hello!
Hello!
LauraZed
2015-06-29 19:24:58
This Math Jam will start in about 6 minutes (7:30 ET, 4:30 PT).
This Math Jam will start in about 6 minutes (7:30 ET, 4:30 PT).
LauraZed
2015-06-29 19:25:46
If you're looking for a course you're enrolled in, go back to AoPS and open your classroom on this page: http://www.artofproblemsolving.com/classroom/index.php
If you're looking for a course you're enrolled in, go back to AoPS and open your classroom on this page: http://www.artofproblemsolving.com/classroom/index.php
LauraZed
2015-06-29 19:26:11
This is a free Math Jam about the Canada/USA Mathcamp 2015 Qualifying Quiz.
This is a free Math Jam about the Canada/USA Mathcamp 2015 Qualifying Quiz.
bluephoenix
2015-06-29 19:26:19
Is this solving problems from the qualifying test?
Is this solving problems from the qualifying test?
LauraZed
2015-06-29 19:26:41
Yup! If anyone hasn't seen it before, you can find the Qualifying Quiz here: http://mathcamp.org/prospectiveapplicants/quiz/index.php
You'll be discussing problems #1, #2, and #4 tonight.
Yup! If anyone hasn't seen it before, you can find the Qualifying Quiz here: http://mathcamp.org/prospectiveapplicants/quiz/index.php
You'll be discussing problems #1, #2, and #4 tonight.
farmerboy
2015-06-29 19:29:16
what do you need to do to get to the camp?
what do you need to do to get to the camp?
LauraZed
2015-06-29 19:30:01
This is the second Math Jam discussing the Qualifying Quiz. If you couldn't make it last week, don't worry! You read through the transcript here later: http://artofproblemsolving.com/school/mathjams-transcripts?id=382
This is the second Math Jam discussing the Qualifying Quiz. If you couldn't make it last week, don't worry! You read through the transcript here later: http://artofproblemsolving.com/school/mathjams-transcripts?id=382
LauraZed
2015-06-29 19:30:36
Okay, let's get this Math Jam started!
Okay, let's get this Math Jam started!
LauraZed
2015-06-29 19:30:43
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-29 19:31:18
Halimeda (Gravity) will be leading the discussion. Halimeda was a Mathcamp student in 2006 and 2007, and has returned in many summers since as a counselor and volunteer. She joined the year-round Mathcamp staff in 2014 as the Assistant Director for External Affairs.
Halimeda (Gravity) will be leading the discussion. Halimeda was a Mathcamp student in 2006 and 2007, and has returned in many summers since as a counselor and volunteer. She joined the year-round Mathcamp staff in 2014 as the Assistant Director for External Affairs.
LauraZed
2015-06-29 19:31:32
Alex (khanh93) will be helping out as well today. Alex 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) will be helping out as well today. Alex 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-29 19:31:52
I'll turn the room over to Halimeda now!
I'll turn the room over to Halimeda now!
Gravity
2015-06-29 19:32:04
Hi Everyone, how are you?
Hi Everyone, how are you?
Gravity
2015-06-29 19:32:20
great
great
Gravity
2015-06-29 19:32:22
To reiterate: We're going over the solutions to problems 1,2, and 4 of the 2015 Mathcamp Qualifying Quiz today. Alex Stark went through problems 3, 5 and 6 last week, and transcripts of both Math Jams will be posted at http://www.mathcamp.org/prospectiveapplicants/quiz/solutions.php
To reiterate: We're going over the solutions to problems 1,2, and 4 of the 2015 Mathcamp Qualifying Quiz today. Alex Stark went through problems 3, 5 and 6 last week, and transcripts of both Math Jams will be posted at http://www.mathcamp.org/prospectiveapplicants/quiz/solutions.php
Gravity
2015-06-29 19:32:34
You can find the Quiz at http://mathcamp.org/prospectiveapplicants/quiz/index.php
You can find the Quiz at http://mathcamp.org/prospectiveapplicants/quiz/index.php
Gravity
2015-06-29 19:32:47
Let's dive right in
Let's dive right in
Gravity
2015-06-29 19:32:49
Problem 1: The Chalkboard Misunderstanding
Problem 1: The Chalkboard Misunderstanding
Gravity
2015-06-29 19:33:02
Problem 1 went as follows: An improper fraction p⁄q (with p > q) is written on a chalkboard. A Mathcamper walks by, sees it, and decides to convert it to a mixed fraction, n r⁄q. She then erases the original.
Problem 1 went as follows: An improper fraction p⁄q (with p > q) is written on a chalkboard. A Mathcamper walks by, sees it, and decides to convert it to a mixed fraction, n r⁄q. She then erases the original.
Gravity
2015-06-29 19:33:08
The next day, another Mathcamper walks by, sees n r⁄q written on the board, and decides that it's a multiplication problem; he evaluates the product, writes it on the board as nr⁄q, and erases the original. Note that if nr ≥ q then we once again have an improper fraction.
The next day, another Mathcamper walks by, sees n r⁄q written on the board, and decides that it's a multiplication problem; he evaluates the product, writes it on the board as nr⁄q, and erases the original. Note that if nr ≥ q then we once again have an improper fraction.
Gravity
2015-06-29 19:33:15
This misunderstanding keeps repeating, until the result is either an integer or a proper fraction. (After that, everyone walking by leaves it alone.) For example, the sequence might be:
This misunderstanding keeps repeating, until the result is either an integer or a proper fraction. (After that, everyone walking by leaves it alone.) For example, the sequence might be:
Gravity
2015-06-29 19:33:21
85⁄6 → 14 1⁄6 → 14⁄6 → 2 2⁄6 → 4⁄6 → END.
85⁄6 → 14 1⁄6 → 14⁄6 → 2 2⁄6 → 4⁄6 → END.
Gravity
2015-06-29 19:33:29
In the example above, we ended up with a fraction that is not in lowest terms.
In the example above, we ended up with a fraction that is not in lowest terms.
Gravity
2015-06-29 19:33:35
a) Now suppose each person reduces his or her fraction to lowest terms before writing it down. Can this affect the final result (if not in our example, then perhaps in a different one)?
a) Now suppose each person reduces his or her fraction to lowest terms before writing it down. Can this affect the final result (if not in our example, then perhaps in a different one)?
Gravity
2015-06-29 19:33:43
b) Suppose the original improper fraction was n⁄2, with n odd. Find, with proof, all values of nfor which the final result will be a proper fraction (not an integer).
Note: whatever condition you come up with, you obviously need to show that, if you start with n⁄2 satisfying this condition, you will end up with a proper fraction. But you also need to show that you are not missing anything. In other words, you will need to prove that, for any fraction n⁄2 not satisfying your condition, you will end up with an integer.
Prove that, for any denominator q ≥ 2, there are infinitely many rational numbers p⁄q for which the process ends with a proper fraction.
(EXTRA) If you feel like playing with this set-up some more and seeing what other results you can derive, please send us anything interesting that you come up with!
b) Suppose the original improper fraction was n⁄2, with n odd. Find, with proof, all values of nfor which the final result will be a proper fraction (not an integer).
Note: whatever condition you come up with, you obviously need to show that, if you start with n⁄2 satisfying this condition, you will end up with a proper fraction. But you also need to show that you are not missing anything. In other words, you will need to prove that, for any fraction n⁄2 not satisfying your condition, you will end up with an integer.
Prove that, for any denominator q ≥ 2, there are infinitely many rational numbers p⁄q for which the process ends with a proper fraction.
(EXTRA) If you feel like playing with this set-up some more and seeing what other results you can derive, please send us anything interesting that you come up with!
Gravity
2015-06-29 19:34:01
Let's start with part a.
Let's start with part a.
Gravity
2015-06-29 19:34:15
Here, we've got two versions of our sequence - one where we reduce at every step, and one where we don't. First, If they differ at any point, we can look at the earliest place in the sequences where they differ. Does that help us?
Here, we've got two versions of our sequence - one where we reduce at every step, and one where we don't. First, If they differ at any point, we can look at the earliest place in the sequences where they differ. Does that help us?
Gravity
2015-06-29 19:36:48
(I'm going to pause for a minute more as people catch up)
(I'm going to pause for a minute more as people catch up)
Gravity
2015-06-29 19:37:22
ok
ok
Gravity
2015-06-29 19:37:28
some people say yes
some people say yes
Gravity
2015-06-29 19:37:29
how?
how?
farmerboy
2015-06-29 19:38:44
yeah
yeah
Longhair343
2015-06-29 19:38:44
Well, we can assume that they differ and work backwards to it, or we have something concrete (the earliest point) to work with
Well, we can assume that they differ and work backwards to it, or we have something concrete (the earliest point) to work with
Gravity
2015-06-29 19:39:50
Right - if the sequences stop being equal, it must be either because they differed after turning an improper fraction into a mixed fraction, or after multiplying the integer part and fractional part of a mixed fraction. This means we can look at each step individually Why can't either of those cause differing values?
Right - if the sequences stop being equal, it must be either because they differed after turning an improper fraction into a mixed fraction, or after multiplying the integer part and fractional part of a mixed fraction. This means we can look at each step individually Why can't either of those cause differing values?
Longhair343
2015-06-29 19:40:20
because the last term was equal, which means, reducing would produce the same result the next time
because the last term was equal, which means, reducing would produce the same result the next time
Gravity
2015-06-29 19:40:37
Exactly - rewriting as mixed fractions is an equality in either case.
Exactly - rewriting as mixed fractions is an equality in either case.
Gravity
2015-06-29 19:40:52
Multiplying the integer part by the fractional part requires a bit more thought but if n p/q = n kp/kq (the fraction on the left being the reduced form of the fraction on the right), then (np)/q=(nkp)/kq.
Multiplying the integer part by the fractional part requires a bit more thought but if n p/q = n kp/kq (the fraction on the left being the reduced form of the fraction on the right), then (np)/q=(nkp)/kq.
Gravity
2015-06-29 19:41:19
with me so far?
with me so far?
Gravity
2015-06-29 19:42:40
good so since reducing doesn't upset either of these steps, reducing will not change the final value
good
so since reducing doesn't upset either of these steps, reducing will not change the final value
Gravity
2015-06-29 19:42:50
From here on out, I'm going to describe the combined process of rewriting as a mixed fraction and then multiplying as a "step" - so in the example given, 85/6 -> 14/6 is one step.
From here on out, I'm going to describe the combined process of rewriting as a mixed fraction and then multiplying as a "step" - so in the example given, 85/6 -> 14/6 is one step.
Gravity
2015-06-29 19:43:01
So now let's consider part (b) - for what odd numbers n does our sequence take n/2 to 1/2. There are two main ways to approach this, and I'd like to look at both of them. First - which numbers n can reach 1/2 in one step?
So now let's consider part (b) - for what odd numbers n does our sequence take n/2 to 1/2. There are two main ways to approach this, and I'd like to look at both of them. First - which numbers n can reach 1/2 in one step?
fractals
2015-06-29 19:43:49
Just n=3
Just n=3
yulanzhang
2015-06-29 19:43:49
3/2
3/2
Gravity
2015-06-29 19:44:01
Right - In the mixed number form the fraction part must be 1/2 so the integer part must have been 1. So only 3/2 works. More generally, for any odd number m, what numbers n can reach m/2 in one step?
Right - In the mixed number form the fraction part must be 1/2 so the integer part must have been 1. So only 3/2 works. More generally, for any odd number m, what numbers n can reach m/2 in one step?
opireader
2015-06-29 19:45:06
2m + 1 = n
2m + 1 = n
fractals
2015-06-29 19:45:06
2m+1, assuming m is odd
2m+1, assuming m is odd
yulanzhang
2015-06-29 19:45:06
n=2m+1?
n=2m+1?
Gravity
2015-06-29 19:45:25
Yes - In the mixed number form the fraction part must be 1/2. Therefore the mixed fraction had to be m 1/2 , the improper fraction had to be (2m+1)/2.
Yes - In the mixed number form the fraction part must be 1/2. Therefore the mixed fraction had to be m 1/2 , the improper fraction had to be (2m+1)/2.
Gravity
2015-06-29 19:45:45
So, by multiplying by 2 then adding 1 to the number that can reach 1/2 in k steps, we get the number that can reach 1/2 in k+1 steps.
So, by multiplying by 2 then adding 1 to the number that can reach 1/2 in k steps, we get the number that can reach 1/2 in k+1 steps.
Gravity
2015-06-29 19:46:05
These numbers are just 1+2+4+...+2^k = 2^(k+1)-1. (You can prove this in many ways including induction).
These numbers are just 1+2+4+...+2^k = 2^(k+1)-1. (You can prove this in many ways including induction).
Gravity
2015-06-29 19:46:29
Now, there's another way to look at this problem - by working in other bases. When computing the sequence starting at p/q, write p in base q - then one step is the same as cutting off the last digit, and multiplying what remains by that last digit.
Now, there's another way to look at this problem - by working in other bases. When computing the sequence starting at p/q, write p in base q - then one step is the same as cutting off the last digit, and multiplying what remains by that last digit.
Gravity
2015-06-29 19:47:14
If that last digit is ever 0, we've reached an integer. What does this tell us about base 2?
If that last digit is ever 0, we've reached an integer. What does this tell us about base 2?
Gravity
2015-06-29 19:48:28
yeah, some of you are saying this "last digit is 0 means integer" thing still holds
yeah, some of you are saying this "last digit is 0 means integer" thing still holds
Gravity
2015-06-29 19:48:46
if we want to end with 1/2 (i.e. not an integer), what does this tell us about base 2?
if we want to end with 1/2 (i.e. not an integer), what does this tell us about base 2?
yulanzhang
2015-06-29 19:49:52
last digit is 1 in base 2?
last digit is 1 in base 2?
farmerboy
2015-06-29 19:49:58
0.1 repeating 1
0.1 repeating 1
Longhair343
2015-06-29 19:50:01
it has to be all 1's
it has to be all 1's
Gravity
2015-06-29 19:50:08
Exactly - the only way to avoid ending on an integer is for every binary digit of n to be 1 - and this is the same answer we got via the other method.
Exactly - the only way to avoid ending on an integer is for every binary digit of n to be 1 - and this is the same answer we got via the other method.
Gravity
2015-06-29 19:50:29
this method can be a little confusing (especially if you're not familiar with binary, and other bases)
this method can be a little confusing (especially if you're not familiar with binary, and other bases)
Gravity
2015-06-29 19:50:47
but it is a very satisfying way of thinking about the problem so worth puzzling over perhaps
but it is a very satisfying way of thinking about the problem so worth puzzling over perhaps
Gravity
2015-06-29 19:51:27
ah, and perhaps a clarification.
ah, and perhaps a clarification.
Gravity
2015-06-29 19:51:43
for this part of the problem, we're wondering about numbers with a denominator of 2
for this part of the problem, we're wondering about numbers with a denominator of 2
Gravity
2015-06-29 19:52:07
thus we are interested in the base 2 expansion of the numerators
thus we are interested in the base 2 expansion of the numerators
Gravity
2015-06-29 19:52:26
ok, lets move on to c)
ok, lets move on to c)
Gravity
2015-06-29 19:52:32
both of our methods for part b can give us an answer here.
both of our methods for part b can give us an answer here.
Gravity
2015-06-29 19:53:09
c) reads
c) reads
Gravity
2015-06-29 19:53:11
(c) Prove that, for any denominator q ≥ 2, there are infinitely many rational numbers p
q
for which the process ends
with a proper fraction.
(c) Prove that, for any denominator q ≥ 2, there are infinitely many rational numbers p
q
for which the process ends
with a proper fraction.
Gravity
2015-06-29 19:53:53
On the one hand, going backwards is no longer unique the way it was when our denominator was 2.
On the one hand, going backwards is no longer unique the way it was when our denominator was 2.
Gravity
2015-06-29 19:54:10
since we can no longer say that the fraction part of a mixed number had to be 1/2
since we can no longer say that the fraction part of a mixed number had to be 1/2
Gravity
2015-06-29 19:54:21
can we nevertheless always find at least one number that leads to an arbitrary p/q in one step?
can we nevertheless always find at least one number that leads to an arbitrary p/q in one step?
Longhair343
2015-06-29 19:57:03
I didn't think of this when I was doing the problems, but any number p whose digits in base q have no 0 would end up as a proper fraction, right?
I didn't think of this when I was doing the problems, but any number p whose digits in base q have no 0 would end up as a proper fraction, right?
Kylen21
2015-06-29 19:57:03
yes
yes
opireader
2015-06-29 19:57:03
(pq+1)/q, of course!
(pq+1)/q, of course!
Gravity
2015-06-29 19:57:21
Right - qp+1. Alternately, what kinds of numbers in base q always end at a fraction?
Right - qp+1. Alternately, what kinds of numbers in base q always end at a fraction?
Gravity
2015-06-29 19:57:53
and if all the digits are 1, there's no way to create a digit that's 0.
and if all the digits are 1, there's no way to create a digit that's 0.
Gravity
2015-06-29 19:58:29
ok
ok
Gravity
2015-06-29 19:58:34
how are we doing so far?
how are we doing so far?
Gravity
2015-06-29 19:59:20
OK! On to Problem 2.
OK! On to Problem 2.
Gravity
2015-06-29 19:59:28
Problem 2: Folding Triangles
Problem 2: Folding Triangles
Gravity
2015-06-29 19:59:44
Gravity
2015-06-29 20:00:04
Gravity
2015-06-29 20:00:40
Gravity
2015-06-29 20:03:18
will one of the other two angles stay the same?
will one of the other two angles stay the same?
yulanzhang
2015-06-29 20:03:57
yes
yes
Konigsberg
2015-06-29 20:03:57
yes, we are sure that one of the angles will stay the same
yes, we are sure that one of the angles will stay the same
cedarwax
2015-06-29 20:03:57
yes
yes
farmerboy
2015-06-29 20:04:04
yes
yes
Gravity
2015-06-29 20:04:07
ok, which one?
ok, which one?
FlakeLCR
2015-06-29 20:04:34
the smaller one
the smaller one
zacchro
2015-06-29 20:04:34
the smaller one
the smaller one
Longhair343
2015-06-29 20:04:34
The smaller one
The smaller one
farmerboy
2015-06-29 20:04:46
smaller one
smaller one
fruitarian
2015-06-29 20:04:46
the smaller one
the smaller one
Gravity
2015-06-29 20:04:49
yes
yes
Gravity
2015-06-29 20:05:00
so two angles of the new triangle will be alpha/2
so two angles of the new triangle will be alpha/2
Gravity
2015-06-29 20:05:03
and beta
and beta
zacchro
2015-06-29 20:05:34
and so the third is gamma+alpha/2
and so the third is gamma+alpha/2
Gravity
2015-06-29 20:05:37
yes
yes
Gravity
2015-06-29 20:05:53
the other angle is $\gamma + \alpha/2$, which is what is needed for the angle sum to be $180$.
the other angle is $\gamma + \alpha/2$, which is what is needed for the angle sum to be $180$.
Gravity
2015-06-29 20:06:33
So, if we fold at vertex $B$ or vertex $C$ instead of vertex $A$, what will be the angles of the new triangle, and why?
So, if we fold at vertex $B$ or vertex $C$ instead of vertex $A$, what will be the angles of the new triangle, and why?
opireader
2015-06-29 20:08:41
If we fold over $B$ and $\alpha<\gamma$, the new angles will be $\alpha,\beta/2,\gamma+\beta/2$
If we fold over $B$ and $\alpha<\gamma$, the new angles will be $\alpha,\beta/2,\gamma+\beta/2$
zacchro
2015-06-29 20:08:41
For similar reasons, it can be $\{\alpha,\frac{\beta}2,\gamma+\frac{\beta}2\}$ and $\{\alpha,\frac{\gamma}2,\beta+\frac{\gamma}2\}$
For similar reasons, it can be $\{\alpha,\frac{\beta}2,\gamma+\frac{\beta}2\}$ and $\{\alpha,\frac{\gamma}2,\beta+\frac{\gamma}2\}$
Gravity
2015-06-29 20:08:59
Great, we know that one angle is halved (the one we're folding in half), and using the same argument we see that the smaller of the two remaining angles stays the same, so the angles will be $(\beta/2, \alpha, \gamma + \beta/2)$ or $(\gamma/2, \alpha, \beta + \gamma/2)$.
Great, we know that one angle is halved (the one we're folding in half), and using the same argument we see that the smaller of the two remaining angles stays the same, so the angles will be $(\beta/2, \alpha, \gamma + \beta/2)$ or $(\gamma/2, \alpha, \beta + \gamma/2)$.
Gravity
2015-06-29 20:09:55
Let's go on to part (b). I'll use the same notation as in part (a).
;(b) You can fold a 45-45-90 triangle at the right angle to obtain another 45-45-90 triangle. Describe all triangles that can be folded in half to get a similar triangle.
We're looking for angles $\alpha \leq \beta \leq \gamma$ that are equal to $\alpha/2, \beta, \gamma + \alpha/2$ in some order, or $\beta/2, \alpha, \gamma + \beta/2$ in some order, or $\gamma/2, \alpha, \beta + \gamma/2$ in some order. That's a lot of possibilities! Can we eliminate any of them?
Let's go on to part (b). I'll use the same notation as in part (a).
;(b) You can fold a 45-45-90 triangle at the right angle to obtain another 45-45-90 triangle. Describe all triangles that can be folded in half to get a similar triangle.
We're looking for angles $\alpha \leq \beta \leq \gamma$ that are equal to $\alpha/2, \beta, \gamma + \alpha/2$ in some order, or $\beta/2, \alpha, \gamma + \beta/2$ in some order, or $\gamma/2, \alpha, \beta + \gamma/2$ in some order. That's a lot of possibilities! Can we eliminate any of them?
Gravity
2015-06-29 20:11:41
how about the first one
how about the first one
Gravity
2015-06-29 20:11:45
alpha/2 etc.
alpha/2 etc.
Kylen21
2015-06-29 20:13:07
180-alpha/2-gamma
180-alpha/2-gamma
zacchro
2015-06-29 20:13:07
impossible since the angle is too small
impossible since the angle is too small
yulanzhang
2015-06-29 20:13:07
since alpha is the smallest none of the other angles listed could equal alpha/2
since alpha is the smallest none of the other angles listed could equal alpha/2
Gravity
2015-06-29 20:13:37
The angle $\alpha/2$ is smaller than all of $\alpha$, $\beta$, and $\gamma$, so there is no way that $\alpha, \beta, \gamma$ can be equal to $\alpha/2, \beta, \gamma + \alpha/2$ in any order. In other words if we want to return to a similar triangle after any number of folds, we can never fold at the
vertex with the smallest angle, because that makes that angle even smaller. And, the angle $\gamma + \beta/2$ is larger than all of $\alpha$, $\beta$, and $\gamma$, so there is no way that $\alpha, \beta, \gamma$ can be equal to $\beta/2, \alpha, \gamma + \beta/2$ in any order.
The angle $\alpha/2$ is smaller than all of $\alpha$, $\beta$, and $\gamma$, so there is no way that $\alpha, \beta, \gamma$ can be equal to $\alpha/2, \beta, \gamma + \alpha/2$ in any order. In other words if we want to return to a similar triangle after any number of folds, we can never fold at the
vertex with the smallest angle, because that makes that angle even smaller. And, the angle $\gamma + \beta/2$ is larger than all of $\alpha$, $\beta$, and $\gamma$, so there is no way that $\alpha, \beta, \gamma$ can be equal to $\beta/2, \alpha, \gamma + \beta/2$ in any order.
howie2000
2015-06-29 20:14:36
nothing can be equal to gamma + alpha/2 because it is bigger than gamma, which is the largest angle
nothing can be equal to gamma + alpha/2 because it is bigger than gamma, which is the largest angle
Gravity
2015-06-29 20:14:42
yes
yes
Gravity
2015-06-29 20:14:49
ok so we only have one situation to deal with
ok so we only have one situation to deal with
Gravity
2015-06-29 20:15:08
we can only fold over the largest angle
we can only fold over the largest angle
Gravity
2015-06-29 20:15:42
i.e. if there is a way to fold the triangle in half to get a similar triangle, then $\gamma$ must be the angle that is folded. Which angles $\alpha \leq \beta \leq \gamma$ are equal to $\gamma/2, \alpha, \beta + \gamma/2$ in some order?
i.e. if there is a way to fold the triangle in half to get a similar triangle, then $\gamma$ must be the angle that is folded. Which angles $\alpha \leq \beta \leq \gamma$ are equal to $\gamma/2, \alpha, \beta + \gamma/2$ in some order?
Longhair343
2015-06-29 20:17:30
a=a b=r/2, r=b+r/2
a=a b=r/2, r=b+r/2
yulanzhang
2015-06-29 20:17:30
alpha = alpha, (gamma/2) = beta, beta+(gamma/2) = gamma
alpha = alpha, (gamma/2) = beta, beta+(gamma/2) = gamma
opireader
2015-06-29 20:17:41
We have $\alpha=\alpha$ automatically.
We have $\alpha=\alpha$ automatically.
opireader
2015-06-29 20:18:02
But we can't have $\gamma=\gamma/2$. So we must have $\gamma=\beta+\gamma/2$ and $\beta=\gamma/2$.
But we can't have $\gamma=\gamma/2$. So we must have $\gamma=\beta+\gamma/2$ and $\beta=\gamma/2$.
Gravity
2015-06-29 20:18:09
Good, we see that $\alpha, \beta, \gamma$ must be equal to $\alpha, \gamma/2, \beta + \gamma/2$ in that order, so $2\beta = \gamma$.
Good, we see that $\alpha, \beta, \gamma$ must be equal to $\alpha, \gamma/2, \beta + \gamma/2$ in that order, so $2\beta = \gamma$.
Gravity
2015-06-29 20:18:17
Given angles $\alpha \leq \beta \leq \gamma$ of a triangle, it's easy to check whether the relation $2\beta = \gamma$ holds; if it does, then we can fold $\gamma$ to get a similar triangle, and if it doesn't, then there is no way to fold to get a similar triangle. What if instead of starting with $\alpha \leq \beta \leq \gamma$ and checking the relation $2\beta = \gamma$, I want to generate all possible $\alpha \leq \beta \leq \gamma$ such that the relation holds? Can we express the solutions in terms of one variable, rather than three variables $\alpha, \beta, \gamma$?
Given angles $\alpha \leq \beta \leq \gamma$ of a triangle, it's easy to check whether the relation $2\beta = \gamma$ holds; if it does, then we can fold $\gamma$ to get a similar triangle, and if it doesn't, then there is no way to fold to get a similar triangle. What if instead of starting with $\alpha \leq \beta \leq \gamma$ and checking the relation $2\beta = \gamma$, I want to generate all possible $\alpha \leq \beta \leq \gamma$ such that the relation holds? Can we express the solutions in terms of one variable, rather than three variables $\alpha, \beta, \gamma$?
fruitarian
2015-06-29 20:21:00
Yes
Yes
farmerboy
2015-06-29 20:21:00
yes
yes
Longhair343
2015-06-29 20:21:09
180-3b, b, 2b, where a=180-3b
180-3b, b, 2b, where a=180-3b
Kylen21
2015-06-29 20:21:09
yes
yes
Gravity
2015-06-29 20:21:15
yes
yes
Gravity
2015-06-29 20:21:19
One way is to say that the angles must be $\beta$, $2\beta$, and $180 - 3\beta$.
One way is to say that the angles must be $\beta$, $2\beta$, and $180 - 3\beta$.
Gravity
2015-06-29 20:21:32
(where alpha is 180-3beta
(where alpha is 180-3beta
Gravity
2015-06-29 20:21:33
)
)
Gravity
2015-06-29 20:21:48
Which values of the variable (in my version, $\beta$) actually produce solution triangles? (Not all real values, certainly!)
Which values of the variable (in my version, $\beta$) actually produce solution triangles? (Not all real values, certainly!)
Gravity
2015-06-29 20:23:10
i hear \beta must be less than 60
i hear \beta must be less than 60
Gravity
2015-06-29 20:23:12
why?
why?
Gravity
2015-06-29 20:23:28
what goes wrong if beta is larger than 60?
what goes wrong if beta is larger than 60?
Kylen21
2015-06-29 20:24:01
if b>60, then b and 2b add up to be greater than 180 degrees
if b>60, then b and 2b add up to be greater than 180 degrees
yulanzhang
2015-06-29 20:24:01
alpha is negative
alpha is negative
fruitarian
2015-06-29 20:24:01
Kylen21
2015-06-29 20:24:01
you can't have a negative angle besides
you can't have a negative angle besides
Gravity
2015-06-29 20:24:41
what do we need to do to ensure that alpha is less than beta?
what do we need to do to ensure that alpha is less than beta?
yulanzhang
2015-06-29 20:26:33
make alpha less than or equal to 45 degrees
make alpha less than or equal to 45 degrees
Gravity
2015-06-29 20:27:05
So, a complete solution for part (b) would prove a statement such as this one: the triangles that can be folded in half to get a similar triangle are those with angles $(180 - 3\beta, \beta, 2\beta)$, where $45 \leq \beta < 60$.
So, a complete solution for part (b) would prove a statement such as this one: the triangles that can be folded in half to get a similar triangle are those with angles $(180 - 3\beta, \beta, 2\beta)$, where $45 \leq \beta < 60$.
Gravity
2015-06-29 20:27:13
nicely done, guys.
nicely done, guys.
Gravity
2015-06-29 20:27:29
lets go on to part c
lets go on to part c
Gravity
2015-06-29 20:27:40
Gravity
2015-06-29 20:28:11
Let's go on to part (c). Those of you who got solutions for part (c), can you write them in terms of one variable as we just did for part (b)?
Let's go on to part (c). Those of you who got solutions for part (c), can you write them in terms of one variable as we just did for part (b)?
Kylen21
2015-06-29 20:29:13
You can just plug the angles in twice, using it as a function
You can just plug the angles in twice, using it as a function
Gravity
2015-06-29 20:29:22
this is more or less true
this is more or less true
Gravity
2015-06-29 20:29:34
the logic for part c is similar to the logic for part b
the logic for part c is similar to the logic for part b
Gravity
2015-06-29 20:29:56
it just involves keeping track of the variables over a couple shifts
it just involves keeping track of the variables over a couple shifts
Gravity
2015-06-29 20:30:24
first of all, All the solutions for (b) are also solutions for (c).
first of all, All the solutions for (b) are also solutions for (c).
Gravity
2015-06-29 20:30:32
The other solutions for (c) can be written as $(\alpha, \frac{1}{5}(180 - \alpha), \frac{4}{5}(180 - \alpha))$ where $0 < \alpha \leq 30$, or as $(\alpha, \frac{2}{5}(180 - \alpha), \frac{3}{5}(180 - \alpha))$ where $0 < \alpha \leq 30$.
The other solutions for (c) can be written as $(\alpha, \frac{1}{5}(180 - \alpha), \frac{4}{5}(180 - \alpha))$ where $0 < \alpha \leq 30$, or as $(\alpha, \frac{2}{5}(180 - \alpha), \frac{3}{5}(180 - \alpha))$ where $0 < \alpha \leq 30$.
Gravity
2015-06-29 20:31:00
We fold the largest angle in $(\alpha, \frac{1}{5}(180 - \alpha), \frac{4}{5}(180 - \alpha))$ to get $(\alpha, \frac{2}{5}(180 - \alpha), \frac{3}{5}(180 - \alpha))$, and then fold the middle angle of that, to get back to $(\alpha, \frac{1}{5}(180 - \alpha), \frac{4}{5}(180 - \alpha)$. If you saw this relationship between solutions, mega-kudos! Not many applicants did, and it's a cool part of the problem.
We fold the largest angle in $(\alpha, \frac{1}{5}(180 - \alpha), \frac{4}{5}(180 - \alpha))$ to get $(\alpha, \frac{2}{5}(180 - \alpha), \frac{3}{5}(180 - \alpha))$, and then fold the middle angle of that, to get back to $(\alpha, \frac{1}{5}(180 - \alpha), \frac{4}{5}(180 - \alpha)$. If you saw this relationship between solutions, mega-kudos! Not many applicants did, and it's a cool part of the problem.
Gravity
2015-06-29 20:32:01
Justifying the answer to part (c) requires a little more work unfortunately, and we might drown a bit in symbols and variables. so i'd like to take a poll. Would you like me to go through the logic quickly?
Justifying the answer to part (c) requires a little more work unfortunately, and we might drown a bit in symbols and variables. so i'd like to take a poll. Would you like me to go through the logic quickly?
Gravity
2015-06-29 20:33:14
ok
ok
Gravity
2015-06-29 20:33:42
i got at least a few yes'es so i'll put up the logic briefly before moving on to d
i got at least a few yes'es so i'll put up the logic briefly before moving on to d
Gravity
2015-06-29 20:33:55
Note from (a) that after a fold, the smallest angle of the new triangle is no greater than the smallest angle of
the old. Thus if we want to return to a similar triangle after any number of folds, we can never fold at the
vertex with the smallest angle, because that makes that angle even smaller. This leaves several ways in which
we may get a similar triangle after two folds.
Note from (a) that after a fold, the smallest angle of the new triangle is no greater than the smallest angle of
the old. Thus if we want to return to a similar triangle after any number of folds, we can never fold at the
vertex with the smallest angle, because that makes that angle even smaller. This leaves several ways in which
we may get a similar triangle after two folds.
Gravity
2015-06-29 20:34:21
(case work essentially... follow the algebra through the other options)
(case work essentially... follow the algebra through the other options)
Gravity
2015-06-29 20:34:40
Case 1. We first fold at B. In that case the largest angle gets larger, so it has to become smaller by the
second fold, which means that the second fold has to be at the (vertex with the) new largest angle ? +?/2.
Also, the smallest angle must still be ?, in other words, we must have ? ? ?/2. In that case, the new
angles ? , ?/2 , ? + ?/2 after the first fold are still in increasing order, and they will be converted to
? , ?/2 + (? + ?/2)/2 , (? + ?/2)/2, i.e., ? , 3?/4 + ?/2, ?/4 + ?/2 by the second fold; note that the
?middle? angle is now the largest. So we need 3?/4 + ?/2 = ?, ?/4 + ?/2 = ?, i.e., ? = 2?/3. Then
2
? = 180 ? 5?/3, so we need 0 < 180 ? 5?/3 ? ?/2 = ?/3, which yields 90 ? ? < 108. So one class of
triangles which can give a similar triangle after two folds has angles 180 ?5?/3 , 2?/3 , ? with ? ? [90, 108),
or equivalently ?, 72 ? 2?/5, 108 ? 3?/5 with ? ? (0, 30], or 180 ? 5?/2 , ? , 3?/2 with ? ? [60, 72).
Case 1. We first fold at B. In that case the largest angle gets larger, so it has to become smaller by the
second fold, which means that the second fold has to be at the (vertex with the) new largest angle ? +?/2.
Also, the smallest angle must still be ?, in other words, we must have ? ? ?/2. In that case, the new
angles ? , ?/2 , ? + ?/2 after the first fold are still in increasing order, and they will be converted to
? , ?/2 + (? + ?/2)/2 , (? + ?/2)/2, i.e., ? , 3?/4 + ?/2, ?/4 + ?/2 by the second fold; note that the
?middle? angle is now the largest. So we need 3?/4 + ?/2 = ?, ?/4 + ?/2 = ?, i.e., ? = 2?/3. Then
2
? = 180 ? 5?/3, so we need 0 < 180 ? 5?/3 ? ?/2 = ?/3, which yields 90 ? ? < 108. So one class of
triangles which can give a similar triangle after two folds has angles 180 ?5?/3 , 2?/3 , ? with ? ? [90, 108),
or equivalently ?, 72 ? 2?/5, 108 ? 3?/5 with ? ? (0, 30], or 180 ? 5?/2 , ? , 3?/2 with ? ? [60, 72).
Gravity
2015-06-29 20:34:52
oops... variables not working out so well
oops... variables not working out so well
Gravity
2015-06-29 20:35:26
ok, given that and the length, I'll rewrite the script and include it in the transcript (with actual variables, since question marks don't help so much)
ok, given that and the length, I'll rewrite the script and include it in the transcript (with actual variables, since question marks don't help so much)
Gravity
2015-06-29 20:35:41
let's go on problem 4 is pretty exciting to me
let's go on
problem 4 is pretty exciting to me
Gravity
2015-06-29 20:35:46
ok
ok
Gravity
2015-06-29 20:35:47
d)
d)
Gravity
2015-06-29 20:36:21
Gravity
2015-06-29 20:36:42
There are many solutions to part (d). One effective strategy is to show that not only can't you fold a 40-60-80 triangle several times to get a 40-60-80 triangle, you actually can't fold *any* triangle to get a 40-60-80 triangle. How would we show this?
There are many solutions to part (d). One effective strategy is to show that not only can't you fold a 40-60-80 triangle several times to get a 40-60-80 triangle, you actually can't fold *any* triangle to get a 40-60-80 triangle. How would we show this?
ptes77
2015-06-29 20:37:37
Work backwards
Work backwards
Gravity
2015-06-29 20:37:44
yes essentially
yes
essentially
Gravity
2015-06-29 20:37:54
The most straightforward way is to start with an arbitrary triangle with angles $\alpha \leq \beta \leq \gamma$, and suppose that $40, 60, 80$ are equal to $\alpha/2, \beta, \gamma + \alpha/2$ in some order, or $\beta/2, \alpha, \gamma + \beta/2$ in some order, or $\gamma/2, \alpha, \beta + \gamma/2$ in some order. We solve for $\alpha, \beta, \gamma$ and get a contradiction in every case.
The most straightforward way is to start with an arbitrary triangle with angles $\alpha \leq \beta \leq \gamma$, and suppose that $40, 60, 80$ are equal to $\alpha/2, \beta, \gamma + \alpha/2$ in some order, or $\beta/2, \alpha, \gamma + \beta/2$ in some order, or $\gamma/2, \alpha, \beta + \gamma/2$ in some order. We solve for $\alpha, \beta, \gamma$ and get a contradiction in every case.
Gravity
2015-06-29 20:38:08
(i.e. numbers that can't make a real triangle)
(i.e. numbers that can't make a real triangle)
Gravity
2015-06-29 20:38:24
A particularly slick solution is to show that whenever we fold, the new triangle has an angle that is at least 90. That means that the new triangle is definitely not 40-60-80. Doesn't the simplicity of this solution blow your mind?
A particularly slick solution is to show that whenever we fold, the new triangle has an angle that is at least 90. That means that the new triangle is definitely not 40-60-80. Doesn't the simplicity of this solution blow your mind?
Gravity
2015-06-29 20:38:54
there are a bunch of other ways to work with part d all of which were pretty cool
there are a bunch of other ways to work with part d all of which were pretty cool
Kylen21
2015-06-29 20:39:20
onwards to #4!
onwards to #4!
Gravity
2015-06-29 20:39:23
indeed!
indeed!
Gravity
2015-06-29 20:39:26
Problem 4: A Royal Tennis Tournament
Problem 4: A Royal Tennis Tournament
Gravity
2015-06-29 20:39:48
Problem 4 was as follows
In King Alfonso's royal court, all nobles are either friends or enemies, following the principle ``The enemy of my enemy is my friend''. (That is, two nobles that share an enemy must be friends, though they can still be friends even if they don't share an enemy.)
Problem 4 was as follows
In King Alfonso's royal court, all nobles are either friends or enemies, following the principle ``The enemy of my enemy is my friend''. (That is, two nobles that share an enemy must be friends, though they can still be friends even if they don't share an enemy.)
Gravity
2015-06-29 20:40:06
For the upcoming royal tennis tournament, the king wants to split up the nobles into pairs of friends. Obviously, if there is an odd number of nobles, pairing them up is impossible. Also, if one noble has no friends at all, then no friendly pairing can be found. But are these the only problems that stand in King Alfonso's way?
For the upcoming royal tennis tournament, the king wants to split up the nobles into pairs of friends. Obviously, if there is an odd number of nobles, pairing them up is impossible. Also, if one noble has no friends at all, then no friendly pairing can be found. But are these the only problems that stand in King Alfonso's way?
Gravity
2015-06-29 20:40:35
(a) Give an example of a friend/enemy network with an even number of nobles, in which each noble has at least
one friend, yet the king still can’t pair up the nobles in a friendly pairing.
(a) Give an example of a friend/enemy network with an even number of nobles, in which each noble has at least
one friend, yet the king still can’t pair up the nobles in a friendly pairing.
Gravity
2015-06-29 20:41:04
Part (a) of this problem is probably the first thing you'd try to do in any case to answer this question: find some examples to get a sense of how these friendship groups can work. What's a third kind of situation in which King Alfonso can't pair up the nobles?
Part (a) of this problem is probably the first thing you'd try to do in any case to answer this question: find some examples to get a sense of how these friendship groups can work. What's a third kind of situation in which King Alfonso can't pair up the nobles?
opireader
2015-06-29 20:42:30
(a) {0, 1, 2, 3, 4, 5} where evens are friends with each other, odds are friends with each other, but no odd is friends with an even.
(a) {0, 1, 2, 3, 4, 5} where evens are friends with each other, odds are friends with each other, but no odd is friends with an even.
Longhair343
2015-06-29 20:42:30
Two Gangs of 3 gangstas!
Two Gangs of 3 gangstas!
Longhair343
2015-06-29 20:42:30
or factions...
or factions...
FlakeLCR
2015-06-29 20:42:30
Two complete graphs of odd order
Two complete graphs of odd order
Longhair343
2015-06-29 20:42:30
3 Cats and 3 Dogs
3 Cats and 3 Dogs
Gravity
2015-06-29 20:42:43
yes
yes
Gravity
2015-06-29 20:42:43
(The smallest example has 6 nobles.)
(The smallest example has 6 nobles.)
Gravity
2015-06-29 20:42:52
Suppose the nobles form 2 factions of 3 nobles each, and each noble is enemies with nobles in the other faction:
Suppose the nobles form 2 factions of 3 nobles each, and each noble is enemies with nobles in the other faction:
Gravity
2015-06-29 20:42:58
Gravity
2015-06-29 20:43:06
(I use solid lines to connect friends and dashed lines to connect enemies.)
(I use solid lines to connect friends and dashed lines to connect enemies.)
Gravity
2015-06-29 20:43:24
After King Alfonso chooses two pairs (one pair from each faction), we always have one noble from each faction left. They are enemies, so they cannot be paired.
After King Alfonso chooses two pairs (one pair from each faction), we always have one noble from each faction left. They are enemies, so they cannot be paired.
Gravity
2015-06-29 20:43:56
there are definitely some other examples
there are definitely some other examples
Gravity
2015-06-29 20:44:08
What's the a more general form of an example that goes wrong for the same reason?
What's the a more general form of an example that goes wrong for the same reason?
opireader
2015-06-29 20:45:59
Where some of the nobles are blue, some are orange, there's an odd number of blue nobles and an odd number of orange nobles, and nobles are friends iff they're the same color.
Where some of the nobles are blue, some are orange, there's an odd number of blue nobles and an odd number of orange nobles, and nobles are friends iff they're the same color.
yulanzhang
2015-06-29 20:45:59
there's a faction with an odd number of people in a group of 6 or more
there's a faction with an odd number of people in a group of 6 or more
Gravity
2015-06-29 20:46:03
yes
yes
Gravity
2015-06-29 20:46:19
it's important that these two groups of friends have no friendships between them
it's important that these two groups of friends have no friendships between them
Gravity
2015-06-29 20:46:45
and then, of course, it's important that these two groups of friends are both odd
and then, of course, it's important that these two groups of friends are both odd
Gravity
2015-06-29 20:47:14
We can have two factions of any size, as long as an odd number of nobles are in each. We can't pair up all the nobles in each faction (one will be left over in each faction), and we can't pair up nobles in different factions. By the way, a noble with no friends is a special case of this: a faction of size one!
We can have two factions of any size, as long as an odd number of nobles are in each. We can't pair up all the nobles in each faction (one will be left over in each faction), and we can't pair up nobles in different factions. By the way, a noble with no friends is a special case of this: a faction of size one!
Gravity
2015-06-29 20:47:40
can we have 3 factions? or 4 factions?
can we have 3 factions? or 4 factions?
opireader
2015-06-29 20:48:40
NOOOOO!!!
NOOOOO!!!
FlakeLCR
2015-06-29 20:48:40
No
No
Longhair343
2015-06-29 20:48:40
No !
No !
Gravity
2015-06-29 20:49:12
no
no
Gravity
2015-06-29 20:49:17
which might be a little surprising
which might be a little surprising
Gravity
2015-06-29 20:49:19
why not?
why not?
Gravity
2015-06-29 20:49:22
what goes wrong?
what goes wrong?
Kylen21
2015-06-29 20:51:22
"the enemy of my enemy is my friend", 2 groups of dogs will have one dog left over each that will unite; likewise for cats
"the enemy of my enemy is my friend", 2 groups of dogs will have one dog left over each that will unite; likewise for cats
yulanzhang
2015-06-29 20:51:22
If one faction has a common enemy with another, they are automatically friends, so the two can be considered 1?
If one faction has a common enemy with another, they are automatically friends, so the two can be considered 1?
opireader
2015-06-29 20:51:22
If a is in Faction 1, b is in Faction 2, c is in Faction 3, then a, b are enemies, b, c are enemies and a, c are enemies. But any two that share an enemy are friends, so this is impossible.
If a is in Faction 1, b is in Faction 2, c is in Faction 3, then a, b are enemies, b, c are enemies and a, c are enemies. But any two that share an enemy are friends, so this is impossible.
Philip7086
2015-06-29 20:51:22
Enemy of enemy is a friend
Enemy of enemy is a friend
Gravity
2015-06-29 20:52:06
If we had three or more factions, we'd be violating the rule ``The enemy of my enemy is my friend'' (EEF). We could look at three nobles all from different factions. A and B, Two nobles in two different factions, have a common enemy C in the third faction, so A and B must be friends.
If we had three or more factions, we'd be violating the rule ``The enemy of my enemy is my friend'' (EEF). We could look at three nobles all from different factions. A and B, Two nobles in two different factions, have a common enemy C in the third faction, so A and B must be friends.
Gravity
2015-06-29 20:53:03
What about the friendships within a faction.
What about the friendships within a faction.
Gravity
2015-06-29 20:53:15
If there are at least two factions
If there are at least two factions
Gravity
2015-06-29 20:53:26
and A and B are in the same faction, what do we know?
and A and B are in the same faction, what do we know?
Gravity
2015-06-29 20:53:33
(about A and B)
(about A and B)
yulanzhang
2015-06-29 20:54:46
they are friends
they are friends
Philip7086
2015-06-29 20:54:46
Us be friends
Us be friends
Kylen21
2015-06-29 20:54:46
they're friends and enemies with C's gang
they're friends and enemies with C's gang
Verjok
2015-06-29 20:54:46
They are friends
They are friends
LaTeX_turtle
2015-06-29 20:54:46
They are friends?
They are friends?
LaTeX_turtle
2015-06-29 20:54:46
They cannot be enemies?
They cannot be enemies?
Gravity
2015-06-29 20:54:51
yes
yes
Gravity
2015-06-29 20:55:49
which tells us that if there are at least two factions, each must be complete: everyone in the same faction must be friends, because they share common enemies in the other faction
which tells us that if there are at least two factions, each must be complete: everyone in the same faction must be friends, because they share common enemies in the other faction
Gravity
2015-06-29 20:56:22
I will mention now that many people assumed there had to be two factions.
I will mention now that many people assumed there had to be two factions.
Gravity
2015-06-29 20:57:14
if this is not the case, we can't use this argument
if this is not the case, we can't use this argument
Kylen21
2015-06-29 20:57:17
there can be one faction!
there can be one faction!
Philip7086
2015-06-29 20:57:17
1 faction?
1 faction?
Longhair343
2015-06-29 20:57:23
Wait, exactly what do we mean factions?
Wait, exactly what do we mean factions?
Gravity
2015-06-29 20:57:27
great question
great question
Gravity
2015-06-29 20:58:38
here, I'm talking about connected components of the graph (for those who know some graph theory)
here, I'm talking about connected components of the graph (for those who know some graph theory)
Gravity
2015-06-29 20:58:40
basically
basically
Gravity
2015-06-29 20:59:04
i am defining a faction to be a group of nobles which are connected by some path of friendships
i am defining a faction to be a group of nobles which are connected by some path of friendships
Gravity
2015-06-29 20:59:35
some people defined it as "a group of nobles that are all freinds with each other and friends with no one outside the faction"
some people defined it as "a group of nobles that are all freinds with each other and friends with no one outside the faction"
Gravity
2015-06-29 20:59:38
which is totally fine
which is totally fine
Gravity
2015-06-29 20:59:56
but you do need to prove that they are all friends with each other (as we did above)
but you do need to prove that they are all friends with each other (as we did above)
Gravity
2015-06-29 21:00:43
we could have one faction for example, where it's just a mishmosh
we could have one faction for example, where it's just a mishmosh
Gravity
2015-06-29 21:00:49
some people are friends
some people are friends
Gravity
2015-06-29 21:00:52
but not everyone
but not everyone
Gravity
2015-06-29 21:01:54
ok we're about to go through the proof that this is the only kind of problematic situation (two factions of odd sizes)
ok
we're about to go through the proof that this is the only kind of problematic situation (two factions of odd sizes)
Gravity
2015-06-29 21:02:05
i expect it to take 10-15 minutes
i expect it to take 10-15 minutes
Gravity
2015-06-29 21:02:40
but it's now 9:00 (the advertised end time) so I wanted to let Laura take the floor briefly in case anyone needs to leave.
but it's now 9:00 (the advertised end time) so I wanted to let Laura take the floor briefly in case anyone needs to leave.
Gravity
2015-06-29 21:04:50
oops, looks like she's busy answering a question perhaps.
oops, looks like she's busy answering a question perhaps.
Gravity
2015-06-29 21:05:50
so I'll quickly ask, how many of you applied to mathcamp this year?
so I'll quickly ask, how many of you applied to mathcamp this year?
Gravity
2015-06-29 21:06:53
great,
great,
Gravity
2015-06-29 21:06:58
and any alums here today?
and any alums here today?
Gravity
2015-06-29 21:07:16
ok
ok
Gravity
2015-06-29 21:07:27
great. If you need to go now, I'm glad you could stop by.
great. If you need to go now, I'm glad you could stop by.
Gravity
2015-06-29 21:07:49
if not, I'm gonna continue on for a few more minutes to talk about how to prove problem 4
if not, I'm gonna continue on for a few more minutes to talk about how to prove problem 4
Gravity
2015-06-29 21:08:15
so now we've thought about this a while
so now we've thought about this a while
Gravity
2015-06-29 21:08:34
(we the hypothetical quiz takers) We fully understand a big class of cases in which there is no friendly pairing. After trying and failing to look for other cases, we decide that this is it, and make a conjecture.
(we the hypothetical quiz takers) We fully understand a big class of cases in which there is no friendly pairing. After trying and failing to look for other cases, we decide that this is it, and make a conjecture.
Gravity
2015-06-29 21:08:49
CONJECTURE: An even number of nobles either (I) has a friendly pairing, or else (II) can be split into two factions of odd size such that nobles are friends only with nobles in their own faction.
CONJECTURE: An even number of nobles either (I) has a friendly pairing, or else (II) can be split into two factions of odd size such that nobles are friends only with nobles in their own faction.
Gravity
2015-06-29 21:09:01
Any ideas on how to prove this?
Any ideas on how to prove this?
LaTeX_turtle
2015-06-29 21:11:27
I think they call this kind of thing a clique in set theory? They're all friends with each other and not friends with the rest?
I think they call this kind of thing a clique in set theory? They're all friends with each other and not friends with the rest?
Longhair343
2015-06-29 21:11:27
Induction on the size of nobles n (or 2n)
Induction on the size of nobles n (or 2n)
Philip7086
2015-06-29 21:11:27
Contradiction?
Contradiction?
FlakeLCR
2015-06-29 21:11:27
assume it is one faction first?
assume it is one faction first?
Gravity
2015-06-29 21:11:44
yeah. there are actually quite a few ways to prove this.
yeah. there are actually quite a few ways to prove this.
Gravity
2015-06-29 21:12:33
you could deal with the one faction case and show that it has a friendly pairing, then use what we've already shown to limit and describe other possible cases
you could deal with the one faction case and show that it has a friendly pairing, then use what we've already shown to limit and describe other possible cases
Gravity
2015-06-29 21:13:02
you can assume there exists a friendly pairing in a group which is *not* of this sort and find a contradiction
you can assume there exists a friendly pairing in a group which is *not* of this sort and find a contradiction
Gravity
2015-06-29 21:13:09
I'm going to explain the induction case
I'm going to explain the induction case
Gravity
2015-06-29 21:13:24
More precisely, if there are $2k$ nobles, we can induct on the value of $k$.
More precisely, if there are $2k$ nobles, we can induct on the value of $k$.
Gravity
2015-06-29 21:13:33
In the base case, $k=1$, we have 2 nobles. If they're friends, we can pair them up. If they're not, then they are two enemy factions of size one.
In the base case, $k=1$, we have 2 nobles. If they're friends, we can pair them up. If they're not, then they are two enemy factions of size one.
Gravity
2015-06-29 21:13:46
Next, we suppose that the conjecture holds for $2k$ nobles. Now take $2k+2$ nobles with an arbitrary configuration of friendships. How can we work in the inductive hypothesis we just made?
Next, we suppose that the conjecture holds for $2k$ nobles. Now take $2k+2$ nobles with an arbitrary configuration of friendships. How can we work in the inductive hypothesis we just made?
Gravity
2015-06-29 21:14:34
in plainer language
in plainer language
Gravity
2015-06-29 21:15:15
knowing we have some group of 2k+2 nobles, how can we get down to 2k of them (since we already know what forms a group of 2k nobles can have)
knowing we have some group of 2k+2 nobles, how can we get down to 2k of them (since we already know what forms a group of 2k nobles can have)
Gravity
2015-06-29 21:16:46
Let's pick a pair of nobles (call them Alice and Bob) that are friends. (We can always do this because in any set of three nobles, there must be one friendship, and we have more than three nobles) Then the inductive hypothesis applies to all the remaining nobles, of which there are $2k$. What can happen now?
Let's pick a pair of nobles (call them Alice and Bob) that are friends. (We can always do this because in any set of three nobles, there must be one friendship, and we have more than three nobles) Then the inductive hypothesis applies to all the remaining nobles, of which there are $2k$. What can happen now?
Philip7086
2015-06-29 21:18:07
Put the 2 remaining ones in one of the factions or 1 each in each of the factions.
Put the 2 remaining ones in one of the factions or 1 each in each of the factions.
Philip7086
2015-06-29 21:18:07
They may be having a friendly pairing or may not be having one.
They may be having a friendly pairing or may not be having one.
Gravity
2015-06-29 21:18:22
well our inductive hypothesis tells us that either they have a friendly pairing or they can be split into two factions of odd size such that nobles are friends only with nobles in their own faction
well our inductive hypothesis tells us that either they have a friendly pairing or they can be split into two factions of odd size such that nobles are friends only with nobles in their own faction
Gravity
2015-06-29 21:18:35
in the first case what do we know?
in the first case what do we know?
Longhair343
2015-06-29 21:19:44
They have friendly pairing
They have friendly pairing
Gravity
2015-06-29 21:20:01
Yes One possibility is that the remaining $2k$ nobles have a friendly pairing. Then all $2k+2$ nobles do, since we can pair Alice and Bob together as well. This falls under case I of the conjecture, so we're happy.
Yes One possibility is that the remaining $2k$ nobles have a friendly pairing. Then all $2k+2$ nobles do, since we can pair Alice and Bob together as well. This falls under case I of the conjecture, so we're happy.
Gravity
2015-06-29 21:20:09
The other possibility is that the remaining $2k$ nobles form two factions of odd size: call them the Blue faction and the Green faction. This tells us what the relationships between those $2k$ nobles are, but not how Alice and Bob feel about them.
The other possibility is that the remaining $2k$ nobles form two factions of odd size: call them the Blue faction and the Green faction. This tells us what the relationships between those $2k$ nobles are, but not how Alice and Bob feel about them.
Gravity
2015-06-29 21:20:17
Philip7086
2015-06-29 21:20:29
Put both of them in one of the factions with which they are friends and we are done.
Put both of them in one of the factions with which they are friends and we are done.
Gravity
2015-06-29 21:20:48
If there is a friendly pairing for all $2k+2$ nobles, what must it look like?
If there is a friendly pairing for all $2k+2$ nobles, what must it look like?
Gravity
2015-06-29 21:22:26
yeah
yeah
Gravity
2015-06-29 21:22:27
Neither the Green faction nor the Blue faction can get paired off on its own, since they have odd sizes. So both factions need help from Alice or Bob. If Alice can find a friend in one faction, and Bob can find a friend in the other, then we have a friendly pairing! (Once again, we're in case I of the conjecture.)
Neither the Green faction nor the Blue faction can get paired off on its own, since they have odd sizes. So both factions need help from Alice or Bob. If Alice can find a friend in one faction, and Bob can find a friend in the other, then we have a friendly pairing! (Once again, we're in case I of the conjecture.)
Gravity
2015-06-29 21:22:47
Why might we fail to find friends for Alice and Bob in different factions? What could happen?
Why might we fail to find friends for Alice and Bob in different factions? What could happen?
Gravity
2015-06-29 21:24:38
yeah I'm hearing a lot of good cases, here
yeah
I'm hearing a lot of good cases, here
Gravity
2015-06-29 21:24:40
One possibility is that Alice has no friends at all aside from Bob (or that Bob has no friends aside from Alice, which can be treated identically). But that would violate ``The enemy of my enemy is my friend'' because Alice, any Green noble, and any Blue noble would be mutual enemies.
One possibility is that Alice has no friends at all aside from Bob (or that Bob has no friends aside from Alice, which can be treated identically). But that would violate ``The enemy of my enemy is my friend'' because Alice, any Green noble, and any Blue noble would be mutual enemies.
Gravity
2015-06-29 21:24:51
Gravity
2015-06-29 21:25:18
The other possibility is that Alice and Bob both only have friends in one faction (say, the Greens). This falls under case II of the conjecture: Alice, Bob, and the Green nobles form one faction, and the Blue nobles form the other faction, and both factions are odd in size.
The other possibility is that Alice and Bob both only have friends in one faction (say, the Greens). This falls under case II of the conjecture: Alice, Bob, and the Green nobles form one faction, and the Blue nobles form the other faction, and both factions are odd in size.
Gravity
2015-06-29 21:25:58
if neither of these cases are true,
if neither of these cases are true,
Gravity
2015-06-29 21:27:01
then we must be back in the situation where Alice is friends with someone in group Green (or Blue... whatever) and Bob is friends with someone in group Blue allowing us to form a friendly pairing
then we must be back in the situation where Alice is friends with someone in group Green (or Blue... whatever) and Bob is friends with someone in group Blue allowing us to form a friendly pairing
Gravity
2015-06-29 21:27:10
thus our conjecture is proven
thus our conjecture is proven
Gravity
2015-06-29 21:27:24
these are the only two possible arrangements of friendship
these are the only two possible arrangements of friendship
Gravity
2015-06-29 21:27:45
We've shown that if $2k$ nobles always fall under case I and case II of the conjecture, then the same is true for $2k+2$ nobles. By induction, the conjecture remains true no matter how many nobles there are.
We've shown that if $2k$ nobles always fall under case I and case II of the conjecture, then the same is true for $2k+2$ nobles. By induction, the conjecture remains true no matter how many nobles there are.
Gravity
2015-06-29 21:28:26
That's all for the explanation part of this Jam, but I'm gonna stay for a bit answering questions (privately and publically) so bring them on out
That's all for the explanation part of this Jam, but I'm gonna stay for a bit answering questions (privately and publically) so bring them on out
Gravity
2015-06-29 21:29:07
If you missed last jam, you can see the transcript here http://www.mathcamp.org/prospectiveapplicants/quiz/solutions.php
If you missed last jam, you can see the transcript here http://www.mathcamp.org/prospectiveapplicants/quiz/solutions.php
Longhair343
2015-06-29 21:31:11
Ummm... I have a question about writing this up. So, you said that I had to prove that everyone in a faction is friends with one another... but I kind of just asserted that as a condition
Ummm... I have a question about writing this up. So, you said that I had to prove that everyone in a faction is friends with one another... but I kind of just asserted that as a condition
yulanzhang
2015-06-29 21:31:11
Generally how many questions do you have to answer and to what extent in order to get into Math Camp?
Generally how many questions do you have to answer and to what extent in order to get into Math Camp?
Gravity
2015-06-29 21:31:14
We don't expect every applicant to solve every problem: in the past, we have sometimes admitted people who could do only half of them, occasionally even fewer. However, don't just solve three or four problems and declare yourself done! The more problems you attempt, the better your chances. We strongly recommend that you try all the problems and send us the results of your efforts: partial solutions, conjectures, methods – everything counts.
We don't expect every applicant to solve every problem: in the past, we have sometimes admitted people who could do only half of them, occasionally even fewer. However, don't just solve three or four problems and declare yourself done! The more problems you attempt, the better your chances. We strongly recommend that you try all the problems and send us the results of your efforts: partial solutions, conjectures, methods – everything counts.
Gravity
2015-06-29 21:31:40
Longhair, that's fine as long as you considered the possibility that some other configuration existed
(you didn't have to use the same termonology we used here)
Longhair, that's fine as long as you considered the possibility that some other configuration existed
(you didn't have to use the same termonology we used here)
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.
