Canada/USA Mathcamp Qualifying Quiz Math Jam, Part 2

Go back to the Math Jam Archive

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

Facilitator: 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.
farmerboy 2015-06-29 19:23:41
hello
twistor9 2015-06-29 19:24:46
hello!
pretzel 2015-06-29 19:24:46
hello
LauraZed 2015-06-29 19:24:48
Hello!
LauraZed 2015-06-29 19:24:58
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
LauraZed 2015-06-29 19:26:11
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?
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.
farmerboy 2015-06-29 19:29:16
what do you need to do to get to the camp?
LauraZed 2015-06-29 19:29:20
You can read more about Mathcamp here: http://mathcamp.org/
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
LauraZed 2015-06-29 19:30:36
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.
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.
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.
LauraZed 2015-06-29 19:31:52
I'll turn the room over to Halimeda now!
Gravity 2015-06-29 19:32:04
Hi Everyone, how are you?
Gravity 2015-06-29 19:32:20
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
Gravity 2015-06-29 19:32:34
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
Gravity 2015-06-29 19:32:49
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.
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.
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:
Gravity 2015-06-29 19:33:21
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.
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)?
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!
Gravity 2015-06-29 19:34:01
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?
Gravity 2015-06-29 19:36:48
(I'm going to pause for a minute more as people catch up)
Gravity 2015-06-29 19:37:22
ok
Gravity 2015-06-29 19:37:28
some people say yes
Gravity 2015-06-29 19:37:29
how?
farmerboy 2015-06-29 19:38:44
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
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?
Longhair343 2015-06-29 19:40:20
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.
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.
Gravity 2015-06-29 19:41:19
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
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.
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?
fractals 2015-06-29 19:43:49
Just n=3
yulanzhang 2015-06-29 19:43:49
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?
opireader 2015-06-29 19:45:06
2m + 1 = n
fractals 2015-06-29 19:45:06
2m+1, assuming m is odd
yulanzhang 2015-06-29 19:45:06
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.
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.
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).
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.
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?
Gravity 2015-06-29 19:48:28
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?
yulanzhang 2015-06-29 19:49:52
last digit is 1 in base 2?
farmerboy 2015-06-29 19:49:58
0.1 repeating 1
Longhair343 2015-06-29 19:50:01
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.
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)
Gravity 2015-06-29 19:50:47
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.
Gravity 2015-06-29 19:51:43
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
Gravity 2015-06-29 19:52:26
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.
Gravity 2015-06-29 19:53:09
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.
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.
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
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?
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?
Kylen21 2015-06-29 19:57:03
yes
opireader 2015-06-29 19:57:03
(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?
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.
Gravity 2015-06-29 19:58:29
ok
Gravity 2015-06-29 19:58:34
how are we doing so far?
Gravity 2015-06-29 19:59:20
OK! On to Problem 2.
Gravity 2015-06-29 19:59:28
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?
yulanzhang 2015-06-29 20:03:57
yes
Konigsberg 2015-06-29 20:03:57
yes, we are sure that one of the angles will stay the same
cedarwax 2015-06-29 20:03:57
yes
farmerboy 2015-06-29 20:04:04
yes
Gravity 2015-06-29 20:04:07
ok, which one?
FlakeLCR 2015-06-29 20:04:34
the smaller one
zacchro 2015-06-29 20:04:34
the smaller one
Longhair343 2015-06-29 20:04:34
The smaller one
farmerboy 2015-06-29 20:04:46
smaller one
fruitarian 2015-06-29 20:04:46
the smaller one
Gravity 2015-06-29 20:04:49
yes
Gravity 2015-06-29 20:05:00
so two angles of the new triangle will be alpha/2
Gravity 2015-06-29 20:05:03
and beta
zacchro 2015-06-29 20:05:34
and so the third is gamma+alpha/2
Gravity 2015-06-29 20:05:37
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$.
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?
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$
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\}$
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)$.
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?
Gravity 2015-06-29 20:11:41
how about the first one
Gravity 2015-06-29 20:11:45
alpha/2 etc.
Kylen21 2015-06-29 20:13:07
180-alpha/2-gamma
zacchro 2015-06-29 20:13:07
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
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.
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
Gravity 2015-06-29 20:14:42
yes
Gravity 2015-06-29 20:14:49
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
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?
Longhair343 2015-06-29 20:17:30
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
opireader 2015-06-29 20:17:41
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$.
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$.
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$?
fruitarian 2015-06-29 20:21:00
Yes
farmerboy 2015-06-29 20:21:00
yes
Longhair343 2015-06-29 20:21:09
180-3b, b, 2b, where a=180-3b
Kylen21 2015-06-29 20:21:09
yes
Gravity 2015-06-29 20:21:15
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$.
Gravity 2015-06-29 20:21:32
(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!)
Gravity 2015-06-29 20:23:10
i hear \beta must be less than 60
Gravity 2015-06-29 20:23:12
why?
Gravity 2015-06-29 20:23:28
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
yulanzhang 2015-06-29 20:24:01
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
Gravity 2015-06-29 20:24:41
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
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$.
Gravity 2015-06-29 20:27:13
nicely done, guys.
Gravity 2015-06-29 20:27:29
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)?
Kylen21 2015-06-29 20:29:13
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
Gravity 2015-06-29 20:29:34
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
Gravity 2015-06-29 20:30:24
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$.
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.
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?
Gravity 2015-06-29 20:33:14
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
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.
Gravity 2015-06-29 20:34:21
(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).
Gravity 2015-06-29 20:34:52
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)
Gravity 2015-06-29 20:35:41
let's go on problem 4 is pretty exciting to me
Gravity 2015-06-29 20:35:46
ok
Gravity 2015-06-29 20:35:47
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?
ptes77 2015-06-29 20:37:37
Work backwards
Gravity 2015-06-29 20:37:44
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.
Gravity 2015-06-29 20:38:08
(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?
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
Kylen21 2015-06-29 20:39:20
onwards to #4!
Gravity 2015-06-29 20:39:23
indeed!
Gravity 2015-06-29 20:39:26
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.)
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?
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.
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?
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.
Longhair343 2015-06-29 20:42:30
Two Gangs of 3 gangstas!
Longhair343 2015-06-29 20:42:30
or factions...
FlakeLCR 2015-06-29 20:42:30
Two complete graphs of odd order
Longhair343 2015-06-29 20:42:30
3 Cats and 3 Dogs
Gravity 2015-06-29 20:42:43
yes
Gravity 2015-06-29 20:42:43
(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:
Gravity 2015-06-29 20:42:58
http://data.artofproblemsolving.com/courses/MathJams/images/royal-tennis-figure-1.png
Gravity 2015-06-29 20:43:06
(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.
Gravity 2015-06-29 20:43:56
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?
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.
yulanzhang 2015-06-29 20:45:59
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
Gravity 2015-06-29 20:46:19
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
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!
Gravity 2015-06-29 20:47:40
can we have 3 factions? or 4 factions?
opireader 2015-06-29 20:48:40
NOOOOO!!!
FlakeLCR 2015-06-29 20:48:40
No
Longhair343 2015-06-29 20:48:40
No !
Gravity 2015-06-29 20:49:12
no
Gravity 2015-06-29 20:49:17
which might be a little surprising
Gravity 2015-06-29 20:49:19
why not?
Gravity 2015-06-29 20:49:22
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
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?
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.
Philip7086 2015-06-29 20:51:22
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.
Gravity 2015-06-29 20:53:03
What about the friendships within a faction.
Gravity 2015-06-29 20:53:15
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?
Gravity 2015-06-29 20:53:33
(about A and B)
yulanzhang 2015-06-29 20:54:46
they are friends
Philip7086 2015-06-29 20:54:46
Us be friends
Kylen21 2015-06-29 20:54:46
they're friends and enemies with C's gang
Verjok 2015-06-29 20:54:46
They are friends
LaTeX_turtle 2015-06-29 20:54:46
They are friends?
LaTeX_turtle 2015-06-29 20:54:46
They cannot be enemies?
Gravity 2015-06-29 20:54:51
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
Gravity 2015-06-29 20:56:22
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
Kylen21 2015-06-29 20:57:17
there can be one faction!
Philip7086 2015-06-29 20:57:17
1 faction?
Longhair343 2015-06-29 20:57:23
Wait, exactly what do we mean factions?
Gravity 2015-06-29 20:57:27
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)
Gravity 2015-06-29 20:58:40
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
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"
Gravity 2015-06-29 20:59:38
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)
Gravity 2015-06-29 21:00:43
we could have one faction for example, where it's just a mishmosh
Gravity 2015-06-29 21:00:49
some people are friends
Gravity 2015-06-29 21:00:52
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)
Gravity 2015-06-29 21:02:05
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.
Gravity 2015-06-29 21:04:50
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?
Gravity 2015-06-29 21:06:53
great,
Gravity 2015-06-29 21:06:58
and any alums here today?
Gravity 2015-06-29 21:07:16
ok
Gravity 2015-06-29 21:07:27
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
Gravity 2015-06-29 21:08:15
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.
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.
Gravity 2015-06-29 21:09:01
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?
Longhair343 2015-06-29 21:11:27
Induction on the size of nobles n (or 2n)
Philip7086 2015-06-29 21:11:27
Contradiction?
FlakeLCR 2015-06-29 21:11:27
assume it is one faction first?
Gravity 2015-06-29 21:11:44
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
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
Gravity 2015-06-29 21:13:09
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$.
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.
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?
Gravity 2015-06-29 21:14:34
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)
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?
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.
Philip7086 2015-06-29 21:18:07
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
Gravity 2015-06-29 21:18:35
in the first case what do we know?
Longhair343 2015-06-29 21:19:44
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.
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.
Gravity 2015-06-29 21:20:17
http://data.artofproblemsolving.com/courses/MathJams/images/royal-tennis-figure-2.png
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.
Gravity 2015-06-29 21:20:48
If there is a friendly pairing for all $2k+2$ nobles, what must it look like?
Gravity 2015-06-29 21:22:26
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.)
Gravity 2015-06-29 21:22:47
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
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.
Gravity 2015-06-29 21:24:51
http://data.artofproblemsolving.com/courses/MathJams/images/royal-tennis-figure-3.png
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.
Gravity 2015-06-29 21:25:58
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
Gravity 2015-06-29 21:27:10
thus our conjecture is proven
Gravity 2015-06-29 21:27:24
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.
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
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
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
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?
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.
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)

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

ACS WASC
ACCREDITED
SCHOOL

Stay Connected

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