Mathcamp 2024 Qualifying Quiz Part 2 Math Jam, Problems 4-6
Go back to the Math Jam ArchiveThis Math Jam will discuss solutions to the second half of the 2024 Mathcamp Qualifying Quiz. Mathcamp is an intensive 5-week-long summer program for mathematically talented high school students. More than just a summer camp, Mathcamp is a vibrant community, made up of a wide variety of people who share a common love of learning and passion for mathematics.
Copyright © 2025 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: AoPS Staff
jwelsh
2024-05-16 18:50:32
Welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam! The Math Jam will begin at 7:00 pm ET (4:00 pm PT). We will cover problems 4-6 today. You can find problems 1-3 in the Math Jam archive!
Welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam! The Math Jam will begin at 7:00 pm ET (4:00 pm PT). We will cover problems 4-6 today. You can find problems 1-3 in the Math Jam archive!
jwelsh
2024-05-16 18:50:47
The classroom is moderated: students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. So, when you send a message, it will not appear immediately, and may not appear at all.
The classroom is moderated: students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. So, when you send a message, it will not appear immediately, and may not appear at all.
andygao100
2024-05-16 18:53:00
hello
hello
nikola_tesla-roadster
2024-05-16 18:53:00
Hiiii
Hiiii
goldendog
2024-05-16 18:53:00
HI
HI
jwelsh
2024-05-16 18:53:11
Hello and welcome! Thanks for joining us!
Hello and welcome! Thanks for joining us!
LostInBali
2024-05-16 18:54:59
this seems cool
this seems cool
jwelsh
2024-05-16 18:55:10
This is very cool! And we're glad you're here for it.
This is very cool! And we're glad you're here for it.
Kai321
2024-05-16 18:56:06
I hope the cake shortage is fixed soon. It's sad that not every camper got a cake slice (Problem 4)
I hope the cake shortage is fixed soon. It's sad that not every camper got a cake slice (Problem 4)
Cerberusman
2024-05-16 19:00:03
Where can I find the transcript of Part 1?
Where can I find the transcript of Part 1?
jwelsh
2024-05-16 19:00:13
In the Math Jam archive, but stay for problems 4-6 first!
In the Math Jam archive, but stay for problems 4-6 first!
jwelsh
2024-05-16 19:00:23
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
jwelsh
2024-05-16 19:00:33
Before I introduce our guests, let me briefly explain how our online classroom works.
Before I introduce our guests, let me briefly explain how our online classroom works.
jwelsh
2024-05-16 19:00:46
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose. You can see a few of these above!
This room is moderated, which means that all your questions and comments come to the moderators. We may share your comments with the whole room if we so choose. You can see a few of these above!
jwelsh
2024-05-16 19:00:55
Also, you'll find that you can adjust the classroom windows in a variety of ways by clicking on the user dropdown menu in the top-right corner of the classroom.
Also, you'll find that you can adjust the classroom windows in a variety of ways by clicking on the user dropdown menu in the top-right corner of the classroom.
jwelsh
2024-05-16 19:01:08
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: www.mathcamp.org
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: www.mathcamp.org
jwelsh
2024-05-16 19:01:20
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
jwelsh
2024-05-16 19:01:44
Each year, Mathcamp creates a Qualifying Quiz, which is the main component of the application process. If you haven't already seen it, you can find the 2024 Quiz problems at https://www.mathcamp.org/qualifying_quiz/ . In this Math Jam, the following Mathcamp staff (all members of this year's Quiz committee) will discuss the problems and their solutions:
Each year, Mathcamp creates a Qualifying Quiz, which is the main component of the application process. If you haven't already seen it, you can find the 2024 Quiz problems at https://www.mathcamp.org/qualifying_quiz/ . In this Math Jam, the following Mathcamp staff (all members of this year's Quiz committee) will discuss the problems and their solutions:
jwelsh
2024-05-16 19:01:59
Dan Gulotta (dgulotta) has been a camper, mentor, and visiting speaker at Mathcamp, most recently in 2021. He is currently a postdoc at the University of Utah, studying number theory and p-adic geometry.
Dan Gulotta (dgulotta) has been a camper, mentor, and visiting speaker at Mathcamp, most recently in 2021. He is currently a postdoc at the University of Utah, studying number theory and p-adic geometry.
jwelsh
2024-05-16 19:02:13
Phoebe Lin (Luraibird49) has been a camper and a JC at Mathcamp. She is about to graduate from the Massachusetts Institute of Technology, studying atmospheric sciences and math.
Phoebe Lin (Luraibird49) has been a camper and a JC at Mathcamp. She is about to graduate from the Massachusetts Institute of Technology, studying atmospheric sciences and math.
jwelsh
2024-05-16 19:02:26
Please give them a warm welcome!
Please give them a warm welcome!
SuperElephant
2024-05-16 19:02:39
Hi!
Hi!
Vincent_Bian
2024-05-16 19:02:39
Hi
Hi
Alexyuan2017
2024-05-16 19:02:39
hewoooo
hewoooo
jwelsh
2024-05-16 19:02:43
Let's turn the room over to Dan now to get us started!
Let's turn the room over to Dan now to get us started!
dgulotta
2024-05-16 19:02:49
Hi everyone! Thanks Jo for the introduction. I'm Dan, and I'll be presenting problems 4 and 6. Phoebe will be presenting problem 5.
Hi everyone! Thanks Jo for the introduction. I'm Dan, and I'll be presenting problems 4 and 6. Phoebe will be presenting problem 5.
dgulotta
2024-05-16 19:02:53
Please feel free to ask questions in the chat at any time!
Please feel free to ask questions in the chat at any time!
dgulotta
2024-05-16 19:02:59
Problem 4: A group of 11 Mathcampers decided to bake a rainbow unicorn sprinkle cake with 10 slices. Unfortunately they cannot split up the slices into smaller pieces, because they do not want to risk upsetting the unicorn. Each Mathcamper wants a slice of the cake (but not more, because Mathcampers aren't greedy). Each Mathcamper helped bake the cake to some extent. The Mathcampers have been assigned fractions $x_1, x_2,\dotsc, x_{11}$ representing their share of the credit in baking the cake, where $0 < x_i < 1/10$ for each $i$, and $x_1 + x_2 + \dotsb + x_{11} = 1$.
Problem 4: A group of 11 Mathcampers decided to bake a rainbow unicorn sprinkle cake with 10 slices. Unfortunately they cannot split up the slices into smaller pieces, because they do not want to risk upsetting the unicorn. Each Mathcamper wants a slice of the cake (but not more, because Mathcampers aren't greedy). Each Mathcamper helped bake the cake to some extent. The Mathcampers have been assigned fractions $x_1, x_2,\dotsc, x_{11}$ representing their share of the credit in baking the cake, where $0 < x_i < 1/10$ for each $i$, and $x_1 + x_2 + \dotsb + x_{11} = 1$.
dgulotta
2024-05-16 19:03:14
(a) How can you randomly distribute the slices of cake such that the $i$th Mathcamper has a probability of exactly $10x_i$ of getting a slice of cake?
(a) How can you randomly distribute the slices of cake such that the $i$th Mathcamper has a probability of exactly $10x_i$ of getting a slice of cake?
dgulotta
2024-05-16 19:03:29
One way to make a random choice is to use a spinner. We divide a circle into 11 pieces, one for each camper. The size of the $i$th piece will be proportional to $x_i$.
One way to make a random choice is to use a spinner. We divide a circle into 11 pieces, one for each camper. The size of the $i$th piece will be proportional to $x_i$.
dgulotta
2024-05-16 19:03:44
dgulotta
2024-05-16 19:03:52
To choose a camper at random, we can spin a "pointer" so that it points in a random direction.
To choose a camper at random, we can spin a "pointer" so that it points in a random direction.
dgulotta
2024-05-16 19:04:01
dgulotta
2024-05-16 19:04:06
So in this case, camper #9 has been selected.
So in this case, camper #9 has been selected.
dgulotta
2024-05-16 19:04:08
But we want to select 10 campers, not just one. How could we do that?
But we want to select 10 campers, not just one. How could we do that?
joeym2011
2024-05-16 19:05:05
make $9$ the only one without cake
make $9$ the only one without cake
eibc
2024-05-16 19:05:05
the one who it lands on is the one who doesn't get cake
the one who it lands on is the one who doesn't get cake
Kai321
2024-05-16 19:05:05
Select one camper to not have cake (though this wouldn't work for next parts)
Select one camper to not have cake (though this wouldn't work for next parts)
dgulotta
2024-05-16 19:05:27
That is one way to do it, but there is another way that generalizes better to part (b).
That is one way to do it, but there is another way that generalizes better to part (b).
eibc
2024-05-16 19:06:11
or have 10 equally spaced pointers
or have 10 equally spaced pointers
Kai321
2024-05-16 19:06:11
"Hop" around the circle 10 times
"Hop" around the circle 10 times
dgulotta
2024-05-16 19:06:16
Instead of having a single arrow, we can have 10 equally spaced arrows.
Instead of having a single arrow, we can have 10 equally spaced arrows.
dgulotta
2024-05-16 19:06:18
In the picture below, every camper except for #7 will get a piece of cake.
In the picture below, every camper except for #7 will get a piece of cake.
dgulotta
2024-05-16 19:06:20
dgulotta
2024-05-16 19:06:44
Will each arrow necessarily point to a different camper? Why or why not?
Will each arrow necessarily point to a different camper? Why or why not?
eibc
2024-05-16 19:07:18
yeah because $0 < x_i < \tfrac{1}{10}$ for all $i$
yeah because $0 < x_i < \tfrac{1}{10}$ for all $i$
admathcamp353
2024-05-16 19:07:18
yes because x_i is less than 1/10
yes because x_i is less than 1/10
dgulotta
2024-05-16 19:07:26
Since each $x_i$ is less than $1/10$, it isn't possible for two pointers to point to the same piece of the circle. So no camper will get more than one slice of cake. The probability that a particular pointer is pointing to the $i$th piece of the circle is $x_i$, so the probability that some pointer is pointing to this piece is $10x_i$, as desired. So we have solved part (a).
Since each $x_i$ is less than $1/10$, it isn't possible for two pointers to point to the same piece of the circle. So no camper will get more than one slice of cake. The probability that a particular pointer is pointing to the $i$th piece of the circle is $x_i$, so the probability that some pointer is pointing to this piece is $10x_i$, as desired. So we have solved part (a).
dgulotta
2024-05-16 19:07:39
(b) Generalize your solution to distribute $k$ slices to $n$ campers, for all $k$ and $n$ with $n > k \ge 1$. As before, the Mathcampers have been assigned fractions $x_1, x_2, \dotsc, x_n$ representing their share of the credit in baking the cake, where $0 < x_i < 1/k$ for each $i$, and $x_1 + \dotsb + x_n = 1$. For each $i$, you want the $i$th Mathcamper to have a probability of exactly $kx_i$ of getting a slice of cake.
(b) Generalize your solution to distribute $k$ slices to $n$ campers, for all $k$ and $n$ with $n > k \ge 1$. As before, the Mathcampers have been assigned fractions $x_1, x_2, \dotsc, x_n$ representing their share of the credit in baking the cake, where $0 < x_i < 1/k$ for each $i$, and $x_1 + \dotsb + x_n = 1$. For each $i$, you want the $i$th Mathcamper to have a probability of exactly $kx_i$ of getting a slice of cake.
dgulotta
2024-05-16 19:07:52
Can we generalize our solution from part (a) to work for any $k$ and $n$?
Can we generalize our solution from part (a) to work for any $k$ and $n$?
NAAUBE
2024-05-16 19:08:36
Yes, by changing the number of arrows
Yes, by changing the number of arrows
Kai321
2024-05-16 19:08:36
do "n" arrows
do "n" arrows
dgulotta
2024-05-16 19:08:46
Yes, if we replace $10$ with $k$ and $11$ with $n$, everything still works.
Yes, if we replace $10$ with $k$ and $11$ with $n$, everything still works.
dgulotta
2024-05-16 19:09:06
So that solves part (b).
So that solves part (b).
dgulotta
2024-05-16 19:09:16
(c) Suppose that, in the setup of part (b), you do not know the value of $k$ (the number of slices). Instead, you will put the Mathcampers in a random order, according to some strategy, and then serve slices of cake in that order until the cake runs out. Is there a way to do this so that for each $i$, the $i$th Mathcamper will have a probability of exactly $kx_i$ of getting a slice of cake — no matter what $k$ turns out to be? (You may still assume that we have $0 < x_i < 1/k$ for all $i$, and $x_1 + \dotsb + x_n = 1$).
(c) Suppose that, in the setup of part (b), you do not know the value of $k$ (the number of slices). Instead, you will put the Mathcampers in a random order, according to some strategy, and then serve slices of cake in that order until the cake runs out. Is there a way to do this so that for each $i$, the $i$th Mathcamper will have a probability of exactly $kx_i$ of getting a slice of cake — no matter what $k$ turns out to be? (You may still assume that we have $0 < x_i < 1/k$ for all $i$, and $x_1 + \dotsb + x_n = 1$).
dgulotta
2024-05-16 19:09:38
While we don't know the exact value of $k$, we can use the inequalities $0 < x_i < 1/k$ to get an upper bound on $k$. What is the largest that $k$ can be, in terms of the $x_i$?
While we don't know the exact value of $k$, we can use the inequalities $0 < x_i < 1/k$ to get an upper bound on $k$. What is the largest that $k$ can be, in terms of the $x_i$?
NAAUBE
2024-05-16 19:10:40
$1/x_i$
$1/x_i$
joeym2011
2024-05-16 19:10:40
$k<\frac1{x_i}$
$k<\frac1{x_i}$
eibc
2024-05-16 19:10:40
$\lceil \tfrac{1}{\max(x_i)} \rceil - 1$
$\lceil \tfrac{1}{\max(x_i)} \rceil - 1$
dgulotta
2024-05-16 19:10:45
We must have $k \le K$, where $K = \left\lfloor 1/(\max_{i} x_i) \right\rfloor$.
We must have $k \le K$, where $K = \left\lfloor 1/(\max_{i} x_i) \right\rfloor$.
dgulotta
2024-05-16 19:10:50
So, any ideas on how to use a spinner to solve this problem?
So, any ideas on how to use a spinner to solve this problem?
MathIsFun286
2024-05-16 19:12:33
use a spinner with K arrows
use a spinner with K arrows
NAAUBE
2024-05-16 19:12:33
Can we use $1/x{max}$ arrows, and number them 1, 2, etc to decide the order?
Can we use $1/x{max}$ arrows, and number them 1, 2, etc to decide the order?
dgulotta
2024-05-16 19:12:36
We make a spinner with $K$ equally spaced arrows labeled $1,2,\dotsc,K$, and use the spinner to choose the order of the first $K$ campers in line. The remaining campers get no cake regardless of $k$, so we place them in an arbitrary order.
We make a spinner with $K$ equally spaced arrows labeled $1,2,\dotsc,K$, and use the spinner to choose the order of the first $K$ campers in line. The remaining campers get no cake regardless of $k$, so we place them in an arbitrary order.
dgulotta
2024-05-16 19:12:48
Again, since $x_i < 1/K$, each arrow in the spinner will point to a different piece of the circle.
Again, since $x_i < 1/K$, each arrow in the spinner will point to a different piece of the circle.
dgulotta
2024-05-16 19:12:58
For any $k \le K$, the probability that one of the first $k$ arrows in the spinner points to the $i$th wedge is $kx_i$, as desired.
For any $k \le K$, the probability that one of the first $k$ arrows in the spinner points to the $i$th wedge is $kx_i$, as desired.
dgulotta
2024-05-16 19:13:17
Any last questions or thoughts on this problem? We'll pause for a minute before moving on.
Any last questions or thoughts on this problem? We'll pause for a minute before moving on.
mynameismaya
2024-05-16 19:13:29
We should have more unicorn problems!!!
We should have more unicorn problems!!!
MathPerson12321
2024-05-16 19:13:43
agree
agree
NAAUBE
2024-05-16 19:14:14
Is it? because if we remove the last arrow, they are not equally spaced anymore. why is this the same as if they were evenly spaced?
Is it? because if we remove the last arrow, they are not equally spaced anymore. why is this the same as if they were evenly spaced?
dgulotta
2024-05-16 19:14:42
The arrows just need to be at least $\max_i x_i$ apart - they don't need to be exactly equally spaced.
The arrows just need to be at least $\max_i x_i$ apart - they don't need to be exactly equally spaced.
admathcamp353
2024-05-16 19:14:59
Would using one spinner and spinning an indefinite number of times work?
Would using one spinner and spinning an indefinite number of times work?
dgulotta
2024-05-16 19:15:37
It think it's tricky to make that work properly - if you do it in the most naive way the probabilities don't come out right
It think it's tricky to make that work properly - if you do it in the most naive way the probabilities don't come out right
dgulotta
2024-05-16 19:16:21
Now I'll turn it over to Phoebe for problem 5.
Now I'll turn it over to Phoebe for problem 5.
Luraibird49
2024-05-16 19:16:34
Thanks Dan! Let's jump into problem 5.
Thanks Dan! Let's jump into problem 5.
Luraibird49
2024-05-16 19:16:40
Shoutout to one of our most prolific graders, Molly, for the solutions and pretty pictures you're about to see!
Shoutout to one of our most prolific graders, Molly, for the solutions and pretty pictures you're about to see!
Luraibird49
2024-05-16 19:16:46
Problem 5
Problem 5
Luraibird49
2024-05-16 19:16:53
Half stitching is a form of embroidery which makes images out of diagonal stitches in a square grid. Our images will all be created from a single thread, which alternates traveling in straight lines (called stitches) along the front and the back of the grid:
Half stitching is a form of embroidery which makes images out of diagonal stitches in a square grid. Our images will all be created from a single thread, which alternates traveling in straight lines (called stitches) along the front and the back of the grid:
Luraibird49
2024-05-16 19:17:00
The front of the grid is where the image is formed. Here, each stitch goes from a point $(x,y)$ either to $(x+1,y+1)$ or $(x−1,y−1).$ We say that we stitch a square if a stitch on the front follows its diagonal (from top right to bottom left or from bottom left to top right).
The front of the grid is where the image is formed. Here, each stitch goes from a point $(x,y)$ either to $(x+1,y+1)$ or $(x−1,y−1).$ We say that we stitch a square if a stitch on the front follows its diagonal (from top right to bottom left or from bottom left to top right).
Luraibird49
2024-05-16 19:17:08
The back of the grid is not part of the image. Here, each stitch can follow any straight line — but it must travel a positive distance, because if you end a stitch where it started, it will unravel.
The back of the grid is not part of the image. Here, each stitch can follow any straight line — but it must travel a positive distance, because if you end a stitch where it started, it will unravel.
Luraibird49
2024-05-16 19:17:16
This problem is about minimizing the total length of thread needed to stitch a given pattern. For example, Figure 1e and Figure 1f (with front stitches in red and back stitches in blue) have the same pattern stitched, but the thread is $2\sqrt{2} + 2\sqrt{5}$ units long in the first case and only $2\sqrt{2} + 2$ units long in the second case.
This problem is about minimizing the total length of thread needed to stitch a given pattern. For example, Figure 1e and Figure 1f (with front stitches in red and back stitches in blue) have the same pattern stitched, but the thread is $2\sqrt{2} + 2\sqrt{5}$ units long in the first case and only $2\sqrt{2} + 2$ units long in the second case.
Luraibird49
2024-05-16 19:17:21
Luraibird49
2024-05-16 19:17:34
Problem 5(a): Show that the minimum length of thread (front and back) needed to stitch every square in an m×n rectangular grid is $mn(\sqrt{2} + 1) − 1.$ An example with $m=3$ and $n=4$ is shown in Figure 1a.
Problem 5(a): Show that the minimum length of thread (front and back) needed to stitch every square in an m×n rectangular grid is $mn(\sqrt{2} + 1) − 1.$ An example with $m=3$ and $n=4$ is shown in Figure 1a.
Luraibird49
2024-05-16 19:17:44
When proving a minimum, we need to show both necessity and sufficiency. In the case of this problem, this means we have to show that we need at least this much thread to stitch the pattern, and that it is possible to stitch the pattern with this much thread. Let's start by showing necessity first.
When proving a minimum, we need to show both necessity and sufficiency. In the case of this problem, this means we have to show that we need at least this much thread to stitch the pattern, and that it is possible to stitch the pattern with this much thread. Let's start by showing necessity first.
Luraibird49
2024-05-16 19:17:54
Consider the front stitches first. The pattern has already been decided for us, so the amount of thread we use on the front stitches is constant regardless of how we decide to stitch the pattern.
Consider the front stitches first. The pattern has already been decided for us, so the amount of thread we use on the front stitches is constant regardless of how we decide to stitch the pattern.
Luraibird49
2024-05-16 19:18:00
How many front stitches are there in total?
How many front stitches are there in total?
joeym2011
2024-05-16 19:18:29
$mn$
$mn$
NAAUBE
2024-05-16 19:18:29
mn
mn
admathcamp353
2024-05-16 19:18:29
mn
mn
genius_007
2024-05-16 19:18:29
$mn$
$mn$
MathIsFun286
2024-05-16 19:18:29
$mn$
$mn$
Luraibird49
2024-05-16 19:18:31
There's one front stitch in each square of a $m \times n$ grid, so there are $mn$ front stitches.
There's one front stitch in each square of a $m \times n$ grid, so there are $mn$ front stitches.
Luraibird49
2024-05-16 19:18:37
How long is a single front stitch?
How long is a single front stitch?
joeym2011
2024-05-16 19:19:03
$\sqrt2$
$\sqrt2$
genius_007
2024-05-16 19:19:03
$\sqrt{2}$
$\sqrt{2}$
Purple8cat
2024-05-16 19:19:03
sqrt(2)
sqrt(2)
MathIsFun286
2024-05-16 19:19:03
$\sqrt{2}$ UNITS
$\sqrt{2}$ UNITS
Super_AA
2024-05-16 19:19:03
$\sqrt(2)$
$\sqrt(2)$
NAAUBE
2024-05-16 19:19:03
$\sqrt{2}$
$\sqrt{2}$
Luraibird49
2024-05-16 19:19:05
Each front stitch is the diagonal of a unit square, so they have length $\sqrt{2}.$
Each front stitch is the diagonal of a unit square, so they have length $\sqrt{2}.$
Luraibird49
2024-05-16 19:19:09
Multiplying those, we get that the front stitches will use $mn\sqrt{2}$ units of thread in total.
Multiplying those, we get that the front stitches will use $mn\sqrt{2}$ units of thread in total.
Luraibird49
2024-05-16 19:19:16
Now onto the back stitches. How many back stitches do we need to connect all the front stitches?
Now onto the back stitches. How many back stitches do we need to connect all the front stitches?
joeym2011
2024-05-16 19:19:35
$mn-1$
$mn-1$
NAAUBE
2024-05-16 19:19:35
$mn-1$
$mn-1$
MathIsFun286
2024-05-16 19:19:35
at least $mn-1$
at least $mn-1$
admathcamp353
2024-05-16 19:19:35
at least mn - 1
at least mn - 1
MathIsFun286
2024-05-16 19:19:35
$mn-1$
$mn-1$
Luraibird49
2024-05-16 19:19:41
Each front stitch has to be followed by a back stitch, except the last front stitch, since we can just end there without stitching on the back again.
Each front stitch has to be followed by a back stitch, except the last front stitch, since we can just end there without stitching on the back again.
Luraibird49
2024-05-16 19:19:45
What is the minimum length for a back stitch?
What is the minimum length for a back stitch?
MathIsFun286
2024-05-16 19:20:08
1
1
admathcamp353
2024-05-16 19:20:08
1
1
NAAUBE
2024-05-16 19:20:08
$1$
$1$
Purple8cat
2024-05-16 19:20:08
1
1
joeym2011
2024-05-16 19:20:08
$1$
$1$
Luraibird49
2024-05-16 19:20:11
It's 1, because that's the minimum distance between two points on a unit grid. Any back stitch shorter than 1 wouldn't be able to reach any other front stitch, so it would be useless.
It's 1, because that's the minimum distance between two points on a unit grid. Any back stitch shorter than 1 wouldn't be able to reach any other front stitch, so it would be useless.
Luraibird49
2024-05-16 19:20:16
So the minimum amount of thread we need to use on the back is $mn-1$ units. Added to the $mn\sqrt{2}$ units on the front, that tells us we need at least $mn(\sqrt{2} + 1) − 1$ units of thread in total - as expected.
So the minimum amount of thread we need to use on the back is $mn-1$ units. Added to the $mn\sqrt{2}$ units on the front, that tells us we need at least $mn(\sqrt{2} + 1) − 1$ units of thread in total - as expected.
Luraibird49
2024-05-16 19:20:29
But our proof isn't finished yet! Now we have to show that this is actually possible.
But our proof isn't finished yet! Now we have to show that this is actually possible.
paixiao
2024-05-16 19:21:06
we can stich everything in the 1st row then go under to the 2nd and so on.
we can stich everything in the 1st row then go under to the 2nd and so on.
Luraibird49
2024-05-16 19:21:09
One way to do so is to stitch row by row: start at the bottom left corner, stitch the row from left to right, move up one unit, stitch the row from right to left, move up one unit, and repeat. It is easy to see that this can be generalized to a grid of any size.
One way to do so is to stitch row by row: start at the bottom left corner, stitch the row from left to right, move up one unit, stitch the row from right to left, move up one unit, and repeat. It is easy to see that this can be generalized to a grid of any size.
Luraibird49
2024-05-16 19:21:13
Luraibird49
2024-05-16 19:21:25
With this method, every back stitch has length 1, so we've achieved the lower bound of $mn(\sqrt{2} + 1) − 1,$ thus proving it is the minimum.
With this method, every back stitch has length 1, so we've achieved the lower bound of $mn(\sqrt{2} + 1) − 1,$ thus proving it is the minimum.
paixiao
2024-05-16 19:21:43
YAY!
YAY!
Luraibird49
2024-05-16 19:21:59
Great! Now what happens with some more complicated patterns?
Great! Now what happens with some more complicated patterns?
Luraibird49
2024-05-16 19:22:08
Problem 5(b):
Problem 5(b):
Luraibird49
2024-05-16 19:22:23
A comb with n teeth is a pattern of width $2n − 1$ and height $2$ that stitches every square in the bottom row and every other square in the top row; an example of this pattern with $n=4$ is shown in Figure 1b.
A comb with n teeth is a pattern of width $2n − 1$ and height $2$ that stitches every square in the bottom row and every other square in the top row; an example of this pattern with $n=4$ is shown in Figure 1b.
Luraibird49
2024-05-16 19:22:34
What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of $n$?
What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of $n$?
Luraibird49
2024-05-16 19:22:49
Let's count the front stitches first. How many front stitches are there in a comb with $n$ teeth, in terms of $n$?
Let's count the front stitches first. How many front stitches are there in a comb with $n$ teeth, in terms of $n$?
MathIsFun286
2024-05-16 19:23:25
3n-1
3n-1
genius_007
2024-05-16 19:23:25
$3n - 1$
$3n - 1$
Luraibird49
2024-05-16 19:23:27
There are $n$ teeth, and each tooth has a stitch underneath it and a stitch to the lower right, forming a L-shape pattern of 3 front stitches for each tooth. The exception is the final tooth, which doesn't have a stitch to the lower right. So that makes $3n-1$ stitches.
There are $n$ teeth, and each tooth has a stitch underneath it and a stitch to the lower right, forming a L-shape pattern of 3 front stitches for each tooth. The exception is the final tooth, which doesn't have a stitch to the lower right. So that makes $3n-1$ stitches.
Luraibird49
2024-05-16 19:23:32
So we'll need $3n-1$ front stitches, and $3n-2$ back stitches to connect them. Using the same logic as part 1, we can find a lower bound on the amount of thread: $(3n - 1)(\sqrt2 + 1) - 1$, which is achieved if every single backstitch has a length of $1$. But is this actually possible?
So we'll need $3n-1$ front stitches, and $3n-2$ back stitches to connect them. Using the same logic as part 1, we can find a lower bound on the amount of thread: $(3n - 1)(\sqrt2 + 1) - 1$, which is achieved if every single backstitch has a length of $1$. But is this actually possible?
MathIsFun286
2024-05-16 19:23:55
no
no
joeym2011
2024-05-16 19:23:55
No
No
admathcamp353
2024-05-16 19:23:55
no
no
NAAUBE
2024-05-16 19:23:55
No
No
Kai321
2024-05-16 19:23:57
no
no
Luraibird49
2024-05-16 19:24:00
Some experimenting will show that it seems to be impossible. But let's prove it a bit more formally.
Some experimenting will show that it seems to be impossible. But let's prove it a bit more formally.
Luraibird49
2024-05-16 19:24:02
Let's think about what we can do with a back stitch of length $1$. Consider the diagram below. After stitching the red front stitch, you will be at one of its endpoints. From there, the possible back stitches of length $1$ are shown as arrows. Using them, you can reach the blue stitches in the highlighted squares.
Let's think about what we can do with a back stitch of length $1$. Consider the diagram below. After stitching the red front stitch, you will be at one of its endpoints. From there, the possible back stitches of length $1$ are shown as arrows. Using them, you can reach the blue stitches in the highlighted squares.
Luraibird49
2024-05-16 19:24:08
Luraibird49
2024-05-16 19:24:22
Notice any patterns with the squares you can reach?
Notice any patterns with the squares you can reach?
MathIsFun286
2024-05-16 19:24:53
opposite colors...
opposite colors...
admathcamp353
2024-05-16 19:24:53
only the ones adjacent
only the ones adjacent
Luraibird49
2024-05-16 19:24:55
They're in a checkerboard pattern, alternating between highlighted and un-highlighted. Parity (oddness and evenness) also alternates like that, so let's try to construct an argument based on parity.
They're in a checkerboard pattern, alternating between highlighted and un-highlighted. Parity (oddness and evenness) also alternates like that, so let's try to construct an argument based on parity.
Luraibird49
2024-05-16 19:25:00
Let's define a point $(x,y)$ as an odd point if $x+y$ is odd, and an even point if $x+y$ is even.
If you start at $(x,y)$, a back stitch of length $1$ brings you to one of four possible points on the grid: $(x+1,y), (x-1,y), (x,y+1), (x,y-1)$. If $x+y$ is odd, then these four points are all even, and vice versa. So a back stitch of length $1$ can connect an odd point and an even point, but it can never connect two odd points or two even points.
Let's define a point $(x,y)$ as an odd point if $x+y$ is odd, and an even point if $x+y$ is even.
If you start at $(x,y)$, a back stitch of length $1$ brings you to one of four possible points on the grid: $(x+1,y), (x-1,y), (x,y+1), (x,y-1)$. If $x+y$ is odd, then these four points are all even, and vice versa. So a back stitch of length $1$ can connect an odd point and an even point, but it can never connect two odd points or two even points.
Luraibird49
2024-05-16 19:25:14
Notice that each front stitch connects $(x,y)$ and $(x+1,y+1)$, for some $x$ and $y$. The sums are $x+y$ and $x+y+2$, so they have the same parity. Parity doesn't change when we stitch a front stitch, so, we can simplify things by defining entire front stitches as odd or even, using the same definition.
Notice that each front stitch connects $(x,y)$ and $(x+1,y+1)$, for some $x$ and $y$. The sums are $x+y$ and $x+y+2$, so they have the same parity. Parity doesn't change when we stitch a front stitch, so, we can simplify things by defining entire front stitches as odd or even, using the same definition.
Luraibird49
2024-05-16 19:25:33
Then, a back stitch of length $1$ can only connect an odd front stitch and an even front stitch.
Back to the comb. If we define the bottom left corner of the comb as $(0,0)$, then we can color the comb like so, with dark squares representing odd front stitches:
Then, a back stitch of length $1$ can only connect an odd front stitch and an even front stitch.
Back to the comb. If we define the bottom left corner of the comb as $(0,0)$, then we can color the comb like so, with dark squares representing odd front stitches:
Luraibird49
2024-05-16 19:25:35
Luraibird49
2024-05-16 19:25:48
Out of the $3n-1$ front stitches, how many are odd and how many are even?
Out of the $3n-1$ front stitches, how many are odd and how many are even?
MathIsFun286
2024-05-16 19:26:20
2n-1 black, n white
2n-1 black, n white
genius_007
2024-05-16 19:26:20
$2n-1$ odd and $n$ even
$2n-1$ odd and $n$ even
joeym2011
2024-05-16 19:26:20
$n$ even and $2n-1$ odd
$n$ even and $2n-1$ odd
RLKC8
2024-05-16 19:26:20
N and 2n-1
N and 2n-1
Luraibird49
2024-05-16 19:26:21
Every front stitch directly underneath a tooth is even, so there are $n$ even front stitches. The remaining $2n-1$ are odd.
Every front stitch directly underneath a tooth is even, so there are $n$ even front stitches. The remaining $2n-1$ are odd.
Luraibird49
2024-05-16 19:26:25
Each back stitch of length $1$ can only connect an odd front stitch and an even front stitch.
Each back stitch of length $1$ can only connect an odd front stitch and an even front stitch.
Luraibird49
2024-05-16 19:26:38
We want to use as many of those as we can, so we connect odd and even front stitches as often as possible. But there are fewer even front stitches than odd ones. After making $2n$ back stitches of length $1$, both ends of every even front stitch have already been used, but there are still some odd front stitches left.
We want to use as many of those as we can, so we connect odd and even front stitches as often as possible. But there are fewer even front stitches than odd ones. After making $2n$ back stitches of length $1$, both ends of every even front stitch have already been used, but there are still some odd front stitches left.
Luraibird49
2024-05-16 19:26:53
The remaining $n-2$ back stitches each connect two odd front stitches - therefore, they must be longer than $1$.
The remaining $n-2$ back stitches each connect two odd front stitches - therefore, they must be longer than $1$.
MathIsFun286
2024-05-16 19:27:11
a back stitch of length $\sqrt{2}$ can connect two stitches of the same parity
a back stitch of length $\sqrt{2}$ can connect two stitches of the same parity
Luraibird49
2024-05-16 19:27:17
What is the second shortest possible length for a back stitch?
What is the second shortest possible length for a back stitch?
Luraibird49
2024-05-16 19:27:21
oops! spoilers
oops! spoilers
NAAUBE
2024-05-16 19:27:30
They must be length $\sqrt{2}$
They must be length $\sqrt{2}$
Luraibird49
2024-05-16 19:27:37
A back stitch of length $\sqrt2$ can connect $(x,y)$ to $(x+1,y+1), (x+1,y-1), (x-1,y+1),$ or $(x-1,y-1)$. In every case, the parity remains the same; that means a back stitch of length $\sqrt2$ should be able to connect two odd front stitches. Promising!
A back stitch of length $\sqrt2$ can connect $(x,y)$ to $(x+1,y+1), (x+1,y-1), (x-1,y+1),$ or $(x-1,y-1)$. In every case, the parity remains the same; that means a back stitch of length $\sqrt2$ should be able to connect two odd front stitches. Promising!
Luraibird49
2024-05-16 19:27:53
Let's say we find a way to stitch the pattern using n back stitches of length $1$, and the remaining $n-2$ back stitches are all length $\sqrt2$.
Let's say we find a way to stitch the pattern using n back stitches of length $1$, and the remaining $n-2$ back stitches are all length $\sqrt2$.
Luraibird49
2024-05-16 19:28:06
Then, the total amount of thread needed would be $(3n-1)\sqrt2$ (for the front stitches) $+ 2n$ (for the back stitches of length $1$) $+ (n-2)\sqrt2$ (for the back stitches of length $\sqrt2$), which simplifies to $(4 \sqrt2+2)n-3\sqrt2$. This is our new lower bound. Is this bound achievable?
Then, the total amount of thread needed would be $(3n-1)\sqrt2$ (for the front stitches) $+ 2n$ (for the back stitches of length $1$) $+ (n-2)\sqrt2$ (for the back stitches of length $\sqrt2$), which simplifies to $(4 \sqrt2+2)n-3\sqrt2$. This is our new lower bound. Is this bound achievable?
MathIsFun286
2024-05-16 19:28:45
yes
yes
NAAUBE
2024-05-16 19:28:45
yes
yes
RLKC8
2024-05-16 19:28:45
Yes?
Yes?
Luraibird49
2024-05-16 19:28:47
Yes, it turns out we can achieve it, if we stitch the pattern like this:
Yes, it turns out we can achieve it, if we stitch the pattern like this:
Luraibird49
2024-05-16 19:28:49
Luraibird49
2024-05-16 19:29:07
Every tooth except the first and last contains one single $\sqrt2$ back stitch, so there are $n-2$ back stitches of length $\sqrt2$, and every other back stitch has length $1$.
Every tooth except the first and last contains one single $\sqrt2$ back stitch, so there are $n-2$ back stitches of length $\sqrt2$, and every other back stitch has length $1$.
Luraibird49
2024-05-16 19:29:15
And since we've just proven we can't do better than that, we have the answer: the minimum length of thread is $(4\sqrt2+2)n-3\sqrt2$.
And since we've just proven we can't do better than that, we have the answer: the minimum length of thread is $(4\sqrt2+2)n-3\sqrt2$.
Luraibird49
2024-05-16 19:29:43
Cool! Let's move on to the next part.
Cool! Let's move on to the next part.
Luraibird49
2024-05-16 19:29:49
Problem 5(c): A tall comb with n teeth is a pattern of width $2n − 1$ and height 3 that stitches every square in the bottom row and every other square in the top two rows; an example of this pattern with $n=4$ is shown in Figure 1c. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of n?
Problem 5(c): A tall comb with n teeth is a pattern of width $2n − 1$ and height 3 that stitches every square in the bottom row and every other square in the top two rows; an example of this pattern with $n=4$ is shown in Figure 1c. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of n?
Luraibird49
2024-05-16 19:30:10
In (b), we found a way to find a lower bound using parity coloring, so let's try that again. When we color in the squares with odd front stitches, the tall comb looks like this:
In (b), we found a way to find a lower bound using parity coloring, so let's try that again. When we color in the squares with odd front stitches, the tall comb looks like this:
Luraibird49
2024-05-16 19:30:12
Luraibird49
2024-05-16 19:30:17
How many front stitches are there in terms of $n$?
How many front stitches are there in terms of $n$?
joeym2011
2024-05-16 19:30:57
$4n-1$
$4n-1$
MathIsFun286
2024-05-16 19:30:57
4n-1
4n-1
NAAUBE
2024-05-16 19:30:57
$4n-1$
$4n-1$
Purple8cat
2024-05-16 19:30:57
4n-1
4n-1
Kai321
2024-05-16 19:30:57
4n-1
4n-1
Luraibird49
2024-05-16 19:30:58
It's very similar to (b). This time, we have a taller four-stitch L-shaped pattern per tooth, minus one for the last tooth, giving $4n-1$ total.
It's very similar to (b). This time, we have a taller four-stitch L-shaped pattern per tooth, minus one for the last tooth, giving $4n-1$ total.
Luraibird49
2024-05-16 19:31:01
Out of those $4n-1$ front stitches, how many are odd and how many are even?
Out of those $4n-1$ front stitches, how many are odd and how many are even?
joeym2011
2024-05-16 19:31:31
$2n$ white squares and $2n-1$ black squares
$2n$ white squares and $2n-1$ black squares
paixiao
2024-05-16 19:31:31
2n-1 and 2n
2n-1 and 2n
MathIsFun286
2024-05-16 19:31:31
2n even, 2n-1 odd, so we can have all length 1 back stitches
2n even, 2n-1 odd, so we can have all length 1 back stitches
NAAUBE
2024-05-16 19:31:31
$2n$ and $2n-1$
$2n$ and $2n-1$
Kai321
2024-05-16 19:31:31
2n, 2n-1
2n, 2n-1
Luraibird49
2024-05-16 19:31:32
Each L-shape contains 2 odd and 2 even front stitches, minus one odd for the last tooth. That's $2n-1$ odd and $2n$ even.
Each L-shape contains 2 odd and 2 even front stitches, minus one odd for the last tooth. That's $2n-1$ odd and $2n$ even.
Luraibird49
2024-05-16 19:31:36
The difference between the number of odd and even front stitches this time is only 1. If we only consider parity, then it seems like it should be possible to arrange the front stitches in order of odd-even-odd...-even-odd, and connect each pair with a back stitch of length 1.
The difference between the number of odd and even front stitches this time is only 1. If we only consider parity, then it seems like it should be possible to arrange the front stitches in order of odd-even-odd...-even-odd, and connect each pair with a back stitch of length 1.
Luraibird49
2024-05-16 19:31:50
If we managed to achieve this, we would get a stitching method using $(4n-1)(\sqrt{2} + 1) − 1$ units of thread, using the same logic as in (a). But is it actually possible?
If we managed to achieve this, we would get a stitching method using $(4n-1)(\sqrt{2} + 1) − 1$ units of thread, using the same logic as in (a). But is it actually possible?
MathIsFun286
2024-05-16 19:32:29
yes
yes
joeym2011
2024-05-16 19:32:29
Yes
Yes
NAAUBE
2024-05-16 19:32:29
Yes!
Yes!
eibc
2024-05-16 19:32:29
yes!
yes!
Luraibird49
2024-05-16 19:32:32
Yes, it turns out it is possible! We can stitch the pattern like this:
Yes, it turns out it is possible! We can stitch the pattern like this:
Luraibird49
2024-05-16 19:32:33
Luraibird49
2024-05-16 19:32:42
Every back stitch has a length of 1, so by the same reasoning as in (a), this is minimal.
Every back stitch has a length of 1, so by the same reasoning as in (a), this is minimal.
admathcamp353
2024-05-16 19:33:12
Are the answers different for $$n=1$$?
Are the answers different for $$n=1$$?
Luraibird49
2024-05-16 19:34:26
Ah, good catch. For at least part (b), if we only consider one tooth, then we can get a more optimal stitching.
Ah, good catch. For at least part (b), if we only consider one tooth, then we can get a more optimal stitching.
joeym2011
2024-05-16 19:34:52
The answer is $2\sqrt2+1$ for $n=1$ in part b. It is unchanged in part c.
The answer is $2\sqrt2+1$ for $n=1$ in part b. It is unchanged in part c.
paixiao
2024-05-16 19:35:24
wait
wait
paixiao
2024-05-16 19:35:24
so if someone submitted the answers
so if someone submitted the answers
paixiao
2024-05-16 19:35:24
and they missed $n=1$ case, they wouldn't get perfect?
and they missed $n=1$ case, they wouldn't get perfect?
Luraibird49
2024-05-16 19:36:25
I think we were mainly looking for reasoning here, so if you saw $n=1,$ give yourself some brownie points!
I think we were mainly looking for reasoning here, so if you saw $n=1,$ give yourself some brownie points!
Luraibird49
2024-05-16 19:36:28
Not everyone got that case
Not everyone got that case
NAAUBE
2024-05-16 19:36:37
Doesn't the general term catch that though?
Doesn't the general term catch that though?
Luraibird49
2024-05-16 19:36:59
Technically, for n = 1, our formula isn’t correct, because we can’t have 2 back stitches of length 1
and −1 back stitch of length 2.
Technically, for n = 1, our formula isn’t correct, because we can’t have 2 back stitches of length 1
and −1 back stitch of length 2.
Luraibird49
2024-05-16 19:37:05
For Part (b)
For Part (b)
Kai321
2024-05-16 19:37:30
the answers are also different for n=0
the answers are also different for n=0
Luraibird49
2024-05-16 19:37:53
Hope that clears things up--let's move on to the next part now!
Hope that clears things up--let's move on to the next part now!
Luraibird49
2024-05-16 19:38:12
Problem 5(d): A wide comb with n teeth is a pattern of width $5n − 4$ and height 2 that stitches every square in the bottom row and every fifth square in the top row; an example of this pattern with $n=3$ is shown in Figure 1d. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of $n$?
Problem 5(d): A wide comb with n teeth is a pattern of width $5n − 4$ and height 2 that stitches every square in the bottom row and every fifth square in the top row; an example of this pattern with $n=3$ is shown in Figure 1d. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of $n$?
Luraibird49
2024-05-16 19:38:39
Since the parity coloring method has worked so well for us so far, let's try it again! When we color in the squares with odd front stitches, the wide comb looks like this:
Since the parity coloring method has worked so well for us so far, let's try it again! When we color in the squares with odd front stitches, the wide comb looks like this:
Luraibird49
2024-05-16 19:38:57
Luraibird49
2024-05-16 19:39:25
How many front stitches are there in terms of $n$?
How many front stitches are there in terms of $n$?
Luraibird49
2024-05-16 19:39:48
Similar to (b) and (c) again - each L-shape contains six front stitches, minus four for the last tooth, which makes $6n-4.$
Similar to (b) and (c) again - each L-shape contains six front stitches, minus four for the last tooth, which makes $6n-4.$
MathIsFun286
2024-05-16 19:39:51
6n-4
6n-4
joeym2011
2024-05-16 19:39:51
$6n-4$
$6n-4$
Luraibird49
2024-05-16 19:39:58
Out of those $6n-4$ front stitches, how many are odd and how many are even?
Out of those $6n-4$ front stitches, how many are odd and how many are even?
Kai321
2024-05-16 19:40:24
black = 3n-2 white = 3n-2
black = 3n-2 white = 3n-2
MathIsFun286
2024-05-16 19:40:24
3n-2 of each
3n-2 of each
shsiliveri
2024-05-16 19:40:24
3n-2 ,3n-2
3n-2 ,3n-2
Luraibird49
2024-05-16 19:40:27
This looks a bit trickier than (c) at first, since the teeth don't all have the same parity. But we can see that regardless of the tooth's parity, each L-shape consists of 3 odd and 3 even front stitches, and the final tooth is always the opposite parity of the square underneath it. That makes a total of $6n-4$ front stitches, and of those, exactly half are odd and half are even.
This looks a bit trickier than (c) at first, since the teeth don't all have the same parity. But we can see that regardless of the tooth's parity, each L-shape consists of 3 odd and 3 even front stitches, and the final tooth is always the opposite parity of the square underneath it. That makes a total of $6n-4$ front stitches, and of those, exactly half are odd and half are even.
Luraibird49
2024-05-16 19:40:38
If we only consider parity, then it seems like it should be possible to arrange the front stitches in order of odd-even-odd...-even, and connect each pair with a back stitch of length 1. This sets our lower bound at $(6n-4)(\sqrt{2}+1)-1,$ using the same logic as in (a).
If we only consider parity, then it seems like it should be possible to arrange the front stitches in order of odd-even-odd...-even, and connect each pair with a back stitch of length 1. This sets our lower bound at $(6n-4)(\sqrt{2}+1)-1,$ using the same logic as in (a).
Luraibird49
2024-05-16 19:40:41
But is this lower bound actually achievable?
But is this lower bound actually achievable?
NAAUBE
2024-05-16 19:41:35
no
no
MathIsFun286
2024-05-16 19:41:35
no
no
Kai321
2024-05-16 19:41:35
no
no
snow52
2024-05-16 19:41:35
no
no
RLKC8
2024-05-16 19:41:35
Wait no
Wait no
Luraibird49
2024-05-16 19:41:39
Some experimentation will show it seems to be impossible. Let's try to prove it a bit more rigorously.
Some experimentation will show it seems to be impossible. Let's try to prove it a bit more rigorously.
Luraibird49
2024-05-16 19:41:43
Consider the upside-down T-shape formed by the middle teeth and the stitches below it, highlighted here in purple:
Consider the upside-down T-shape formed by the middle teeth and the stitches below it, highlighted here in purple:
Luraibird49
2024-05-16 19:41:46
Luraibird49
2024-05-16 19:42:20
It's pretty clear that it's never optimal to stitch part of this T-shape, leave, then stitch the rest of it later. If we do this, our thread will end up further than $\sqrt{2}$ away from the unstitched parts, forcing us to use a very long back stitch. So let's look at how we can stitch the entire T-shape most optimally.
It's pretty clear that it's never optimal to stitch part of this T-shape, leave, then stitch the rest of it later. If we do this, our thread will end up further than $\sqrt{2}$ away from the unstitched parts, forcing us to use a very long back stitch. So let's look at how we can stitch the entire T-shape most optimally.
joeym2011
2024-05-16 19:42:31
No, near each tooth there are three white and one black or vice versa.
No, near each tooth there are three white and one black or vice versa.
NAAUBE
2024-05-16 19:42:31
Start from the bottom left, and you can't do it minimally
Start from the bottom left, and you can't do it minimally
Luraibird49
2024-05-16 19:42:49
Three of these front stitches have the same parity (let's say, WLOG, that they're even), while the remaining one (the one in the middle bottom) is odd.
Three of these front stitches have the same parity (let's say, WLOG, that they're even), while the remaining one (the one in the middle bottom) is odd.
Luraibird49
2024-05-16 19:43:00
There aren't enough odd stitches to alternate between parities. The best we can do is even-odd-even-even - i.e. we need to use at least one back stitch of length at least $\sqrt{2}$ in order to connect two front stitches of the same parity.
There aren't enough odd stitches to alternate between parities. The best we can do is even-odd-even-even - i.e. we need to use at least one back stitch of length at least $\sqrt{2}$ in order to connect two front stitches of the same parity.
NAAUBE
2024-05-16 19:43:17
so you need one length of $\sqrt{2}$
so you need one length of $\sqrt{2}$
Luraibird49
2024-05-16 19:43:24
One back stitch of length $\sqrt{2}$ for each middle tooth means at least $n-2$ of our back stitches need to have length at least $\sqrt{2}.$ Our new lower bound is the old one plus $(n-2)(\sqrt{2}-1),$ which simplifies to $(7\sqrt{2}+5)n-6\sqrt{2}-3.$
One back stitch of length $\sqrt{2}$ for each middle tooth means at least $n-2$ of our back stitches need to have length at least $\sqrt{2}.$ Our new lower bound is the old one plus $(n-2)(\sqrt{2}-1),$ which simplifies to $(7\sqrt{2}+5)n-6\sqrt{2}-3.$
Luraibird49
2024-05-16 19:43:42
Is this lower bound achievable?
Is this lower bound achievable?
RLKC8
2024-05-16 19:44:13
Yes
Yes
joeym2011
2024-05-16 19:44:13
yes
yes
Kai321
2024-05-16 19:44:13
yes
yes
snow52
2024-05-16 19:44:13
yes
yes
Luraibird49
2024-05-16 19:44:16
Yes, it is achievable if we stitch the pattern like this:
Yes, it is achievable if we stitch the pattern like this:
Luraibird49
2024-05-16 19:44:23
Luraibird49
2024-05-16 19:44:45
So we've proven this is the minimum.
So we've proven this is the minimum.
NAAUBE
2024-05-16 19:45:24
Is there no need to prove this for all $n$ more rigorously by something like induction?
Is there no need to prove this for all $n$ more rigorously by something like induction?
Luraibird49
2024-05-16 19:45:34
I think our parity arguments above generalize for all $n.$
I think our parity arguments above generalize for all $n.$
Luraibird49
2024-05-16 19:46:01
But you can also use induction to prove the above!
But you can also use induction to prove the above!
Luraibird49
2024-05-16 19:46:16
Okay, let's move on to the last part of the problem!
Okay, let's move on to the last part of the problem!
Luraibird49
2024-05-16 19:46:23
Problem 5(e): Can you prove anything in general about the minimum length of thread needed to stitch a pattern?
Problem 5(e): Can you prove anything in general about the minimum length of thread needed to stitch a pattern?
Luraibird49
2024-05-16 19:46:40
This final part is an open-ended problem. What have we learned about the minimum length of thread from parts (a), (b), and (c)?
This final part is an open-ended problem. What have we learned about the minimum length of thread from parts (a), (b), and (c)?
MathIsFun286
2024-05-16 19:47:34
Let's consider how many odd squares and how many even squares are stitched
Let's consider how many odd squares and how many even squares are stitched
joeym2011
2024-05-16 19:47:34
It depends on the minimum lengths of the string on the back, which depends on the square parities.
It depends on the minimum lengths of the string on the back, which depends on the square parities.
Luraibird49
2024-05-16 19:48:22
These are good observations!
These are good observations!
Luraibird49
2024-05-16 19:48:35
In summary:
In summary:
Luraibird49
2024-05-16 19:48:50
Absolute lower bound: Any pattern with $n$ front stitches requires at least $n(\sqrt{2}-1)+1$ units.
Absolute lower bound: Any pattern with $n$ front stitches requires at least $n(\sqrt{2}-1)+1$ units.
Luraibird49
2024-05-16 19:48:53
Parity lower bound: If a pattern has $n$ front stitches total, $k$ of which are one parity and $n-k$ of which are the other parity, and $2k<n-1,$ we need at least $n-1-2k$ back stitches of length more than 1. That gives us a new lower bound of $(2n−2k−1)\sqrt{2}+2k.$
Parity lower bound: If a pattern has $n$ front stitches total, $k$ of which are one parity and $n-k$ of which are the other parity, and $2k<n-1,$ we need at least $n-1-2k$ back stitches of length more than 1. That gives us a new lower bound of $(2n−2k−1)\sqrt{2}+2k.$
Luraibird49
2024-05-16 19:49:09
There are patterns where achieving even the parity lower bound is impossible.
There are patterns where achieving even the parity lower bound is impossible.
Luraibird49
2024-05-16 19:49:37
Let's pause for some more questions on this part.
Let's pause for some more questions on this part.
Luraibird49
2024-05-16 19:49:43
this question!
this question!
NAAUBE
2024-05-16 19:49:50
How many unique proofs for this did you receive?
How many unique proofs for this did you receive?
Luraibird49
2024-05-16 19:50:29
So many!!! Lots of good ideas and different ways of thinking about the problem -- we were really excited about reading all of the different solutions
So many!!! Lots of good ideas and different ways of thinking about the problem -- we were really excited about reading all of the different solutions
paixiao
2024-05-16 19:50:51
WHOA! maybe 1000?
WHOA! maybe 1000?
Luraibird49
2024-05-16 19:50:55
Maybe!!!!
Maybe!!!!
admathcamp353
2024-05-16 19:51:55
Does this have a connection to graph theory?
Does this have a connection to graph theory?
Luraibird49
2024-05-16 19:52:16
I think so! Some of the solutions we got definitely used some graph theory!
I think so! Some of the solutions we got definitely used some graph theory!
Kai321
2024-05-16 19:53:19
Isn't the absolute lower bound equal to n(sqrt2 + 1) - 1?
Isn't the absolute lower bound equal to n(sqrt2 + 1) - 1?
Luraibird49
2024-05-16 19:53:31
I think you're right, actually -- good catch!
I think you're right, actually -- good catch!
Luraibird49
2024-05-16 19:53:43
Alright, now I'm going to pass you all back to Dan to look at Problem 6!
Alright, now I'm going to pass you all back to Dan to look at Problem 6!
dgulotta
2024-05-16 19:54:10
Thanks Phoebe!
Thanks Phoebe!
dgulotta
2024-05-16 19:54:14
Problem 6: You may have heard of the Borromean rings (a famous pattern of 3 equal circles) or the Olympic rings (a famous pattern of 5 equal circles). The unchanging rings (which aren't famous because we just made up the name) are a pattern that can be made from different numbers of circles, with some special points on them marked.
Problem 6: You may have heard of the Borromean rings (a famous pattern of 3 equal circles) or the Olympic rings (a famous pattern of 5 equal circles). The unchanging rings (which aren't famous because we just made up the name) are a pattern that can be made from different numbers of circles, with some special points on them marked.
dgulotta
2024-05-16 19:54:24
A system of unchanging rings must satisfy three unchanging rules:
1. If two circles meet at a marked point, they share exactly two marked points.
2. If two marked points lie on a common circle, they must share exactly two common circles.
3. We can get from any circle to any other by some number of hops along marked points.
A system of unchanging rings must satisfy three unchanging rules:
1. If two circles meet at a marked point, they share exactly two marked points.
2. If two marked points lie on a common circle, they must share exactly two common circles.
3. We can get from any circle to any other by some number of hops along marked points.
dgulotta
2024-05-16 19:54:35
One possible system of unchanging rings is shown below:
One possible system of unchanging rings is shown below:
dgulotta
2024-05-16 19:54:37
dgulotta
2024-05-16 19:54:44
(a) Draw a system of unchanging rings with more than 4 circles, all equal in size.
(a) Draw a system of unchanging rings with more than 4 circles, all equal in size.
dgulotta
2024-05-16 19:54:55
For this construction, it's useful to think in terms of vectors. The symmetry in the previous diagram can be a bit misleading, so here is a less symmetric configuration of unchanging rings:
For this construction, it's useful to think in terms of vectors. The symmetry in the previous diagram can be a bit misleading, so here is a less symmetric configuration of unchanging rings:
dgulotta
2024-05-16 19:55:00
dgulotta
2024-05-16 19:55:12
Let's declare the center of the middle (orange) circle to be the origin $\mathbf{0}$, and suppose that all of the circles have radius $1$. Let the unit vectors $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$ correspond to the three marked points on this circle.
Let's declare the center of the middle (orange) circle to be the origin $\mathbf{0}$, and suppose that all of the circles have radius $1$. Let the unit vectors $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$ correspond to the three marked points on this circle.
dgulotta
2024-05-16 19:55:22
How can we express the center of the upper (teal) circle in terms of $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$?
How can we express the center of the upper (teal) circle in terms of $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$?
dgulotta
2024-05-16 19:55:26
Jack_w
2024-05-16 19:56:19
$v_1 + v_2$
$v_1 + v_2$
MathIsFun286
2024-05-16 19:56:19
$v_1+v_2$
$v_1+v_2$
joeym2011
2024-05-16 19:56:19
v1+v2
v1+v2
dgulotta
2024-05-16 19:56:27
The center of circle must have distance $1$ from both $\mathbf{v}_1$ and $\mathbf{v}_2$. There are exactly two points with this property: $\mathbf{0}$ (the center of the middle (orange) circle) and $\mathbf{v}_1 + \mathbf{v}_2$. So the latter must be the center of the upper (teal) circle.
The center of circle must have distance $1$ from both $\mathbf{v}_1$ and $\mathbf{v}_2$. There are exactly two points with this property: $\mathbf{0}$ (the center of the middle (orange) circle) and $\mathbf{v}_1 + \mathbf{v}_2$. So the latter must be the center of the upper (teal) circle.
dgulotta
2024-05-16 19:56:39
Similarly, the centers of the other two circles are $\mathbf{v}_1+\mathbf{v}_3$ and $\mathbf{v}_2 + \mathbf{v}_3$.
Similarly, the centers of the other two circles are $\mathbf{v}_1+\mathbf{v}_3$ and $\mathbf{v}_2 + \mathbf{v}_3$.
dgulotta
2024-05-16 19:56:43
What are the coordinates of the remaining marked point?
What are the coordinates of the remaining marked point?
dgulotta
2024-05-16 19:56:44
joeym2011
2024-05-16 19:57:39
$\textbf v_1+\textbf v_2+\textbf v_3$
$\textbf v_1+\textbf v_2+\textbf v_3$
MathIsFun286
2024-05-16 19:57:39
$v_1+v_2+v_3$
$v_1+v_2+v_3$
Jack_w
2024-05-16 19:57:39
$v_1 + v_2 + v_3$
$v_1 + v_2 + v_3$
RLKC8
2024-05-16 19:57:39
Add them all up?
Add them all up?
dgulotta
2024-05-16 19:57:45
The point needs to have distance $1$ from $\mathbf{v}_1 + \mathbf{v}_2$, $\mathbf{v}_1 + \mathbf{v}_3$, and $\mathbf{v}_2 + \mathbf{v}_3$. There is only one point with this property, and it is $\mathbf{v}_1+\mathbf{v}_2+\mathbf{v}_3$.
The point needs to have distance $1$ from $\mathbf{v}_1 + \mathbf{v}_2$, $\mathbf{v}_1 + \mathbf{v}_3$, and $\mathbf{v}_2 + \mathbf{v}_3$. There is only one point with this property, and it is $\mathbf{v}_1+\mathbf{v}_2+\mathbf{v}_3$.
dgulotta
2024-05-16 19:57:59
dgulotta
2024-05-16 19:58:03
Can we generalize this construction to create a system with more circles?
Can we generalize this construction to create a system with more circles?
EpicBird08
2024-05-16 19:58:39
yes
yes
NAAUBE
2024-05-16 19:58:39
yes! try 4 marked moints/vectors
yes! try 4 marked moints/vectors
joeym2011
2024-05-16 19:58:39
Use four vectors and use combinations.
Use four vectors and use combinations.
dgulotta
2024-05-16 19:58:45
We can add a fourth unit vector $\mathbf{v}_4$. We will place a circle centered at $\mathbf{0}$, marked points at $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4$, circles centered at $\mathbf{v}_1+\mathbf{v}_2$, $\mathbf{v}_1 + \mathbf{v}_3$, $\mathbf{v}_1 + \mathbf{v}_4$, etc. There will be a total of $\binom{4}{0} + \binom{4}{2} + \binom{4}{4} = 8$ circles and $\binom{4}{1} + \binom{4}{3}=8$ marked points. The configuration will look something like this:
We can add a fourth unit vector $\mathbf{v}_4$. We will place a circle centered at $\mathbf{0}$, marked points at $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4$, circles centered at $\mathbf{v}_1+\mathbf{v}_2$, $\mathbf{v}_1 + \mathbf{v}_3$, $\mathbf{v}_1 + \mathbf{v}_4$, etc. There will be a total of $\binom{4}{0} + \binom{4}{2} + \binom{4}{4} = 8$ circles and $\binom{4}{1} + \binom{4}{3}=8$ marked points. The configuration will look something like this:
dgulotta
2024-05-16 19:59:01
dgulotta
2024-05-16 19:59:17
We do need to be a bit careful here. Can we choose any unit vectors $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4$, or are there some choices that don't work?
We do need to be a bit careful here. Can we choose any unit vectors $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4$, or are there some choices that don't work?
joeym2011
2024-05-16 20:00:22
Make sure no circles or marked points overlap.
Make sure no circles or marked points overlap.
snow52
2024-05-16 20:00:22
there are some that dont work
there are some that dont work
Kai321
2024-05-16 20:00:22
vi = -vj
vi = -vj
Multpi12
2024-05-16 20:00:22
v1 and v2 on the same point?
v1 and v2 on the same point?
dgulotta
2024-05-16 20:00:27
We are assuming the 8 points and 8 circles constructed above are all different. If $\mathbf{v}_1 = \mathbf{v}_2$ or $\mathbf{v}_1 + \mathbf{v}_2 = \mathbf{0}$, for example, this assumption will not be correct. We should also make sure that, for example, the marked point $\mathbf{v}_1+\mathbf{v}_2+\mathbf{v}_3$ does not accidentally lie on the circle centered at $\mathbf{0}$.
We are assuming the 8 points and 8 circles constructed above are all different. If $\mathbf{v}_1 = \mathbf{v}_2$ or $\mathbf{v}_1 + \mathbf{v}_2 = \mathbf{0}$, for example, this assumption will not be correct. We should also make sure that, for example, the marked point $\mathbf{v}_1+\mathbf{v}_2+\mathbf{v}_3$ does not accidentally lie on the circle centered at $\mathbf{0}$.
dgulotta
2024-05-16 20:00:38
The things that could go wrong are:
(1) a sum or difference of two vectors could be zero.
(2) a sum or difference of three vectors could have length one.
(3) a sum or difference of four vectors could be zero.
The things that could go wrong are:
(1) a sum or difference of two vectors could be zero.
(2) a sum or difference of three vectors could have length one.
(3) a sum or difference of four vectors could be zero.
dgulotta
2024-05-16 20:00:50
It's possible to prove that (2) and (3) can only happen if (1) happens. So as long as no two of $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4$ are equal or sum to zero, we do get a configuration of unchanging rings with 8 circles and 8 marked points. In the interest of time, I'll skip checking the details. One could always just choose a specific $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4$ and verify that none of (1)-(3) occur.
It's possible to prove that (2) and (3) can only happen if (1) happens. So as long as no two of $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4$ are equal or sum to zero, we do get a configuration of unchanging rings with 8 circles and 8 marked points. In the interest of time, I'll skip checking the details. One could always just choose a specific $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4$ and verify that none of (1)-(3) occur.
dgulotta
2024-05-16 20:01:33
That concludes part (a).
That concludes part (a).
dgulotta
2024-05-16 20:01:36
Maybe you thought this problem was about geometry? Just kidding! You see, there is a special kind of circle called a math circle: it's not a geometric object, but a group of people doing math together. Let's say that a "marked point" in such a case is a person participating in one or more of the math circles. We can form a system of unchanging rings out of math circles as well, by satisfying the unchanging rules.
Maybe you thought this problem was about geometry? Just kidding! You see, there is a special kind of circle called a math circle: it's not a geometric object, but a group of people doing math together. Let's say that a "marked point" in such a case is a person participating in one or more of the math circles. We can form a system of unchanging rings out of math circles as well, by satisfying the unchanging rules.
dgulotta
2024-05-16 20:01:53
(b) Prove that every system of unchanging rings (whether made up of ordinary circles or math circles) has an unchanging constant $n$, such that every circle contains exactly $n$ marked points, and every marked point is contained in exactly $n$ circles. (In the example drawn above, $n=3$.)
(b) Prove that every system of unchanging rings (whether made up of ordinary circles or math circles) has an unchanging constant $n$, such that every circle contains exactly $n$ marked points, and every marked point is contained in exactly $n$ circles. (In the example drawn above, $n=3$.)
dgulotta
2024-05-16 20:02:16
For this part of the problem, it's convenient to use graph theory. Given a system of unchanging rings, we construct a graph called the "incidence graph". It is defined as follows. We draw a vertex for each math circle and each marked point. For each point-circle incidence, we draw an edge between the corresponding vertices. The resulting graph has the following properties:
For this part of the problem, it's convenient to use graph theory. Given a system of unchanging rings, we construct a graph called the "incidence graph". It is defined as follows. We draw a vertex for each math circle and each marked point. For each point-circle incidence, we draw an edge between the corresponding vertices. The resulting graph has the following properties:
dgulotta
2024-05-16 20:02:42
1. If two vertices have a common neighbor, they have exactly two common neighbors.
2. There is a path between any pair of vertices.
3. The graph is bipartite. (In other words, it can be colored with two colors so that no two vertices of the same color are adjacent.)
1. If two vertices have a common neighbor, they have exactly two common neighbors.
2. There is a path between any pair of vertices.
3. The graph is bipartite. (In other words, it can be colored with two colors so that no two vertices of the same color are adjacent.)
dgulotta
2024-05-16 20:03:30
What does the incidence graph for our original system of unchanging rings look like?
What does the incidence graph for our original system of unchanging rings look like?
dgulotta
2024-05-16 20:06:33
So, here was the graph again
So, here was the graph again
dgulotta
2024-05-16 20:06:38
dgulotta
2024-05-16 20:06:53
Each point and circle was associated with a sum of vectors
Each point and circle was associated with a sum of vectors
dgulotta
2024-05-16 20:07:17
Is there a nice way to arrange these 8 sums of vectors?
Is there a nice way to arrange these 8 sums of vectors?
joeym2011
2024-05-16 20:08:05
Connect those differing by one vector.
Connect those differing by one vector.
dgulotta
2024-05-16 20:08:44
Multpi12
2024-05-16 20:09:06
Cube?
Cube?
dgulotta
2024-05-16 20:09:31
The incidence graph looks like a cube. We can label the lower left vertex with $\mathbf{0}$, the three adjacent vertices with $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$, etc.
The incidence graph looks like a cube. We can label the lower left vertex with $\mathbf{0}$, the three adjacent vertices with $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$, etc.
dgulotta
2024-05-16 20:09:52
Although we didn't know it when we wrote the problem, it turns out that systems of unchanging rings have been studied before. They are known in the literature as "semibiplanes". Graphs satisfying properties 1-2 above are known as "$(0,2)$-graphs". So if you want to know more about these graphs, there are a few papers out there!
Although we didn't know it when we wrote the problem, it turns out that systems of unchanging rings have been studied before. They are known in the literature as "semibiplanes". Graphs satisfying properties 1-2 above are known as "$(0,2)$-graphs". So if you want to know more about these graphs, there are a few papers out there!
NAAUBE
2024-05-16 20:10:22
Does the one with 8 circles become a hypercube?
Does the one with 8 circles become a hypercube?
dgulotta
2024-05-16 20:10:24
Yes!
Yes!
dgulotta
2024-05-16 20:10:43
Part (b) is asking us to show that every vertex in the incidence graph has the same number of edges. Since the graph is connected, it's enough to show that any two adjacent vertices have the same number of edges. What technique might we want to use here?
Part (b) is asking us to show that every vertex in the incidence graph has the same number of edges. Since the graph is connected, it's enough to show that any two adjacent vertices have the same number of edges. What technique might we want to use here?
joeym2011
2024-05-16 20:13:22
Focus on a point on a circle and prove that every circle through the point corresponds to another point on the circle and vice versa.
Focus on a point on a circle and prove that every circle through the point corresponds to another point on the circle and vice versa.
dgulotta
2024-05-16 20:13:28
Constructing a bijection is one way to show that two sets have the same number of elements.
Constructing a bijection is one way to show that two sets have the same number of elements.
dgulotta
2024-05-16 20:13:42
Let $v$, $v'$ be two adjacent vertices. We will construct a bijection between edges connected to $v$ and edges connected to $v'$.
Let $v$, $v'$ be two adjacent vertices. We will construct a bijection between edges connected to $v$ and edges connected to $v'$.
dgulotta
2024-05-16 20:13:49
Let $e$ be an edge connected to $v$. If $v'$ is the other endpoint of $v$, we will send $e$ to $e$. Otherwise, let $w$ be the other endpoint of $e$. Since $v$ is adjacent to $v'$ and $w$, there must be exactly one other vertex $w'$ that is adjacent to these two vertices. We will send $e$ to the edge $e'$ connecting $v'$ and $w'$.
Let $e$ be an edge connected to $v$. If $v'$ is the other endpoint of $v$, we will send $e$ to $e$. Otherwise, let $w$ be the other endpoint of $e$. Since $v$ is adjacent to $v'$ and $w$, there must be exactly one other vertex $w'$ that is adjacent to these two vertices. We will send $e$ to the edge $e'$ connecting $v'$ and $w'$.
dgulotta
2024-05-16 20:13:52
dgulotta
2024-05-16 20:14:14
Note that if we apply this construction to $e'$, we get $e$ back, since $w$ is the vertex other than $v'$ that is adjacent to $v$ and $w'$. So we have constructed a bijection between edges connected to $v$ and edges connected to $v'$.
Note that if we apply this construction to $e'$, we get $e$ back, since $w$ is the vertex other than $v'$ that is adjacent to $v$ and $w'$. So we have constructed a bijection between edges connected to $v$ and edges connected to $v'$.
dgulotta
2024-05-16 20:14:30
Therefore, any two adjacent vertices must have the same number of edges. Since the graph is connected, any two vertices must have the same number of edges. So we have solved part (b).
Therefore, any two adjacent vertices must have the same number of edges. Since the graph is connected, any two vertices must have the same number of edges. So we have solved part (b).
EpicBird08
2024-05-16 20:15:07
wow that was quick!
wow that was quick!
dgulotta
2024-05-16 20:15:16
(c) In a system of unchanging rings with unchanging constant $n$, what is the maximum number of circles?
(c) In a system of unchanging rings with unchanging constant $n$, what is the maximum number of circles?
dgulotta
2024-05-16 20:15:32
To get an idea of what the answer should be, let's first try constructing a system of unchanging rings with unchanging constant $n$. Any ideas on how to do that?
To get an idea of what the answer should be, let's first try constructing a system of unchanging rings with unchanging constant $n$. Any ideas on how to do that?
NAAUBE
2024-05-16 20:16:27
Can we use combinatorics for this like we briefly did in a?
Can we use combinatorics for this like we briefly did in a?
joeym2011
2024-05-16 20:16:27
Start with the origin circle and the $n$ vector marked points.
Start with the origin circle and the $n$ vector marked points.
Jack_w
2024-05-16 20:16:27
back to the vectors approach, with $n$ unit vectors?
back to the vectors approach, with $n$ unit vectors?
NAAUBE
2024-05-16 20:16:27
Pick a number of vectors!
Pick a number of vectors!
dgulotta
2024-05-16 20:17:25
The construction from part (a) can be generalized. If we start with $n$ vectors $\{\mathbf{v}_1,\mathbf{v}_2,\dotsc,\mathbf{v}_n\}$, we can construct a system of unchanging rings with unchanging constant $n$ by placing circles centered at the sums of an odd number of vectors and marked points at sums of an even number of vectors. How many marked points and circles will we end up with?
The construction from part (a) can be generalized. If we start with $n$ vectors $\{\mathbf{v}_1,\mathbf{v}_2,\dotsc,\mathbf{v}_n\}$, we can construct a system of unchanging rings with unchanging constant $n$ by placing circles centered at the sums of an odd number of vectors and marked points at sums of an even number of vectors. How many marked points and circles will we end up with?
dgulotta
2024-05-16 20:18:15
(or rather, for consistency, let's place circles at the even sums and points at the odd sums, for consistency with our earlier answer.)
(or rather, for consistency, let's place circles at the even sums and points at the odd sums, for consistency with our earlier answer.)
MathIsFun286
2024-05-16 20:18:31
$2^{n-1}$
$2^{n-1}$
joeym2011
2024-05-16 20:18:31
$2^{n-1}$
$2^{n-1}$
EpicBird08
2024-05-16 20:18:31
which gives 2^n/2 = 2^(n-1)
which gives 2^n/2 = 2^(n-1)
Jack_w
2024-05-16 20:18:31
$2^{n-1}$ of each?
$2^{n-1}$ of each?
NAAUBE
2024-05-16 20:18:40
n choose 0 + n choose 2 +.... N choose n-2 + n choose n
n choose 0 + n choose 2 +.... N choose n-2 + n choose n
dgulotta
2024-05-16 20:18:42
There are $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \dotsb$ circles. The binomial theorem tells us that $2^n = (1+1)^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dotsb$, while $0 = (1-1)^n = \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \dotsb$. So $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \dotsb = (2^n+0)/2 = 2^{n-1}$. Similarly, there are $\binom{n}{1} + \binom{n}{3} + \binom{n}{5} + \dotsb = 2^{n-1}$ marked points.
There are $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \dotsb$ circles. The binomial theorem tells us that $2^n = (1+1)^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dotsb$, while $0 = (1-1)^n = \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \dotsb$. So $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \dotsb = (2^n+0)/2 = 2^{n-1}$. Similarly, there are $\binom{n}{1} + \binom{n}{3} + \binom{n}{5} + \dotsb = 2^{n-1}$ marked points.
dgulotta
2024-05-16 20:19:09
We might guess that $2^{n-1}$ is the maximum number of circles, and this guess turns out to be correct. Before we move on to proving that it is the maximum, can you describe the incidence graph for the set of unchanging rings described above?
We might guess that $2^{n-1}$ is the maximum number of circles, and this guess turns out to be correct. Before we move on to proving that it is the maximum, can you describe the incidence graph for the set of unchanging rings described above?
joeym2011
2024-05-16 20:20:05
$n$-dimensional cube
$n$-dimensional cube
MathIsFun286
2024-05-16 20:20:05
n-dimensional hypercube
n-dimensional hypercube
NAAUBE
2024-05-16 20:20:05
n dimensional cube?
n dimensional cube?
Jack_w
2024-05-16 20:20:05
$n$-dimensional polytope that resembles a cube
$n$-dimensional polytope that resembles a cube
dgulotta
2024-05-16 20:20:11
Right, it's an $n$-dimensional hypercube. We can think of the vertices as the set of the points in $\mathbb{R}^n$ whose coordinates are all $0$ or $1$. Two vertices are connected by an edge if they differ in only one coordinate.
Right, it's an $n$-dimensional hypercube. We can think of the vertices as the set of the points in $\mathbb{R}^n$ whose coordinates are all $0$ or $1$. Two vertices are connected by an edge if they differ in only one coordinate.
dgulotta
2024-05-16 20:20:24
Now we'll prove that there cannot be more than $2^{n-1}$ math circles. We will choose an arbitrary "starting vertex" $s$ in the incidence graph, and consider the distance from $s$ to each other vertex. If a vertex $v$ has distance $m$ from $s$, then the triangle inequality implies that the neighbors of $v$ have distance between $m-1$ and $m+1$ from $s$.
Now we'll prove that there cannot be more than $2^{n-1}$ math circles. We will choose an arbitrary "starting vertex" $s$ in the incidence graph, and consider the distance from $s$ to each other vertex. If a vertex $v$ has distance $m$ from $s$, then the triangle inequality implies that the neighbors of $v$ have distance between $m-1$ and $m+1$ from $s$.
dgulotta
2024-05-16 20:20:31
Since the graph is bipartite, the neighbors can't have distance exactly $m$ from $s$. So their distance must be $m-1$ or $m+1$.
Since the graph is bipartite, the neighbors can't have distance exactly $m$ from $s$. So their distance must be $m-1$ or $m+1$.
dgulotta
2024-05-16 20:20:38
In the $n$-dimensional hypercube graph, how many of $v$'s neighbors have distance $m-1$ from $s$, and how many have distance $m+1$ from $s$?
In the $n$-dimensional hypercube graph, how many of $v$'s neighbors have distance $m-1$ from $s$, and how many have distance $m+1$ from $s$?
dgulotta
2024-05-16 20:22:06
It might help to think about the cube example first.
It might help to think about the cube example first.
dgulotta
2024-05-16 20:22:16
MathIsFun286
2024-05-16 20:23:21
m have distance m-1 from s, and n-m have distance m from s
m have distance m-1 from s, and n-m have distance m from s
joeym2011
2024-05-16 20:23:21
$m$ are distance $m-1$ away and $n-m$ are distance $m+1$ away?
$m$ are distance $m-1$ away and $n-m$ are distance $m+1$ away?
dgulotta
2024-05-16 20:24:38
In the cube example, we can think of the lower left corner as the starting point. Vertices that are distance one away from the starting point have one edge going back to the starting point and two edges going to vertices of distance 2.
In the cube example, we can think of the lower left corner as the starting point. Vertices that are distance one away from the starting point have one edge going back to the starting point and two edges going to vertices of distance 2.
dgulotta
2024-05-16 20:25:01
Vertices of distance 2 have two edges going back to a vertex of distance 1 and one vertex going toward the vertex of distance 3.
Vertices of distance 2 have two edges going back to a vertex of distance 1 and one vertex going toward the vertex of distance 3.
dgulotta
2024-05-16 20:25:52
For a general n-dimensional hypercube, if a point is distance $m$ from the starting point, it has $m$ neighbors with distance $m-1$, and $n-m$ neighbors with distance $m+1$. This suggests the following lemma.
For a general n-dimensional hypercube, if a point is distance $m$ from the starting point, it has $m$ neighbors with distance $m-1$, and $n-m$ neighbors with distance $m+1$. This suggests the following lemma.
dgulotta
2024-05-16 20:26:11
Lemma: Let $G$ be $(0,2)$-graph, and let $s,v$ be vertices of $g$. Let $m$ be the distance from $s$ to $v$. Then at least $m$ neighbors of $v$ have distance $m-1$ from $s$.
Lemma: Let $G$ be $(0,2)$-graph, and let $s,v$ be vertices of $g$. Let $m$ be the distance from $s$ to $v$. Then at least $m$ neighbors of $v$ have distance $m-1$ from $s$.
dgulotta
2024-05-16 20:26:24
Proof: We will use induction on $m$. The base case $m=0$ is trivial. Now let $v$ be a point of distance $m>0$ from $s$. Then $v$ has a neighbor $v'$ that has distance $m-1$ from $s$. By the induction hypothesis, $v'$ has $m-1$ neighbors $w_1,\dotsc,w_{m-1}$ that have distance $m-2$ from $s$. For each $i$, $w_i$ and $v$ share a neighbor $v'$, so they must share a second neighbor $w_i'$. Each $w_i'$ must have distance exactly $m-1$ from $s$, since $w_i$ has distance $m-2$ and $v$ has distance $m$.
Proof: We will use induction on $m$. The base case $m=0$ is trivial. Now let $v$ be a point of distance $m>0$ from $s$. Then $v$ has a neighbor $v'$ that has distance $m-1$ from $s$. By the induction hypothesis, $v'$ has $m-1$ neighbors $w_1,\dotsc,w_{m-1}$ that have distance $m-2$ from $s$. For each $i$, $w_i$ and $v$ share a neighbor $v'$, so they must share a second neighbor $w_i'$. Each $w_i'$ must have distance exactly $m-1$ from $s$, since $w_i$ has distance $m-2$ and $v$ has distance $m$.
dgulotta
2024-05-16 20:26:28
dgulotta
2024-05-16 20:27:01
Are the points $w_1',\dotsc,w_{m-1}'$ necessarily distinct?
Are the points $w_1',\dotsc,w_{m-1}'$ necessarily distinct?
dgulotta
2024-05-16 20:29:07
If $w_1'$ was equal to $w_2'$, which points would be neighbors of both $v'$ and$w_1'$?
If $w_1'$ was equal to $w_2'$, which points would be neighbors of both $v'$ and$w_1'$?
Multpi12
2024-05-16 20:30:09
v and w1/w2
v and w1/w2
NAAUBE
2024-05-16 20:30:09
$w_1$ and $w_2$
$w_1$ and $w_2$
NAAUBE
2024-05-16 20:30:09
and v
and v
snow52
2024-05-16 20:30:09
$w_2, w_1$ and $v$
$w_2, w_1$ and $v$
dgulotta
2024-05-16 20:30:16
Is that allowed?
Is that allowed?
joeym2011
2024-05-16 20:30:38
no
no
NAAUBE
2024-05-16 20:30:38
no
no
Multpi12
2024-05-16 20:30:38
no
no
dgulotta
2024-05-16 20:31:21
Right, the unchanging rules say that two vertices must share zero or two neighbors, not three.
Right, the unchanging rules say that two vertices must share zero or two neighbors, not three.
dgulotta
2024-05-16 20:32:08
In general: If $w_i'$ was equal to $w_j'$, then $v$, $w_i$ and $w_j$ would all be adjacent to both $v'$ and $w_i'=w_j'$, in contradiction of the unchanging rules. Therefore, $\{v', w_1',\dotsc,w_{m-1}'\}$ is a set of $m$ distinct neighbors of $v$ that have distance $m-1$ from $s$. This completes the proof of the lemma.
In general: If $w_i'$ was equal to $w_j'$, then $v$, $w_i$ and $w_j$ would all be adjacent to both $v'$ and $w_i'=w_j'$, in contradiction of the unchanging rules. Therefore, $\{v', w_1',\dotsc,w_{m-1}'\}$ is a set of $m$ distinct neighbors of $v$ that have distance $m-1$ from $s$. This completes the proof of the lemma.
dgulotta
2024-05-16 20:32:30
In the $n$-dimensional hypercube graph, how many vertices have distance $m$ from the starting point?
In the $n$-dimensional hypercube graph, how many vertices have distance $m$ from the starting point?
joeym2011
2024-05-16 20:33:58
$\binom nm$
$\binom nm$
MathIsFun286
2024-05-16 20:33:58
$\binom{n}{m}$
$\binom{n}{m}$
RLKC8
2024-05-16 20:33:58
n choose m?
n choose m?
dgulotta
2024-05-16 20:34:00
Right, if we think of the points of the hypercube as having coordinates 0 or 1, and the point with all zeros as the starting point, then the points with $n$ ones have distance $m$. There are $\binom{n}{m}$ of those.
Right, if we think of the points of the hypercube as having coordinates 0 or 1, and the point with all zeros as the starting point, then the points with $n$ ones have distance $m$. There are $\binom{n}{m}$ of those.
dgulotta
2024-05-16 20:34:34
This also suggests a lemma.
This also suggests a lemma.
dgulotta
2024-05-16 20:34:37
Lemma: Let $G$ be a $(0,2)$-graph, and let $s$ be a vertex of $G$. Suppose that each vertex of $G$ has $n$ neighbors. For each $m$, there are at most $\binom{n}{m}$ vertices of distance $m$ from $s$.
Lemma: Let $G$ be a $(0,2)$-graph, and let $s$ be a vertex of $G$. Suppose that each vertex of $G$ has $n$ neighbors. For each $m$, there are at most $\binom{n}{m}$ vertices of distance $m$ from $s$.
dgulotta
2024-05-16 20:34:52
Proof: Again, we use induction on $m$, and the base case $m=0$ is trivial. Now assume that $m>0$, and that there are at most $\binom{n}{m-1}$ vertices of distance $m-1$. Each vertex of distance $m$ has at least $m$ neighbors of distance $m-1$, while each vertex of distance $m-1$ has at most $n-(m-1)=n-m+1$ neighbors of distance $m$. Therefore, the number of vertices of distance $m$ is at most $\binom{n}{m-1} \frac{m}{n-m+1} = \binom{n}{m}$. This completes the induction.
Proof: Again, we use induction on $m$, and the base case $m=0$ is trivial. Now assume that $m>0$, and that there are at most $\binom{n}{m-1}$ vertices of distance $m-1$. Each vertex of distance $m$ has at least $m$ neighbors of distance $m-1$, while each vertex of distance $m-1$ has at most $n-(m-1)=n-m+1$ neighbors of distance $m$. Therefore, the number of vertices of distance $m$ is at most $\binom{n}{m-1} \frac{m}{n-m+1} = \binom{n}{m}$. This completes the induction.
dgulotta
2024-05-16 20:35:37
Finally, if we choose the starting vertex $s$ to correspond to a math circle, then we see that the total number of math circles is at most $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \dotsb = 2^{n-1}$.
Finally, if we choose the starting vertex $s$ to correspond to a math circle, then we see that the total number of math circles is at most $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \dotsb = 2^{n-1}$.
dgulotta
2024-05-16 20:36:58
So we have shown both that it's possible to have $2^{n-1}$ math circles, and that we can't have more than $2^{n-1}$ math circles. So $2^{n-1}$ is the maximum.
So we have shown both that it's possible to have $2^{n-1}$ math circles, and that we can't have more than $2^{n-1}$ math circles. So $2^{n-1}$ is the maximum.
NAAUBE
2024-05-16 20:37:21
Can we have less?
Can we have less?
dgulotta
2024-05-16 20:37:29
Yes, we're just about to get to that!
Yes, we're just about to get to that!
dgulotta
2024-05-16 20:37:36
(d) For some $n$, find a nonempty system of unchanging rings with unchanging constant $n$ such that it has fewer circles than the maximum you found in part (c).
(d) For some $n$, find a nonempty system of unchanging rings with unchanging constant $n$ such that it has fewer circles than the maximum you found in part (c).
dgulotta
2024-05-16 20:38:03
We know of a few different examples. Here is one that involves actual circles, but in three dimensions. We take the "marked points" to be the vertices of an icosahedron. For each vertex of the icosahedron, we draw a circle through its five neighbors.
We know of a few different examples. Here is one that involves actual circles, but in three dimensions. We take the "marked points" to be the vertices of an icosahedron. For each vertex of the icosahedron, we draw a circle through its five neighbors.
dgulotta
2024-05-16 20:38:14
dgulotta
2024-05-16 20:38:32
Two marked points share a circle if and only if they are both adjacent to that circle's center. Similarly, two circles share a marked point if and only if both centers are adjacent to the marked point.
Two marked points share a circle if and only if they are both adjacent to that circle's center. Similarly, two circles share a marked point if and only if both centers are adjacent to the marked point.
dgulotta
2024-05-16 20:38:43
We can check that if two points on an icosahedron have a common neighbor, then they have exactly two common neighbors. There are essentially two different cases, shown below.
We can check that if two points on an icosahedron have a common neighbor, then they have exactly two common neighbors. There are essentially two different cases, shown below.
dgulotta
2024-05-16 20:38:47
dgulotta
2024-05-16 20:39:25
So this is in fact a configuration of unchanging rings. It has unchanging constant $5$. An icosahedron has $12$ vertices, so there are $12$ math circles, and $12$ marked points.
So this is in fact a configuration of unchanging rings. It has unchanging constant $5$. An icosahedron has $12$ vertices, so there are $12$ math circles, and $12$ marked points.
dgulotta
2024-05-16 20:39:44
If you're interested in seeing more solutions to part (d), I'll post a some at https://artofproblemsolving.com/community/c135h3301991_mathcamp_2024_qq_discussion_is_open in a few minutes.
If you're interested in seeing more solutions to part (d), I'll post a some at https://artofproblemsolving.com/community/c135h3301991_mathcamp_2024_qq_discussion_is_open in a few minutes.
dgulotta
2024-05-16 20:40:00
And you can probably find even more by searching for "(0,2) graphs".
And you can probably find even more by searching for "(0,2) graphs".
dgulotta
2024-05-16 20:40:24
If you have any last questions, I can answer them now.
If you have any last questions, I can answer them now.
Jack_w
2024-05-16 20:41:55
how many applicants managed to fully solve problem 6?
how many applicants managed to fully solve problem 6?
NAAUBE
2024-05-16 20:41:55
Did many people solve this one?
Did many people solve this one?
dgulotta
2024-05-16 20:41:57
I don't remember exactly - most applicants didn't solve it fully but at least a few did.
I don't remember exactly - most applicants didn't solve it fully but at least a few did.
NAAUBE
2024-05-16 20:44:15
did anyone who solved it find the papers of 0,2 graphs or cite them? or did you learn about them separately?
did anyone who solved it find the papers of 0,2 graphs or cite them? or did you learn about them separately?
dgulotta
2024-05-16 20:44:17
We learned about the papers when an applicant mentioned them to us.
We learned about the papers when an applicant mentioned them to us.
dgulotta
2024-05-16 20:44:25
I think a few applicants found them.
I think a few applicants found them.
dgulotta
2024-05-16 20:45:13
That's the end of the quiz. Thank you so much for spending your evening with us!
That's the end of the quiz. Thank you so much for spending your evening with us!
dgulotta
2024-05-16 20:45:29
We'll be posting tonight's transcript at https://www.mathcamp.org/qualifying_quiz/solutions/ within the next few days, in case you want to revisit some of what we covered tonight.
We'll be posting tonight's transcript at https://www.mathcamp.org/qualifying_quiz/solutions/ within the next few days, in case you want to revisit some of what we covered tonight.
dgulotta
2024-05-16 20:45:33
We hope you enjoyed this year's QQ, and stay tuned for the 2025 Quiz (and the summer 2025 application) to be posted in January.
We hope you enjoyed this year's QQ, and stay tuned for the 2025 Quiz (and the summer 2025 application) to be posted in January.
shsiliveri
2024-05-16 20:46:21
thank you
thank you
joeym2011
2024-05-16 20:46:21
Thanks, I will test it myself!
Thanks, I will test it myself!
snow52
2024-05-16 20:46:21
Thank you!
Thank you!
blackillerpanther229
2024-05-16 20:46:21
byee! thank you!!
byee! thank you!!
jwelsh
2024-05-16 20:46:24
Thank you all for coming! Over 400 students joined us today.
Thank you all for coming! Over 400 students joined us today.
jwelsh
2024-05-16 20:46:34
Thank you, Dan and Phoebe, for leading us through problems 4-6!
Thank you, Dan and Phoebe, for leading us through problems 4-6!
jwelsh
2024-05-16 20:46:50
If you have questions for Mathcamp, you can contact them at www.mathcamp.org/contact.php
If you have questions for Mathcamp, you can contact them at www.mathcamp.org/contact.php
jwelsh
2024-05-16 20:47:05
Finally, a transcript of this Math Jam will be posted soon here: www.aops.com/school/mathjams-transcripts
Finally, a transcript of this Math Jam will be posted soon here: www.aops.com/school/mathjams-transcripts
Copyright © 2025 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.
