Mathcamp 2023 Qualifying Quiz Math Jam
Go back to the Math Jam ArchiveThis Math Jam will discuss solutions to the 2023 Mathcamp Qualifying Quiz. Mathcamp is an intensive 5-week-long summer program for mathematically talented high school student. 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 © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
Facilitator: AoPS Staff
devenware
2023-05-23 19:00:22
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!
winstonDeGreef
2023-05-23 19:00:37
hi
hi
achyutksingh
2023-05-23 19:00:37
hihi
hihi
MathWinner121
2023-05-23 19:00:37
Glad to be here
Glad to be here
BabaLama
2023-05-23 19:00:37
hi
hi
devenware
2023-05-23 19:00:39
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.
devenware
2023-05-23 19:00:44
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.
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.
devenware
2023-05-23 19:01:01
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
devenware
2023-05-23 19:01:06
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
Many AoPS instructors, assistants, and students are alumni of this outstanding program!
devenware
2023-05-23 19:01:14
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 2023 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 2023 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:
devenware
2023-05-23 19:01:54
Tim Black (timblack) has taught Mathcamp classes on topics ranging from complexity theory to board games, plus a lot of ways to avoid doing calculus. He's been at camp as either a camper or staff most summers since 2005. He also spent many years teaching math and computer science at the University of Chicago.
Tim Black (timblack) has taught Mathcamp classes on topics ranging from complexity theory to board games, plus a lot of ways to avoid doing calculus. He's been at camp as either a camper or staff most summers since 2005. He also spent many years teaching math and computer science at the University of Chicago.
devenware
2023-05-23 19:02:06
Dan Gulotta (dgulotta) has been a camper, mentor, and visiting speaker at Mathcamp, most recently in 2021. He is currently a postdoc at Boston University, studying number theory.
Dan Gulotta (dgulotta) has been a camper, mentor, and visiting speaker at Mathcamp, most recently in 2021. He is currently a postdoc at Boston University, studying number theory.
Yunny
2023-05-23 19:02:24
ily
2023-05-23 19:02:24
It's starting!!!
It's starting!!!
MathWinner121
2023-05-23 19:02:35
Hello!!!!!
Hello!!!!!
EpicBird08
2023-05-23 19:02:35
yay!
yay!
devenware
2023-05-23 19:02:40
Let's turn the room over to Tim and Dan now to get us started!
Let's turn the room over to Tim and Dan now to get us started!
timblack
2023-05-23 19:02:58
Hello everyone!
Hello everyone!
dgulotta
2023-05-23 19:03:08
Hi everyone!
Hi everyone!
timblack
2023-05-23 19:03:08
A big thanks as always to @devenware and the AoPS team for hosting us, and to all of you for being here!
A big thanks as always to @devenware and the AoPS team for hosting us, and to all of you for being here!
MathWinner121
2023-05-23 19:03:19
Hello, Tim and Dan!
Hello, Tim and Dan!
WangJY01
2023-05-23 19:03:19
Hi!
Hi!
akmathisfun2020
2023-05-23 19:03:19
hello!
hello!
bobjoebilly
2023-05-23 19:03:19
hi
hi
Curious_Droid
2023-05-23 19:03:19
hi
hi
alex4010
2023-05-23 19:03:19
Hi
Hi
timblack
2023-05-23 19:03:28
Tonight, we'll be working through solutions to the Mathcamp 2023 Qualifying Quiz. This Math Jam is likely to be interesting mostly to students who applied to Mathcamp and worked through the Qualifying Quiz on their own, but if you didn't, you're of course still welcome to stick around and see some interesting problems!
Tonight, we'll be working through solutions to the Mathcamp 2023 Qualifying Quiz. This Math Jam is likely to be interesting mostly to students who applied to Mathcamp and worked through the Qualifying Quiz on their own, but if you didn't, you're of course still welcome to stick around and see some interesting problems!
timblack
2023-05-23 19:03:38
To follow along, you may want to have the Qualifying Quiz open in another window: https://www.mathcamp.org/qualifying_quiz/current_quiz/
To follow along, you may want to have the Qualifying Quiz open in another window: https://www.mathcamp.org/qualifying_quiz/current_quiz/
timblack
2023-05-23 19:03:46
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, or the application process, you'll find lots of info on our website (e.g., at https://www.mathcamp.org/about_mathcamp/).
Today, we'll just be talking about the Quiz. If you have questions about Mathcamp itself, or the application process, you'll find lots of info on our website (e.g., at https://www.mathcamp.org/about_mathcamp/).
timblack
2023-05-23 19:04:05
The Quiz problems are written by Mathcamp alumni, staff, and friends each year, and the solutions we'll be walking through today are a collaboration by lots of Mathcamp staff (with good ideas from the applicants, too!).
The Quiz problems are written by Mathcamp alumni, staff, and friends each year, and the solutions we'll be walking through today are a collaboration by lots of Mathcamp staff (with good ideas from the applicants, too!).
timblack
2023-05-23 19:04:20
If you applied this year, I strongly recommend having your own solutions open. That way, you can reply more quickly to the questions we ask of the room. And we're expecting you all to pitch in to the solutions!
If you applied this year, I strongly recommend having your own solutions open. That way, you can reply more quickly to the questions we ask of the room. And we're expecting you all to pitch in to the solutions!
timblack
2023-05-23 19:04:34
We'll be posting the transcript from tonight on https://www.mathcamp.org/qualifying_quiz/solutions/ within the next few days, so no need to worry if you have to miss part of the event.
We'll be posting the transcript from tonight on https://www.mathcamp.org/qualifying_quiz/solutions/ within the next few days, so no need to worry if you have to miss part of the event.
timblack
2023-05-23 19:04:56
Students can use LaTeX in this classroom, just like on the message boards. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We claim that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We claim that $\frac{1}{2} + \frac{1}{3} = \frac{5}{6}$.
Students can use LaTeX in this classroom, just like on the message boards. Specifically, place your math LaTeX code inside dollar signs. For example, type:
We claim that \$\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\$.
This should give you:
We claim that $\frac{1}{2} + \frac{1}{3} = \frac{5}{6}$.
timblack
2023-05-23 19:05:08
As @devenware pointed out: this chat room is moderated. That means your messages go only to us, and we will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time (and we'll do our best to answer).
We've got a lot to cover, so let's get started! I'll dive right into Problem #1 to kick us off.
As @devenware pointed out: this chat room is moderated. That means your messages go only to us, and we will choose which to pass on, so please don't be shy to contribute and/or ask questions about the problems at any time (and we'll do our best to answer).
We've got a lot to cover, so let's get started! I'll dive right into Problem #1 to kick us off.
timchen
2023-05-23 19:05:25
$\frac{1}{2}+\frac{1}{3}\neq\frac{5}{6}.$
$\frac{1}{2}+\frac{1}{3}\neq\frac{5}{6}.$
timblack
2023-05-23 19:05:28
timblack
2023-05-23 19:05:43
1. You have a funny calculator with only two buttons: $+1$ and $\times 2$. The first button adds $1$ to the current number, the second multiplies it by $2$. For each nonnegative integer $n$, what is the shortest sequence of buttons that will get you from $0$ to $n$? (As with all problems on the Qualifying Quiz, make sure to justify your answer with a proof.)
1. You have a funny calculator with only two buttons: $+1$ and $\times 2$. The first button adds $1$ to the current number, the second multiplies it by $2$. For each nonnegative integer $n$, what is the shortest sequence of buttons that will get you from $0$ to $n$? (As with all problems on the Qualifying Quiz, make sure to justify your answer with a proof.)
timblack
2023-05-23 19:05:57
For this first problem especially, instead of just typing out the solution, I want to go through the problem solving process with you.
For this first problem especially, instead of just typing out the solution, I want to go through the problem solving process with you.
timblack
2023-05-23 19:06:06
To save some typing, I'm going to write + to represent the $+1$ button and * for the $\times 2$ button. I'll write Z to mean "start with zero."
What number do we end up with if we press Z+*++*+ ?
To save some typing, I'm going to write + to represent the $+1$ button and * for the $\times 2$ button. I'll write Z to mean "start with zero."
What number do we end up with if we press Z+*++*+ ?
TheBeast5520
2023-05-23 19:06:39
9
9
vrondoS
2023-05-23 19:06:39
9
9
Technodoggo
2023-05-23 19:06:39
$9$
$9$
angie.
2023-05-23 19:06:39
9
9
impromptuA
2023-05-23 19:06:39
9
9
HappyBunny
2023-05-23 19:06:39
9
9
timblack
2023-05-23 19:06:42
That's right:
$0 + 1 = 1$,
$1 \times 2 = 2$,
$2 + 1 = 3$,
$3 + 1 = 4$,
$4 \times 2 = 8$,
$8 + 1 = 9$.
So Z+*+++*+ $\rightarrow 9$.
That's right:
$0 + 1 = 1$,
$1 \times 2 = 2$,
$2 + 1 = 3$,
$3 + 1 = 4$,
$4 \times 2 = 8$,
$8 + 1 = 9$.
So Z+*+++*+ $\rightarrow 9$.
timblack
2023-05-23 19:06:59
There it took seven button presses to get to 9 (the Z doesn't count). Is this the shortest sequence to get from zero to 9?
There it took seven button presses to get to 9 (the Z doesn't count). Is this the shortest sequence to get from zero to 9?
ThousandthStar
2023-05-23 19:07:21
No
No
winstonDeGreef
2023-05-23 19:07:21
no
no
spm269
2023-05-23 19:07:21
no
no
wilsonstmartin
2023-05-23 19:07:21
no
no
timblack
2023-05-23 19:07:29
What's a shorter sequence?
What's a shorter sequence?
rithek.shankar
2023-05-23 19:07:54
There is Z+***+
There is Z+***+
JigglypuffDaBest
2023-05-23 19:07:54
Z+***+
Z+***+
pierrecai
2023-05-23 19:07:54
Z+***+=9
Z+***+=9
BrianSun
2023-05-23 19:07:54
Z+***+
Z+***+
timblack
2023-05-23 19:08:02
Nice. Z+***+ $\rightarrow 9$, and that's only five presses.
Nice. Z+***+ $\rightarrow 9$, and that's only five presses.
timblack
2023-05-23 19:08:10
In this case, to get from $0$ to $9$, we started by pressing the + to get $1$, then we pressed * as many times as we could without going over 9 (in this case, three times), then we pressed + until we got to $9$ (in this case, just once).
In this case, to get from $0$ to $9$, we started by pressing the + to get $1$, then we pressed * as many times as we could without going over 9 (in this case, three times), then we pressed + until we got to $9$ (in this case, just once).
timblack
2023-05-23 19:08:56
This seems like a promising method to me: after we get to $1$, it feels good to press * as many times as we can, because that lets us quickly jump to bigger and bigger numbers. For example, Z+++++++ is only $7$, while Z+****** is already $64$. But is this really the best method? Again, the method is: press + once, then press * as many times as possible, and then press + until you reach $n$.
This seems like a promising method to me: after we get to $1$, it feels good to press * as many times as we can, because that lets us quickly jump to bigger and bigger numbers. For example, Z+++++++ is only $7$, while Z+****** is already $64$. But is this really the best method? Again, the method is: press + once, then press * as many times as possible, and then press + until you reach $n$.
timblack
2023-05-23 19:09:27
A method like this is sometimes called a greedy strategy, because you are doing the thing that looks best in the moment, without checking to see if it's really what's best in the long run. Sometimes it really is the best, but often times it isn't.
A method like this is sometimes called a greedy strategy, because you are doing the thing that looks best in the moment, without checking to see if it's really what's best in the long run. Sometimes it really is the best, but often times it isn't.
MisakaMikasa
2023-05-23 19:09:41
no, it is bad if n is not close to a power of 2
no, it is bad if n is not close to a power of 2
bobjoebilly
2023-05-23 19:09:41
no, because if we have something like $2^n - 1$ it will be very inefficient
no, because if we have something like $2^n - 1$ it will be very inefficient
timblack
2023-05-23 19:09:49
No, this is not the best method; it does not result in the fewest number of button presses. What's an $n$ where this doesn't give the shortest sequence?
No, this is not the best method; it does not result in the fewest number of button presses. What's an $n$ where this doesn't give the shortest sequence?
NL008
2023-05-23 19:10:23
127
127
winstonDeGreef
2023-05-23 19:10:23
63
63
AP0LL0-11
2023-05-23 19:10:23
12
12
Mahikohli
2023-05-23 19:10:23
15
15
timblack
2023-05-23 19:10:29
These are all good examples
These are all good examples
timblack
2023-05-23 19:11:04
If we followed this method for $n = 15$, we would press + to get $1$, then we would press * three times to get $8$, then we couldn't press * anymore, so we would have to press + seven times to finish off: Z+***+++++++ $\rightarrow 15$. What's a shorter sequences of presses to get to $n = 15$?
If we followed this method for $n = 15$, we would press + to get $1$, then we would press * three times to get $8$, then we couldn't press * anymore, so we would have to press + seven times to finish off: Z+***+++++++ $\rightarrow 15$. What's a shorter sequences of presses to get to $n = 15$?
NoahLeaf
2023-05-23 19:11:54
Z+*+*+*+
Z+*+*+*+
LongJumpMain
2023-05-23 19:11:54
Z+++*+*+
Z+++*+*+
akmathisfun2020
2023-05-23 19:11:54
Z+*+*+*+
Z+*+*+*+
Chameleon07
2023-05-23 19:11:54
Z+*+*+*+
Z+*+*+*+
timblack
2023-05-23 19:11:55
Yep, Z+*+*+*+ $\rightarrow 15$, and that's only seven button presses instead of eleven.
Yep, Z+*+*+*+ $\rightarrow 15$, and that's only seven button presses instead of eleven.
timblack
2023-05-23 19:12:24
I want to point this out especially because a "greedy" strategy like this is tempting, but doesn't always work.
I want to point this out especially because a "greedy" strategy like this is tempting, but doesn't always work.
timblack
2023-05-23 19:12:35
Sometimes it works, but when it does, you need to PROVE it to be sure
Sometimes it works, but when it does, you need to PROVE it to be sure
timblack
2023-05-23 19:12:41
For now, we need to go back to the drawing board.
For now, we need to go back to the drawing board.
timblack
2023-05-23 19:13:13
I see some good suggestions in the chat already
I see some good suggestions in the chat already
timblack
2023-05-23 19:13:32
If you don't have ideas yet, for problems like this, it's a good idea to try some small values of $n$, and then look for a pattern. If you are solving this on your own, you might try all $n$ up to (say) $20$, and work out the shortest sequence for each.
If you don't have ideas yet, for problems like this, it's a good idea to try some small values of $n$, and then look for a pattern. If you are solving this on your own, you might try all $n$ up to (say) $20$, and work out the shortest sequence for each.
timblack
2023-05-23 19:13:43
Here are shortest sequences for $n$ between $0$ and $20$:
Here are shortest sequences for $n$ between $0$ and $20$:
timblack
2023-05-23 19:13:51
Z $\rightarrow 0$.
Z+ $\rightarrow 1$.
Z+* $\rightarrow 2$.
Z+*+ $\rightarrow 3$.
Z+** $\rightarrow 4$.
Z+**+ $\rightarrow 5$.
Z+*+* $\rightarrow 6$.
Z+*+*+ $\rightarrow 7$.
Z+*** $\rightarrow 8$.
Z+***+ $\rightarrow 9$.
Z+**+* $\rightarrow 10$.
Z+**+*+ $\rightarrow 11$.
Z+*+** $\rightarrow 12$.
Z+*+**+ $\rightarrow 13$.
Z+*+*+* $\rightarrow 14$.
Z+*+*+*+ $\rightarrow 15$.
Z+**** $\rightarrow 16$.
Z+****+ $\rightarrow 17$.
Z+***+* $\rightarrow 18$.
Z+***+*+ $\rightarrow 19$.
Z+**+** $\rightarrow 20$.
Z $\rightarrow 0$.
Z+ $\rightarrow 1$.
Z+* $\rightarrow 2$.
Z+*+ $\rightarrow 3$.
Z+** $\rightarrow 4$.
Z+**+ $\rightarrow 5$.
Z+*+* $\rightarrow 6$.
Z+*+*+ $\rightarrow 7$.
Z+*** $\rightarrow 8$.
Z+***+ $\rightarrow 9$.
Z+**+* $\rightarrow 10$.
Z+**+*+ $\rightarrow 11$.
Z+*+** $\rightarrow 12$.
Z+*+**+ $\rightarrow 13$.
Z+*+*+* $\rightarrow 14$.
Z+*+*+*+ $\rightarrow 15$.
Z+**** $\rightarrow 16$.
Z+****+ $\rightarrow 17$.
Z+***+* $\rightarrow 18$.
Z+***+*+ $\rightarrow 19$.
Z+**+** $\rightarrow 20$.
timblack
2023-05-23 19:14:02
Do you notice any patterns?
Do you notice any patterns?
winstonDeGreef
2023-05-23 19:14:35
there are no consecutive pluses
there are no consecutive pluses
TheBeast5520
2023-05-23 19:14:35
Never two +s in a row
Never two +s in a row
vrondoS
2023-05-23 19:14:35
no consecutive +s
no consecutive +s
timblack
2023-05-23 19:15:04
The operation + doesn't appear twice in a row. This is a good observation that holds at least for $n$ up to $20$. I'd like to investigate whether it always holds. Let's take a look at this for a minute, and then come back to other observations
The operation + doesn't appear twice in a row. This is a good observation that holds at least for $n$ up to $20$. I'd like to investigate whether it always holds. Let's take a look at this for a minute, and then come back to other observations
timblack
2023-05-23 19:15:24
The sequence Z+***+**+++*+* is a fairly arbitrary sequence that happens to result in $158$. Can you find a shorter sequence that gives $158$? Ideally you can find this while doing almost no arithmetic.
The sequence Z+***+**+++*+* is a fairly arbitrary sequence that happens to result in $158$. Can you find a shorter sequence that gives $158$? Ideally you can find this while doing almost no arithmetic.
TheBeast5520
2023-05-23 19:16:05
*++ can be condensed to +*
*++ can be condensed to +*
NoahLeaf
2023-05-23 19:16:05
Because having *++ in a sequence is the same as ending it with +*, but is less efficient.
Because having *++ in a sequence is the same as ending it with +*, but is less efficient.
timchen
2023-05-23 19:16:05
Remove the double +s and replace them with a + before the previous *, to get Z+***+*+*+*+*
Remove the double +s and replace them with a + before the previous *, to get Z+***+*+*+*+*
impromptuA
2023-05-23 19:16:05
Z+***+*+*+*+*
Z+***+*+*+*+*
WangJY01
2023-05-23 19:16:05
Z+***+*+*+*+*
Z+***+*+*+*+*
timblack
2023-05-23 19:16:27
Yes, Z+***+*+*+*+*. Specifically, we've taken a *++ out of the original sequence, and replaced it with +*. This reduces the total number of button presses by one.
Yes, Z+***+*+*+*+*. Specifically, we've taken a *++ out of the original sequence, and replaced it with +*. This reduces the total number of button presses by one.
timblack
2023-05-23 19:16:37
We are always allowed to replace *++ with +*, because if $m$ is the number we have before those presses, we either do *++ to get $(m \times 2) + 1 + 1 = 2m + 2$, or we do +* to get $(m + 1) \times 2 = 2m + 2$. Either way we get the same value!
We are always allowed to replace *++ with +*, because if $m$ is the number we have before those presses, we either do *++ to get $(m \times 2) + 1 + 1 = 2m + 2$, or we do +* to get $(m + 1) \times 2 = 2m + 2$. Either way we get the same value!
timblack
2023-05-23 19:16:54
If we have a shortest sequence from $0$ to $n$, then it can't have *++ in it, or else we could do the operation above, meaning it wasn't actually the shortest.
If we have a shortest sequence from $0$ to $n$, then it can't have *++ in it, or else we could do the operation above, meaning it wasn't actually the shortest.
timblack
2023-05-23 19:17:08
Actually, that means that a shortest sequence can't have two or more + operations in a row, except possibly at the beginning of the sequence, because otherwise those + operations will be preceded by a *, so we would have a *++ in there.
Actually, that means that a shortest sequence can't have two or more + operations in a row, except possibly at the beginning of the sequence, because otherwise those + operations will be preceded by a *, so we would have a *++ in there.
timblack
2023-05-23 19:17:34
There is a shortest sequence without two or more + operations in a row at the beginning either, because we can always replace Z++ with Z+*; either way you get $2$.
There is a shortest sequence without two or more + operations in a row at the beginning either, because we can always replace Z++ with Z+*; either way you get $2$.
bobjoebilly
2023-05-23 19:17:41
beginning it doesn't matter since Z++ is the same as Z+*
beginning it doesn't matter since Z++ is the same as Z+*
timblack
2023-05-23 19:17:57
So, we can now say conclusively that there is a shortest sequence without two or more + operations in a row.
So, we can now say conclusively that there is a shortest sequence without two or more + operations in a row.
timblack
2023-05-23 19:18:26
Let's find some more patterns. Here's the first 20 again:
Let's find some more patterns. Here's the first 20 again:
timblack
2023-05-23 19:18:27
Z $\rightarrow 0$.
Z+ $\rightarrow 1$.
Z+* $\rightarrow 2$.
Z+*+ $\rightarrow 3$.
Z+** $\rightarrow 4$.
Z+**+ $\rightarrow 5$.
Z+*+* $\rightarrow 6$.
Z+*+*+ $\rightarrow 7$.
Z+*** $\rightarrow 8$.
Z+***+ $\rightarrow 9$.
Z+**+* $\rightarrow 10$.
Z+**+*+ $\rightarrow 11$.
Z+*+** $\rightarrow 12$.
Z+*+**+ $\rightarrow 13$.
Z+*+*+* $\rightarrow 14$.
Z+*+*+*+ $\rightarrow 15$.
Z+**** $\rightarrow 16$.
Z+****+ $\rightarrow 17$.
Z+***+* $\rightarrow 18$.
Z+***+*+ $\rightarrow 19$.
Z+**+** $\rightarrow 20$.
Z $\rightarrow 0$.
Z+ $\rightarrow 1$.
Z+* $\rightarrow 2$.
Z+*+ $\rightarrow 3$.
Z+** $\rightarrow 4$.
Z+**+ $\rightarrow 5$.
Z+*+* $\rightarrow 6$.
Z+*+*+ $\rightarrow 7$.
Z+*** $\rightarrow 8$.
Z+***+ $\rightarrow 9$.
Z+**+* $\rightarrow 10$.
Z+**+*+ $\rightarrow 11$.
Z+*+** $\rightarrow 12$.
Z+*+**+ $\rightarrow 13$.
Z+*+*+* $\rightarrow 14$.
Z+*+*+*+ $\rightarrow 15$.
Z+**** $\rightarrow 16$.
Z+****+ $\rightarrow 17$.
Z+***+* $\rightarrow 18$.
Z+***+*+ $\rightarrow 19$.
Z+**+** $\rightarrow 20$.
timblack
2023-05-23 19:18:33
Anything else stand out?
Anything else stand out?
floradaisy136
2023-05-23 19:18:58
odd ones end with +
odd ones end with +
angie.
2023-05-23 19:19:03
Odd numbers always end with a plus.
Odd numbers always end with a plus.
JigglypuffDaBest
2023-05-23 19:19:10
odd number always ends in +?
odd number always ends in +?
timblack
2023-05-23 19:19:19
For odd $n$, the sequence ends in +. Even though we're just noticing this as a pattern, we can actually prove that to get to an odd number, we have to end with +. That's because if we ended with * instead, we would have a whole number times two which is (the definition of) even.
For odd $n$, the sequence ends in +. Even though we're just noticing this as a pattern, we can actually prove that to get to an odd number, we have to end with +. That's because if we ended with * instead, we would have a whole number times two which is (the definition of) even.
epiconan
2023-05-23 19:19:57
oh even number also end with *
oh even number also end with *
timblack
2023-05-23 19:20:05
For even $n$, the sequence ends in *. This sort of make sense: For example, to get to $n = 20$, we could end with a + by doing $19 + 1 = 20$ or we could end with a * by doing $10 \times 2 = 20$. Of those, going from $10$ to $20$ is a much bigger "jump" than $19$ to $20$.
For even $n$, the sequence ends in *. This sort of make sense: For example, to get to $n = 20$, we could end with a + by doing $19 + 1 = 20$ or we could end with a * by doing $10 \times 2 = 20$. Of those, going from $10$ to $20$ is a much bigger "jump" than $19$ to $20$.
EpicBird08
2023-05-23 19:20:28
Let's work backward!
Let's work backward!
mockingjay11
2023-05-23 19:20:28
Try the reverse method
Try the reverse method
akmathisfun2020
2023-05-23 19:20:28
Would it work if I solved the problem backwards, with the buttons $-1$ and $\div 2$, and tried to get from $n$ to $0$?
Would it work if I solved the problem backwards, with the buttons $-1$ and $\div 2$, and tried to get from $n$ to $0$?
MisakaMikasa
2023-05-23 19:20:28
Work backwards
Work backwards
timblack
2023-05-23 19:20:38
I like this idea of thinking backwards to try to get from $n$ back to $0$. Let's carefully write down our method for constructing the sequence of button presses:
I like this idea of thinking backwards to try to get from $n$ back to $0$. Let's carefully write down our method for constructing the sequence of button presses:
LongJumpMain
2023-05-23 19:21:03
The last operation to get to an even number is * and the last to get to an odd number is +
The last operation to get to an even number is * and the last to get to an odd number is +
winstonDeGreef
2023-05-23 19:21:03
now you can work back from n, because if n is even, the last operation must be *, and if its odd the last operation must be +
now you can work back from n, because if n is even, the last operation must be *, and if its odd the last operation must be +
TheBeast5520
2023-05-23 19:21:03
Recursive. For an odd n, it is shortest sequence for n-1 plus a +. For an even n it is shortest sequence for n/2 plus a *
Recursive. For an odd n, it is shortest sequence for n-1 plus a +. For an even n it is shortest sequence for n/2 plus a *
timblack
2023-05-23 19:21:11
Start by writing down $n$ on a piece of paper. We build the sequence backwards. If the number is odd, choose +, then scratch out the number and replace it with $n - 1$. If instead the number is even, choose *, then scratch out the number and replace it with $n / 2$. Repeat until you get down to zero, then stop. Remember that we have chosen the button presses in reverse order.
Start by writing down $n$ on a piece of paper. We build the sequence backwards. If the number is odd, choose +, then scratch out the number and replace it with $n - 1$. If instead the number is even, choose *, then scratch out the number and replace it with $n / 2$. Repeat until you get down to zero, then stop. Remember that we have chosen the button presses in reverse order.
timblack
2023-05-23 19:21:32
Let's do an example of following this procedure. Let's arbitrarily take $n = 42$.
Let's do an example of following this procedure. Let's arbitrarily take $n = 42$.
timblack
2023-05-23 19:21:36
So, $42$ is the answer, but what is thequestion sequence? Follow this method and see if you can come up with the sequence of presses. Z?????? $\rightarrow 42$.
So, $42$ is the answer, but what is the
Curious_Droid
2023-05-23 19:22:14
42 -> 21 -> 20 -> 10 -> 5 -> 4 -> 2 -> 1
42 -> 21 -> 20 -> 10 -> 5 -> 4 -> 2 -> 1
Curious_Droid
2023-05-23 19:22:14
Z+**+**+*
Z+**+**+*
Technodoggo
2023-05-23 19:22:17
Z+**+**+*
Z+**+**+*
FructosePear
2023-05-23 19:22:17
+**+**+*
+**+**+*
timblack
2023-05-23 19:22:30
$42$ is even. We choose *, then replace $42$ with $42 / 2 = 21$.
$42$ is even. We choose *, then replace $42$ with $42 / 2 = 21$.
timblack
2023-05-23 19:22:37
$21$ is odd. We choose +, then replace $21$ with $21 - 1 = 20$.
$21$ is odd. We choose +, then replace $21$ with $21 - 1 = 20$.
timblack
2023-05-23 19:22:43
$20$ is even. We choose *, then replace $20$ with $20 / 2 = 10$.
$20$ is even. We choose *, then replace $20$ with $20 / 2 = 10$.
timblack
2023-05-23 19:22:47
$10$ is even. We choose *, then replace $10$ with $10 / 2 = 5$.
$10$ is even. We choose *, then replace $10$ with $10 / 2 = 5$.
timblack
2023-05-23 19:22:52
$5$ is odd. We choose +, then replace $5$ with $5 - 1 = 4$.
$5$ is odd. We choose +, then replace $5$ with $5 - 1 = 4$.
timblack
2023-05-23 19:22:57
$4$ is even. We choose *, then replace $4$ with $4 / 2 = 2$.
$4$ is even. We choose *, then replace $4$ with $4 / 2 = 2$.
timblack
2023-05-23 19:23:01
$2$ is even. We choose *, then replace $2$ with $2 / 2 = 1$.
$2$ is even. We choose *, then replace $2$ with $2 / 2 = 1$.
timblack
2023-05-23 19:23:06
$1$ is odd. We choose +, then replace $1$ with $1 - 1 = 0$.
$1$ is odd. We choose +, then replace $1$ with $1 - 1 = 0$.
timblack
2023-05-23 19:23:17
$0$ is our stopping condition, so we are done.
$0$ is our stopping condition, so we are done.
timblack
2023-05-23 19:23:31
Remember that we need to read off our button presses in reverse order, so the sequence of presses is Z+**+**+* $\rightarrow 42$.
Remember that we need to read off our button presses in reverse order, so the sequence of presses is Z+**+**+* $\rightarrow 42$.
MisakaMikasa
2023-05-23 19:23:42
How do we rigorously prove that working backwards always results in the most efficient sequence?
How do we rigorously prove that working backwards always results in the most efficient sequence?
timblack
2023-05-23 19:23:48
This will be our method for constructing the sequence. But we are not done. Remember that the instructions say, "As with all problems on the Qualifying Quiz, make sure to justify your answer with a proof." This is the most important part!
This will be our method for constructing the sequence. But we are not done. Remember that the instructions say, "As with all problems on the Qualifying Quiz, make sure to justify your answer with a proof." This is the most important part!
timblack
2023-05-23 19:24:11
Here's what we need to prove:
1. The sequence really results in $n$.
2. When $n$ is odd, the last button press in a shortest sequence is +.
3. When $n$ is even, the last button press in a shortest sequence is *.
We'll take these one at a time.
Here's what we need to prove:
1. The sequence really results in $n$.
2. When $n$ is odd, the last button press in a shortest sequence is +.
3. When $n$ is even, the last button press in a shortest sequence is *.
We'll take these one at a time.
timblack
2023-05-23 19:24:26
1. The sequence really results in $n$.
Notice that when we cross out $a$ and replace it with $b$, we choose the operation that goes from $b$ back to $a$. So hopefully you can see why following the button presses backwards buulds from $0$ up to $n$.
1. The sequence really results in $n$.
Notice that when we cross out $a$ and replace it with $b$, we choose the operation that goes from $b$ back to $a$. So hopefully you can see why following the button presses backwards buulds from $0$ up to $n$.
timblack
2023-05-23 19:24:48
If you want to be formal in your proof, you can use induction on the number of button presses to show that the the number written down at any given time is the number that results from the remaining button presses in reverse order. But for the sake of moving along, I'm not going to do that induction here.
If you want to be formal in your proof, you can use induction on the number of button presses to show that the the number written down at any given time is the number that results from the remaining button presses in reverse order. But for the sake of moving along, I'm not going to do that induction here.
timblack
2023-05-23 19:25:13
2. When $n$ is odd, the last button press in a shortest sequence is +.
We addressed this one before. To get an odd number, you must end in +, because if you ended in * you'd have an even number.
2. When $n$ is odd, the last button press in a shortest sequence is +.
We addressed this one before. To get an odd number, you must end in +, because if you ended in * you'd have an even number.
timblack
2023-05-23 19:25:44
3. When $n$ is even, the last button press in a shortest sequence is *.
This is the hardest statement to prove, but we've already done the hard part. For the sake of contradiction, if the last button press had to be +, what would the second-to-last button press have to be?
3. When $n$ is even, the last button press in a shortest sequence is *.
This is the hardest statement to prove, but we've already done the hard part. For the sake of contradiction, if the last button press had to be +, what would the second-to-last button press have to be?
NoahLeaf
2023-05-23 19:26:11
3. Otherwise, the sequence would have to end in *++, which can be condensed to +*
3. Otherwise, the sequence would have to end in *++, which can be condensed to +*
Shreyasharma
2023-05-23 19:26:11
+
+
epiconan
2023-05-23 19:26:11
+
+
miguel00
2023-05-23 19:26:11
It would have to be +
It would have to be +
timblack
2023-05-23 19:26:21
Right, before the last +, we would have an odd number, which means before that we would have had to have another +. Do you see the problem?
Right, before the last +, we would have an odd number, which means before that we would have had to have another +. Do you see the problem?
timchen
2023-05-23 19:26:47
We said that was bad.
We said that was bad.
oyc_1975
2023-05-23 19:26:47
*++ --> +*
*++ --> +*
winstonDeGreef
2023-05-23 19:26:47
the ++ can be condensed to + before a *
the ++ can be condensed to + before a *
timblack
2023-05-23 19:26:49
We showed earlier that there is a shortest sequence without two + operations in a row. So, we have a contradiction; the last button press doesn't have to be +; it can be *.
We showed earlier that there is a shortest sequence without two + operations in a row. So, we have a contradiction; the last button press doesn't have to be +; it can be *.
timblack
2023-05-23 19:27:07
This finishes the proof!
This finishes the proof!
timblack
2023-05-23 19:27:45
The problem doesn't actually ask for the length of a shortest sequence of presses, just the sequence itself. But if you want to describe the number of presses, you can describe it as
The problem doesn't actually ask for the length of a shortest sequence of presses, just the sequence itself. But if you want to describe the number of presses, you can describe it as
NL008
2023-05-23 19:27:47
It is binary, + is 1 and * is 0
It is binary, + is 1 and * is 0
NL008
2023-05-23 19:27:47
It kind of resembles binary
It kind of resembles binary
timblack
2023-05-23 19:28:09
You can describe it as (length of binary representation of $n$) + (number of 1s in the binary representation of $n$) - 1. I'm not going to prove that today, but it's very related to the sequence of presses itself.
You can describe it as (length of binary representation of $n$) + (number of 1s in the binary representation of $n$) - 1. I'm not going to prove that today, but it's very related to the sequence of presses itself.
winstonDeGreef
2023-05-23 19:28:15
*+ is one and * is 0
*+ is one and * is 0
timblack
2023-05-23 19:28:33
That was a lot of work, but remember that for this first problem, I wanted to go through not just the sequence and the proof, but the whole problem solving process as well.
That was a lot of work, but remember that for this first problem, I wanted to go through not just the sequence and the proof, but the whole problem solving process as well.
timblack
2023-05-23 19:28:38
Remember that you are welcome to ask questions in the chat at any point. I'm going to take just another minute before moving on to problem 2.
Remember that you are welcome to ask questions in the chat at any point. I'm going to take just another minute before moving on to problem 2.
ninjatutle
2023-05-23 19:29:19
is it really a funny calculator though
is it really a funny calculator though
Technodoggo
2023-05-23 19:29:35
it doesn't sound like a calculator...
it doesn't sound like a calculator...
timblack
2023-05-23 19:30:38
Okay! Problem 2!
Okay! Problem 2!
timblack
2023-05-23 19:30:55
2. Ordinarily, when an object bounces off of a surface — whether it's light reflecting from a mirror or a billiard ball bouncing off the side of a billiards table — its path makes the same angle with the surface before and after the bounce. However, a Bizarro Billiards table behaves differently.
The table is a rectangle with two horizontal and two vertical sides in the $x$--$y$ plane. The rule that determines how balls bounce is:
- If the ball is moving up and right along a line with slope $1$, and it hits the top side of the table, it bounces off and continues moving down and right along a line with slope $-1/2$.
- If the ball is moving up and right along a line with slope $2$, and it hits the top side of the table, it bounces off and continues moving down and right along a line with slope $-1$.
- These two bounces are reversible: if the ball is moving up and left along a line with slope $-1/2$ or $-1$, it bounces off and continues moving down and left along a line with slope $1$ or slope $2$, respectively.
- When the ball is bouncing off another side of the table, the rule for bouncing is the same as it would be if you rotated the table to make that side the top side.
\end{itemize}
This rule is summarized in the diagram below.
2. Ordinarily, when an object bounces off of a surface — whether it's light reflecting from a mirror or a billiard ball bouncing off the side of a billiards table — its path makes the same angle with the surface before and after the bounce. However, a Bizarro Billiards table behaves differently.
The table is a rectangle with two horizontal and two vertical sides in the $x$--$y$ plane. The rule that determines how balls bounce is:
- If the ball is moving up and right along a line with slope $1$, and it hits the top side of the table, it bounces off and continues moving down and right along a line with slope $-1/2$.
- If the ball is moving up and right along a line with slope $2$, and it hits the top side of the table, it bounces off and continues moving down and right along a line with slope $-1$.
- These two bounces are reversible: if the ball is moving up and left along a line with slope $-1/2$ or $-1$, it bounces off and continues moving down and left along a line with slope $1$ or slope $2$, respectively.
- When the ball is bouncing off another side of the table, the rule for bouncing is the same as it would be if you rotated the table to make that side the top side.
\end{itemize}
This rule is summarized in the diagram below.
timblack
2023-05-23 19:31:02
timblack
2023-05-23 19:31:52
There were three parts to the problem. We'll take them one at a time.
There were three parts to the problem. We'll take them one at a time.
timblack
2023-05-23 19:31:55
(a) Suppose that the ball starts in the top left corner (point $B$) moving down and right along a line with slope $-1$. If the ball hits side $AD$ and bounces off, then hits side $BC$ and bounces off, and then ends up at corner $D$, what must the proportions of the rectangle be?
(a) Suppose that the ball starts in the top left corner (point $B$) moving down and right along a line with slope $-1$. If the ball hits side $AD$ and bounces off, then hits side $BC$ and bounces off, and then ends up at corner $D$, what must the proportions of the rectangle be?
timblack
2023-05-23 19:32:11
The trajectory of the ball in this problem is shown in the diagram below.
The trajectory of the ball in this problem is shown in the diagram below.
timblack
2023-05-23 19:32:15
timblack
2023-05-23 19:32:31
On the downward bounces, the ball moves with slope $-1$
On the downward bounces, the ball moves with slope $-1$
timblack
2023-05-23 19:32:42
On the upward bounce, the ball moves with slope $2$
On the upward bounce, the ball moves with slope $2$
timblack
2023-05-23 19:33:25
So, if $AB = 1$, how far apart are the bounce points?
So, if $AB = 1$, how far apart are the bounce points?
oyc_1975
2023-05-23 19:33:41
so if $AB = 1$ then we can cut up the path by slope and have $AD = 1+0.5+1 = 2.5$
so if $AB = 1$ then we can cut up the path by slope and have $AD = 1+0.5+1 = 2.5$
oyc_1975
2023-05-23 19:33:41
$1,0.5,1$
$1,0.5,1$
timblack
2023-05-23 19:33:52
On the downward bounces, the ball moves with slope $-1$; therefore, every time it moves a vertical distance of $AB$, it moves a horizontal distance of $AB$ as well.
On the downward bounces, the ball moves with slope $-1$; therefore, every time it moves a vertical distance of $AB$, it moves a horizontal distance of $AB$ as well.
timblack
2023-05-23 19:34:04
On the upward bounce, the ball moves with slope $2$; therefore, when it moves a vertical distance of $AB$, it only moves a horizontal distance of $\frac12AB$.
On the upward bounce, the ball moves with slope $2$; therefore, when it moves a vertical distance of $AB$, it only moves a horizontal distance of $\frac12AB$.
timblack
2023-05-23 19:34:15
Its total horizontal distance traveled is $AB + \frac12AB + AB = \frac52 AB$; therefore, if it ends up traveling a distance of $BC$ horizontally, the proportions of the rectangle must be $AB : BC = 1: \frac52 = 2:5$.
Its total horizontal distance traveled is $AB + \frac12AB + AB = \frac52 AB$; therefore, if it ends up traveling a distance of $BC$ horizontally, the proportions of the rectangle must be $AB : BC = 1: \frac52 = 2:5$.
timblack
2023-05-23 19:34:21
That's (a)!
That's (a)!
Shreyasharma
2023-05-23 19:34:43
timblack
2023-05-23 19:34:52
(b) Suppose that the ball starts in the bottom left corner (point $A$) moving up and right along a line with slope $1$. If the ball hits side $BC$ and bounces off, then hits side $CD$ and bounces off, then hits side $AD$ and bounces off, and then ends up at corner $B$, what must the proportions of the rectangle be?
(b) Suppose that the ball starts in the bottom left corner (point $A$) moving up and right along a line with slope $1$. If the ball hits side $BC$ and bounces off, then hits side $CD$ and bounces off, then hits side $AD$ and bounces off, and then ends up at corner $B$, what must the proportions of the rectangle be?
timblack
2023-05-23 19:35:01
The trajectory of the ball in this problem is shown in the diagram below. Let $X$, $Y$, and $Z$ be the locations of the three points where the ball bounces (on sides $BC$, $CD$, and $AD$, respectively).
The trajectory of the ball in this problem is shown in the diagram below. Let $X$, $Y$, and $Z$ be the locations of the three points where the ball bounces (on sides $BC$, $CD$, and $AD$, respectively).
timblack
2023-05-23 19:35:05
timblack
2023-05-23 19:35:19
We can do similar accounting here, with a bit more work
We can do similar accounting here, with a bit more work
timblack
2023-05-23 19:35:51
We should trace through the slopes:
We should trace through the slopes:
timblack
2023-05-23 19:35:54
BZ?
BZ?
Curious_Droid
2023-05-23 19:36:11
-1/2
-1/2
JigglypuffDaBest
2023-05-23 19:36:11
-1/2
-1/2
timblack
2023-05-23 19:36:13
Slope $-1/2$
Slope $-1/2$
timblack
2023-05-23 19:36:17
ZY?
ZY?
JigglypuffDaBest
2023-05-23 19:36:29
1
1
happypi31415
2023-05-23 19:36:29
$1$
$1$
vrondoS
2023-05-23 19:36:29
1
1
spm269
2023-05-23 19:36:29
1?
1?
timblack
2023-05-23 19:36:34
YX?
YX?
HappyBunny
2023-05-23 19:36:47
-1/2
-1/2
GryFry
2023-05-23 19:36:47
-1/2
-1/2
timblack
2023-05-23 19:36:51
$-1/2$
$-1/2$
timblack
2023-05-23 19:36:58
And XA?
And XA?
Chameleon07
2023-05-23 19:37:04
1
1
CrunchyCucumber
2023-05-23 19:37:04
1
1
timblack
2023-05-23 19:37:08
$1$.
$1$.
timblack
2023-05-23 19:37:20
We know that $AX$ and $YZ$ are parallel lines with slope $1$ (though the ball moves in opposite directions along those lines). Therefore $BX = AB$ and $DY = DZ$.
We know that $AX$ and $YZ$ are parallel lines with slope $1$ (though the ball moves in opposite directions along those lines). Therefore $BX = AB$ and $DY = DZ$.
timblack
2023-05-23 19:37:31
Meanwhile, $XY$ and $ZB$ are parallel lines with slope $-\frac12$ (though, again, the ball moves in opposite directions along those lines). Therefore $XC = 2 CY$ and $AZ = 2AB$.
Meanwhile, $XY$ and $ZB$ are parallel lines with slope $-\frac12$ (though, again, the ball moves in opposite directions along those lines). Therefore $XC = 2 CY$ and $AZ = 2AB$.
timblack
2023-05-23 19:37:42
Because only the proportions of the rectangle matter, let $AB = 1$, so that $BX = 1$ and $AZ = 2$.
Because only the proportions of the rectangle matter, let $AB = 1$, so that $BX = 1$ and $AZ = 2$.
timblack
2023-05-23 19:37:56
We do not yet know $XC$, so let $XC = x$; then $CY = \frac12 x$, $DY = 1 - CY = 1 - \frac12x$, and $DZ = DY = 1 - \frac12x$.
We do not yet know $XC$, so let $XC = x$; then $CY = \frac12 x$, $DY = 1 - CY = 1 - \frac12x$, and $DZ = DY = 1 - \frac12x$.
timblack
2023-05-23 19:38:20
Because $BC = AD$, we get an equation to solve for $x$:
$BX + XC = AZ + ZD \implies 1 + x = 2 + (1 - \frac12x).$
Because $BC = AD$, we get an equation to solve for $x$:
$BX + XC = AZ + ZD \implies 1 + x = 2 + (1 - \frac12x).$
timblack
2023-05-23 19:38:37
Solve for $x$?
Solve for $x$?
miguel00
2023-05-23 19:39:31
x=4/3
x=4/3
impromptuA
2023-05-23 19:39:31
$x=\frac{4}{3}$
$x=\frac{4}{3}$
NoahLeaf
2023-05-23 19:39:31
x=4/3
x=4/3
AoPSyang
2023-05-23 19:39:31
4/3
4/3
timblack
2023-05-23 19:39:33
Solving, we get $x = \frac43$.
Solving, we get $x = \frac43$.
timblack
2023-05-23 19:39:40
So $BC = \frac73$: the proportions of the rectangle must be $AB : BC = 1 : \frac73 = 3 : 7$.
So $BC = \frac73$: the proportions of the rectangle must be $AB : BC = 1 : \frac73 = 3 : 7$.
timblack
2023-05-23 19:39:52
And that's (b)
And that's (b)
rithek.shankar
2023-05-23 19:40:01
Yay
Yay
Mahikohli
2023-05-23 19:40:12
so I did my QT through coordinates, should I have done it this way?
so I did my QT through coordinates, should I have done it this way?
JigglypuffDaBest
2023-05-23 19:40:12
is it ok if I did this in a much more complicated way with much more confusing variables
is it ok if I did this in a much more complicated way with much more confusing variables
timblack
2023-05-23 19:40:21
Yes, there are lots of different ways to solve this
Yes, there are lots of different ways to solve this
timblack
2023-05-23 19:40:35
For that matter, there are usually multiple ways to solve all the problems on the Qualifying Quiz
For that matter, there are usually multiple ways to solve all the problems on the Qualifying Quiz
timblack
2023-05-23 19:40:39
It's more interesting that way
It's more interesting that way
JigglypuffDaBest
2023-05-23 19:41:02
(i know clarity is a big thing)
(i know clarity is a big thing)
timblack
2023-05-23 19:41:22
Clarity is always good. But lots of other things are good too.
Clarity is always good. But lots of other things are good too.
timblack
2023-05-23 19:41:34
(c) Suppose that the rectangle has height $AB = 3$ and width $BC = 5$, and the ball starts in the bottom left corner (point $A$) moving up and right along a line with slope $1$. Describe the trajectory that the ball takes.
(c) Suppose that the rectangle has height $AB = 3$ and width $BC = 5$, and the ball starts in the bottom left corner (point $A$) moving up and right along a line with slope $1$. Describe the trajectory that the ball takes.
timblack
2023-05-23 19:41:52
The first few bounces of the ball are shown in the first diagram below.
The first few bounces of the ball are shown in the first diagram below.
timblack
2023-05-23 19:41:57
timblack
2023-05-23 19:42:12
A few calculations quickly tell us that we're not going to end up in a corner like last time; the collision points have denominators that, experimentally, are increasing powers of $2$.
A few calculations quickly tell us that we're not going to end up in a corner like last time; the collision points have denominators that, experimentally, are increasing powers of $2$.
Curious_Droid
2023-05-23 19:42:29
it kind of goes to the path where the ball keeps returning to its original position after four bounces
it kind of goes to the path where the ball keeps returning to its original position after four bounces
miguel00
2023-05-23 19:42:39
The ball slowly approaches a tradjectory
The ball slowly approaches a tradjectory
timblack
2023-05-23 19:42:59
I like these descriptions. In fact, where the ball "wants" to be is the cyclic trajectory shown in the second diagram below: repeatedly visiting the two points at a distance $1$ from $B$ (along $AB$ and $BC$) and the two points at a distance $1$ from $D$ (along $CD$ and $AD$). We can check that if $AB = CD = 3$ and $BC = AD = 5$, then the sides of this cyclic trajectory have the correct slopes. Unfortunately, the only way to end up on this cyclic trajectory is to start on it; the ball we actually have will never get there.
I like these descriptions. In fact, where the ball "wants" to be is the cyclic trajectory shown in the second diagram below: repeatedly visiting the two points at a distance $1$ from $B$ (along $AB$ and $BC$) and the two points at a distance $1$ from $D$ (along $CD$ and $AD$). We can check that if $AB = CD = 3$ and $BC = AD = 5$, then the sides of this cyclic trajectory have the correct slopes. Unfortunately, the only way to end up on this cyclic trajectory is to start on it; the ball we actually have will never get there.
timblack
2023-05-23 19:43:08
oyc_1975
2023-05-23 19:43:17
slowly approaches a stable loop but never really reaches it
slowly approaches a stable loop but never really reaches it
timblack
2023-05-23 19:43:27
One way to describe the actual path the ball takes is to keep track of the following distances:
- When the ball bounces off $AB$ or $BC$, how far away is it from $B$?
- When the ball bounces off $CD$ or $AD$, how far away is it from $D$?
One way to describe the actual path the ball takes is to keep track of the following distances:
- When the ball bounces off $AB$ or $BC$, how far away is it from $B$?
- When the ball bounces off $CD$ or $AD$, how far away is it from $D$?
timblack
2023-05-23 19:43:38
We can begin by computing these distances for the first few bounces, to see a pattern.
We can begin by computing these distances for the first few bounces, to see a pattern.
timblack
2023-05-23 19:43:51
The ball starts at point $A$, which at distance $3$ from $B$ along $AB$.
The ball starts at point $A$, which at distance $3$ from $B$ along $AB$.
timblack
2023-05-23 19:44:02
The next bounce is on $BC$, at distance ??? from $B$.
The next bounce is on $BC$, at distance ??? from $B$.
Curious_Droid
2023-05-23 19:44:42
3
3
DU4532
2023-05-23 19:44:42
also $3$
also $3$
oyc_1975
2023-05-23 19:44:42
3
3
JigglypuffDaBest
2023-05-23 19:44:42
3
3
timblack
2023-05-23 19:44:45
The next bounce is on $BC$, also at distance $3$ from $B$.
The next bounce is on $BC$, also at distance $3$ from $B$.
timblack
2023-05-23 19:45:02
The next bounce is on $CD$. How far from $D$?
The next bounce is on $CD$. How far from $D$?
AoPSyang
2023-05-23 19:45:41
2
2
oyc_1975
2023-05-23 19:45:41
2
2
NoahLeaf
2023-05-23 19:45:41
2
2
timchen
2023-05-23 19:45:41
Wait $2$
Wait $2$
timblack
2023-05-23 19:45:44
Traveling $2$ units horizontally, the ball travels $1$ unit vertically, so it hits $CD$ at distance $2$ from $D$.
Traveling $2$ units horizontally, the ball travels $1$ unit vertically, so it hits $CD$ at distance $2$ from $D$.
timblack
2023-05-23 19:46:07
The next bounce is on $AD$, also at distance $2$ from $D$ (since we're traveling along a slope of $1$).
The next bounce is on $AD$, also at distance $2$ from $D$ (since we're traveling along a slope of $1$).
timblack
2023-05-23 19:46:17
The next bounce is on $AB$. Traveling $3$ units horizontally, the ball travels $\frac32$ units vertically, so it hits $CD$ at distance $\frac32$ from $B$.
The next bounce is on $AB$. Traveling $3$ units horizontally, the ball travels $\frac32$ units vertically, so it hits $CD$ at distance $\frac32$ from $B$.
timblack
2023-05-23 19:46:33
We've now bounced off each wall once.
We've now bounced off each wall once.
timblack
2023-05-23 19:46:51
The next bounce is on $BC$, at what distance from $B$?
The next bounce is on $BC$, at what distance from $B$?
Chameleon07
2023-05-23 19:47:39
3/2
3/2
rithek.shankar
2023-05-23 19:47:39
3/2
3/2
impromptuA
2023-05-23 19:47:39
3/2
3/2
Mahikohli
2023-05-23 19:47:39
3/2
3/2
timblack
2023-05-23 19:47:41
Right, we're again traveling along a path of slope 1, so we get an isosceles right triangle. The next bounce is on $BC$, also at distance $\frac32$ from $B$.
Right, we're again traveling along a path of slope 1, so we get an isosceles right triangle. The next bounce is on $BC$, also at distance $\frac32$ from $B$.
timblack
2023-05-23 19:47:57
The next bounce is on $CD$. Traveling $5 - \frac32 = \frac72$ units horizontally, the ball travels $\frac74$ units vertically, so it hits $CD$ at distance $3 - \frac74 = \frac54$ from $D$.
The next bounce is on $CD$. Traveling $5 - \frac32 = \frac72$ units horizontally, the ball travels $\frac74$ units vertically, so it hits $CD$ at distance $3 - \frac74 = \frac54$ from $D$.
timblack
2023-05-23 19:48:21
(We're again traveling along a path of slope $-1/2$)
(We're again traveling along a path of slope $-1/2$)
timblack
2023-05-23 19:48:30
Knowing that the first few distances we measure are $3$, $2$, $\frac32$, $\frac54$ and that ultimately they should be getting closer and closer to $1$, we can conjecture the following rule:
Knowing that the first few distances we measure are $3$, $2$, $\frac32$, $\frac54$ and that ultimately they should be getting closer and closer to $1$, we can conjecture the following rule:
timblack
2023-05-23 19:48:43
Conjecture. If we look at $4$ consecutive bounces of the ball, off sides $AB$, $BC$, $CD$, $AD$ in that order, the first two bounces are at distance $1 + (\frac12)^{2k-1}$ from $B$, and the last two bounces are at distance $1 + (\frac12)^{2k}$ from $D$. The value of $k$ increases with each iteration.
Conjecture. If we look at $4$ consecutive bounces of the ball, off sides $AB$, $BC$, $CD$, $AD$ in that order, the first two bounces are at distance $1 + (\frac12)^{2k-1}$ from $B$, and the last two bounces are at distance $1 + (\frac12)^{2k}$ from $D$. The value of $k$ increases with each iteration.
miguel00
2023-05-23 19:49:06
We can prove this by induction
We can prove this by induction
timblack
2023-05-23 19:49:16
Good idea! Once we have conjectured this rule, we can prove it by induction. The first two points where the ball touches the rectangle are indeed at distance $3 = 1 + (\frac12)^{-1}$ from $B$, and the next two are at distance $2 = 1 + (\frac12)^0$ from $D$, which is what the conjecture predicts for $k=0$.
Good idea! Once we have conjectured this rule, we can prove it by induction. The first two points where the ball touches the rectangle are indeed at distance $3 = 1 + (\frac12)^{-1}$ from $B$, and the next two are at distance $2 = 1 + (\frac12)^0$ from $D$, which is what the conjecture predicts for $k=0$.
timblack
2023-05-23 19:49:32
Suppose that one cycle of $4$ bounces happened as predicted. Then, leaving side $AD$ moving up and left along a line of slope $-\frac12$, the ball has $5 - (1 + (\frac12)^{2k}) = 4 - (\frac12)^{2k}$ to travel horizontally, so it travels $2 - (\frac12)^{2k+1}$ vertically, and hits side $AB$ at distance $3 - (2 - (\frac12)^{2k+1}) = 1 + (\frac12)^{2k+1}$ from $B$, as predicted.
Suppose that one cycle of $4$ bounces happened as predicted. Then, leaving side $AD$ moving up and left along a line of slope $-\frac12$, the ball has $5 - (1 + (\frac12)^{2k}) = 4 - (\frac12)^{2k}$ to travel horizontally, so it travels $2 - (\frac12)^{2k+1}$ vertically, and hits side $AB$ at distance $3 - (2 - (\frac12)^{2k+1}) = 1 + (\frac12)^{2k+1}$ from $B$, as predicted.
timblack
2023-05-23 19:49:52
After that, the ball bounces along a line with slope $1$, so it hits $BC$ at the same distance $1 + (\frac12)^{2k+1}$ from $B$.
After that, the ball bounces along a line with slope $1$, so it hits $BC$ at the same distance $1 + (\frac12)^{2k+1}$ from $B$.
timblack
2023-05-23 19:50:12
After that, the ball bounces along a line with slope $-\frac12$ and has a horizontal distance of $5 - (1 + (\frac12)^{2k+1}) = 4 - (\frac12)^{2k+1}$ to travel until it hits $CD$. It travels a vertical distance of $2 - (\frac12)^{2k+2}$ in the same time, and hits $CD$ at a distance of $3 - (2 - (\frac12)^{2k+2}) = 1 + (\frac12)^{2k+2}$ from $D$.
After that, the ball bounces along a line with slope $-\frac12$ and has a horizontal distance of $5 - (1 + (\frac12)^{2k+1}) = 4 - (\frac12)^{2k+1}$ to travel until it hits $CD$. It travels a vertical distance of $2 - (\frac12)^{2k+2}$ in the same time, and hits $CD$ at a distance of $3 - (2 - (\frac12)^{2k+2}) = 1 + (\frac12)^{2k+2}$ from $D$.
timblack
2023-05-23 19:50:30
Ooof, a lot of formulas
Ooof, a lot of formulas
timblack
2023-05-23 19:50:43
But the nice thing about formulas is that you can sit down and grind them out
But the nice thing about formulas is that you can sit down and grind them out
timblack
2023-05-23 19:50:52
Almost done.
Almost done.
timblack
2023-05-23 19:50:54
After that, the ball bounces along a line with slope $1$, so it hits $AD$ at the same distance of $1 + (\frac12)^{2k+2}$ from $D$.
After that, the ball bounces along a line with slope $1$, so it hits $AD$ at the same distance of $1 + (\frac12)^{2k+2}$ from $D$.
timblack
2023-05-23 19:51:20
That's right where we are supposed to be after one cycle!
That's right where we are supposed to be after one cycle!
timblack
2023-05-23 19:51:26
We have completed one more iteration of the cycle in accordance with the conjecture. By induction on $k$, we will continue bouncing in the same way forever.
We have completed one more iteration of the cycle in accordance with the conjecture. By induction on $k$, we will continue bouncing in the same way forever.
timblack
2023-05-23 19:52:03
That's wraps up problem 2!
That's wraps up problem 2!
timblack
2023-05-23 19:52:21
I'll pause for a moment before moving on to problem 3
I'll pause for a moment before moving on to problem 3
timblack
2023-05-23 19:52:40
This is a good time to use the chat for questions, or to express your sense of excitement and adventure
This is a good time to use the chat for questions, or to express your sense of excitement and adventure
EpicBird08
2023-05-23 19:52:45
problem 3b was WONDERFUL
problem 3b was WONDERFUL
Curious_Droid
2023-05-23 19:53:16
a pool table couldnt realistically have this property... right?
a pool table couldnt realistically have this property... right?
timblack
2023-05-23 19:53:20
I don't think so
I don't think so
timblack
2023-05-23 19:53:28
I thought about it a bit...
I thought about it a bit...
rithek.shankar
2023-05-23 19:54:00
Magnetic ones chould
Magnetic ones chould
timblack
2023-05-23 19:54:03
hmmm
hmmm
rithek.shankar
2023-05-23 19:54:09
Time for 3
Time for 3
rithek.shankar
2023-05-23 19:54:09
3 is my favorite
3 is my favorite
timblack
2023-05-23 19:54:15
Okay, let's do it
Okay, let's do it
timblack
2023-05-23 19:54:55
3. You have $4046$ identical-looking coins, but $2023$ of them weigh $1$ gram each, while the other $2023$ coins weigh $2$ grams each. You cannot distinguish these coins in any way manually. However, you have a partially-working scale, tuned to some unknown integer value $X$: when you weigh a set of coins, the scale reports if the weight is ``less than $X$ grams'' or ``at least $X$ grams''. You know that $1 < X < 6070$.
3. You have $4046$ identical-looking coins, but $2023$ of them weigh $1$ gram each, while the other $2023$ coins weigh $2$ grams each. You cannot distinguish these coins in any way manually. However, you have a partially-working scale, tuned to some unknown integer value $X$: when you weigh a set of coins, the scale reports if the weight is ``less than $X$ grams'' or ``at least $X$ grams''. You know that $1 < X < 6070$.
timblack
2023-05-23 19:55:16
One of my favorite problems too. I read a lot of submissions, so thought a lot about it
One of my favorite problems too. I read a lot of submissions, so thought a lot about it
timblack
2023-05-23 19:55:24
(a) Prove that you can eventually find a set of coins that weighs exactly X grams.
(a) Prove that you can eventually find a set of coins that weighs exactly X grams.
timblack
2023-05-23 19:55:32
(b) Prove that you can find such a set in at most 10000 weighings.
(b) Prove that you can find such a set in at most 10000 weighings.
timblack
2023-05-23 19:55:46
Note the scale never tell you "exactly $X$ grams." If the coins on the scale weigh exactly $X$ grams, the scale will still just tell you "at least $X$ grams."
Note the scale never tell you "exactly $X$ grams." If the coins on the scale weigh exactly $X$ grams, the scale will still just tell you "at least $X$ grams."
Curious_Droid
2023-05-23 19:56:09
i am still finding bugs in my submission to 3b to this day
i am still finding bugs in my submission to 3b to this day
timblack
2023-05-23 19:56:14
Thank you for sharing this!
Thank you for sharing this!
timblack
2023-05-23 19:56:20
I think it captures a common sentiment
I think it captures a common sentiment
timblack
2023-05-23 19:56:26
There are a lot of moving parts here
There are a lot of moving parts here
timblack
2023-05-23 19:56:35
Technically, if you solve part (b), you've automatically solved part (a). But this problem has a lot of moving parts, and it's especially easy to overlook something in part (b). So, if you can come up with a separate, simpler solution that works just for part (a) that you are sure is right, it was probably a good idea to write that up separately and submit it. So, we'll come up with a solution to (a) first.
Technically, if you solve part (b), you've automatically solved part (a). But this problem has a lot of moving parts, and it's especially easy to overlook something in part (b). So, if you can come up with a separate, simpler solution that works just for part (a) that you are sure is right, it was probably a good idea to write that up separately and submit it. So, we'll come up with a solution to (a) first.
timblack
2023-05-23 19:57:18
Actually, we'll start with a bit of a side observation (but keep in mind there are many different ways to approach this)
Actually, we'll start with a bit of a side observation (but keep in mind there are many different ways to approach this)
timblack
2023-05-23 19:57:20
Let set $S$ and $T$ be two equally sized sets of coin that differ by a single coin. That is, you can get from $S$ to $T$ by removing one coin and adding a different one. Suppose that you weigh each set on the broken scale, and find that $S$ has weight "less than $X$ grams" and $T$ has weight "at least $X$ grams." What more specifically can you say about the weight of $S$ and $T$?
Let set $S$ and $T$ be two equally sized sets of coin that differ by a single coin. That is, you can get from $S$ to $T$ by removing one coin and adding a different one. Suppose that you weigh each set on the broken scale, and find that $S$ has weight "less than $X$ grams" and $T$ has weight "at least $X$ grams." What more specifically can you say about the weight of $S$ and $T$?
lpieleanu
2023-05-23 19:58:53
$S = X-1, T = X$
$S = X-1, T = X$
Curious_Droid
2023-05-23 19:58:53
S must be X-1 and T must be X?
S must be X-1 and T must be X?
timchen
2023-05-23 19:58:53
$T=X,S=X-1$
$T=X,S=X-1$
akmathisfun2020
2023-05-23 19:58:53
T is X grams and S is X-1 grams
T is X grams and S is X-1 grams
CrunchyCucumber
2023-05-23 19:58:53
T weighs X and S weights X-1
T weighs X and S weights X-1
timblack
2023-05-23 19:58:58
I'd prefer to say that $T$ weighs $X$ grams rather than $T = X$, but otherwise I agree.
I'd prefer to say that $T$ weighs $X$ grams rather than $T = X$, but otherwise I agree.
timblack
2023-05-23 19:59:08
$S$ weighs exactly $X - 1$ grams, and $T$ weighs exactly $X$ grams.
$S$ weighs exactly $X - 1$ grams, and $T$ weighs exactly $X$ grams.
timblack
2023-05-23 19:59:24
Exactly! "Exactly" is hard to come by in this problem
Exactly! "Exactly" is hard to come by in this problem
timblack
2023-05-23 19:59:30
All the coins weigh either $1$ or $2$ grams, so when you swap out one coin for another, it can change the weight of the pile by at most $1$ gram. Since $S$ weighs at most $X - 1$ grams and $T$ weighs at least $X$ grams, and the sets can differ by at most $1$ gram, we know exactly how much each of those two piles weigh.
All the coins weigh either $1$ or $2$ grams, so when you swap out one coin for another, it can change the weight of the pile by at most $1$ gram. Since $S$ weighs at most $X - 1$ grams and $T$ weighs at least $X$ grams, and the sets can differ by at most $1$ gram, we know exactly how much each of those two piles weigh.
timblack
2023-05-23 19:59:52
Now let's say $S$ and $T$ are two sets with the same size, but now these sets might have any number of coins in common, or none at all. Again, say that you weigh each set, and find $S$ weights "less than $X$ grams" while $T$ weighs "at least $X$ grams." How can you use the broken scale to find a set that weighs exactly $X$ grams?
Now let's say $S$ and $T$ are two sets with the same size, but now these sets might have any number of coins in common, or none at all. Again, say that you weigh each set, and find $S$ weights "less than $X$ grams" while $T$ weighs "at least $X$ grams." How can you use the broken scale to find a set that weighs exactly $X$ grams?
oyc_1975
2023-05-23 20:00:44
keep on swapping coins?
keep on swapping coins?
Curious_Droid
2023-05-23 20:00:44
try swapping coins between sets
try swapping coins between sets
timblack
2023-05-23 20:00:50
Something to do with swapping coins...
Something to do with swapping coins...
CrunchyCucumber
2023-05-23 20:01:02
Transfer coins between the two sets?
Transfer coins between the two sets?
NoahLeaf
2023-05-23 20:01:11
Switch coins from one to the other one at a time
Switch coins from one to the other one at a time
timblack
2023-05-23 20:01:29
Start with $S$ on the broken scale. We'll swap out coins from $S$ one at a time for coins from $T$, and after each swap we'll take a weighing.
Start with $S$ on the broken scale. We'll swap out coins from $S$ one at a time for coins from $T$, and after each swap we'll take a weighing.
timblack
2023-05-23 20:01:40
If you prefer set notation, here's a more precise way to say this:
- Let $V$ be the intersection of $S$ and $T$.
- Let $s_1, s_2, \dots, s_k$ be the coins that are in $S$ but not $T$.
- Let $t_1, t_2, \dots, t_k$ be the coins that are in $T$ but not $S$.
- So $S = V \cup \{s_1, s_2, \dots, s_k\}$ and $T = V \cup \{t_1, t_2, \dots, t_k\}$.
- For $i = 0, 1, \dots, k$, let $S_i = V \cup \{t_1, t_2, \dots, t_i, s_{i + 1}, s_{i + 2}, \dots, s_k\}$.
- So, $S_0 = S$ and $S_k = T$.
- Each $S_i$ differs from $S_{i + 1}$ by swapping out exactly one coin.
- We weigh $S_0 = S$, then $S_1$, then $S_2$, and so on on the broken scale.
If you prefer set notation, here's a more precise way to say this:
- Let $V$ be the intersection of $S$ and $T$.
- Let $s_1, s_2, \dots, s_k$ be the coins that are in $S$ but not $T$.
- Let $t_1, t_2, \dots, t_k$ be the coins that are in $T$ but not $S$.
- So $S = V \cup \{s_1, s_2, \dots, s_k\}$ and $T = V \cup \{t_1, t_2, \dots, t_k\}$.
- For $i = 0, 1, \dots, k$, let $S_i = V \cup \{t_1, t_2, \dots, t_i, s_{i + 1}, s_{i + 2}, \dots, s_k\}$.
- So, $S_0 = S$ and $S_k = T$.
- Each $S_i$ differs from $S_{i + 1}$ by swapping out exactly one coin.
- We weigh $S_0 = S$, then $S_1$, then $S_2$, and so on on the broken scale.
timblack
2023-05-23 20:02:45
But frankly, the set notation doesn't matter too much here if you understand what I mean by swapping coins one at a time
But frankly, the set notation doesn't matter too much here if you understand what I mean by swapping coins one at a time
timblack
2023-05-23 20:03:00
We already know weighing $S$ results in "less than $X$ grams." Then we swap out a coin, and we might get "less than $X$ grams," or we might get "at least $X$ grams." If we get "at least", stop. As long as we keep getting "less than," swap out another coin and weigh again. We know we'll eventually see "at least," because if nothing stops us earlier, we'll eventually have $T$ on the scale, which we know weighs "at least $X$ grams."
We already know weighing $S$ results in "less than $X$ grams." Then we swap out a coin, and we might get "less than $X$ grams," or we might get "at least $X$ grams." If we get "at least", stop. As long as we keep getting "less than," swap out another coin and weigh again. We know we'll eventually see "at least," because if nothing stops us earlier, we'll eventually have $T$ on the scale, which we know weighs "at least $X$ grams."
GryFry
2023-05-23 20:03:18
when set s becomes at least X grams, S weighs exactly X grams
when set s becomes at least X grams, S weighs exactly X grams
timblack
2023-05-23 20:03:53
Nice. Let's think about that first set $S_i$ that weighs "at least $X$ grams." We know that we got that set by taking another set, $S_{i - 1}$ that weighed "less than $X$ grams," and swapping a single coin. So $S_i$ must weigh exactly $X$ grams.
Nice. Let's think about that first set $S_i$ that weighs "at least $X$ grams." We know that we got that set by taking another set, $S_{i - 1}$ that weighed "less than $X$ grams," and swapping a single coin. So $S_i$ must weigh exactly $X$ grams.
timblack
2023-05-23 20:04:14
Since we already knew the weight of $S_0 = S$ and $S_k = T$, this process takes at most $k - 1$ additional weighings, where $k$ is at most the size of $S$ (which equals the size of $T$).
Since we already knew the weight of $S_0 = S$ and $S_k = T$, this process takes at most $k - 1$ additional weighings, where $k$ is at most the size of $S$ (which equals the size of $T$).
timblack
2023-05-23 20:04:34
For a set $S$ of coins, let $\#S$ be the number of coins in $S$. To summarize:
Lemma: Let $S$ and $T$ be sets of coins with $\#S = \#T$. Suppose that $S$ weighs "less than $X$ grams" and $T$ weighs "at least $X$ grams." Then it is possible to find a set weighing exactly $X$ grams using fewer than $\#S$ additional weighings with the broken scale.
For a set $S$ of coins, let $\#S$ be the number of coins in $S$. To summarize:
Lemma: Let $S$ and $T$ be sets of coins with $\#S = \#T$. Suppose that $S$ weighs "less than $X$ grams" and $T$ weighs "at least $X$ grams." Then it is possible to find a set weighing exactly $X$ grams using fewer than $\#S$ additional weighings with the broken scale.
Curious_Droid
2023-05-23 20:04:54
well then we could be basically done as long as we find two same-size sets of coins one <X and one >=X?
well then we could be basically done as long as we find two same-size sets of coins one <X and one >=X?
timblack
2023-05-23 20:05:03
Yes, we now have one avenue to solving the problem!
Yes, we now have one avenue to solving the problem!
timblack
2023-05-23 20:05:40
If we can find a pair of sets where one weighs less than $X$ grams and the other weighs at least, and the have the same number of coins, we can apply the lemma and be done
If we can find a pair of sets where one weighs less than $X$ grams and the other weighs at least, and the have the same number of coins, we can apply the lemma and be done
timblack
2023-05-23 20:05:57
Okay, so let's see if this helps with (a)
Okay, so let's see if this helps with (a)
timblack
2023-05-23 20:06:01
In part (a), we're allowed an unlimited number of weighings with the broken scale. So if we want, we can just weigh every possible set of coins. How many weighings would that be?
In part (a), we're allowed an unlimited number of weighings with the broken scale. So if we want, we can just weigh every possible set of coins. How many weighings would that be?
happypi31415
2023-05-23 20:07:17
2^4046
2^4046
wilsonstmartin
2023-05-23 20:07:17
$2^2024
$2^2024
NoahLeaf
2023-05-23 20:07:17
$2^{4046}$, although we can reduce this by one by not considering the empty set
$2^{4046}$, although we can reduce this by one by not considering the empty set
timblack
2023-05-23 20:07:25
There are $4046$ coins, so there are $2^{4046}$ sets of coins. It would take... a while... to weigh them all, but it's allowed.
There are $4046$ coins, so there are $2^{4046}$ sets of coins. It would take... a while... to weigh them all, but it's allowed.
timblack
2023-05-23 20:07:43
If we do all those weighings, and we find two sets that have the same size, but where one weighs "less than $X$ grams" and the other weighs "at least $X$ grams," then that's great; we can apply the lemma to find a set that weighs exactly $X$ grams.
If we do all those weighings, and we find two sets that have the same size, but where one weighs "less than $X$ grams" and the other weighs "at least $X$ grams," then that's great; we can apply the lemma to find a set that weighs exactly $X$ grams.
MisakaMikasa
2023-05-23 20:07:52
Is it always possible to find two sets that complies the conditions?
Is it always possible to find two sets that complies the conditions?
timblack
2023-05-23 20:07:54
Do you think there are always two such sets?
Do you think there are always two such sets?
CrunchyCucumber
2023-05-23 20:08:55
yes
yes
vrondoS
2023-05-23 20:08:55
yes
yes
ninjatutle
2023-05-23 20:08:55
not always...
not always...
snow52
2023-05-23 20:08:55
no
no
lpieleanu
2023-05-23 20:08:55
yep
yep
akmathisfun2020
2023-05-23 20:08:55
no
no
timblack
2023-05-23 20:08:59
Yes! Well... technically, no... If $X = 6069$, then only the set of all coins weighs "at least $X$ grams," and all other sets weigh "less than $X$ grams." But this case is easy to spot if you weigh all $2^{4046}$ sets, and in this case the answer is the set of all coins.
Yes! Well... technically, no... If $X = 6069$, then only the set of all coins weighs "at least $X$ grams," and all other sets weigh "less than $X$ grams." But this case is easy to spot if you weigh all $2^{4046}$ sets, and in this case the answer is the set of all coins.
timblack
2023-05-23 20:09:17
But otherwise, as long as $X \neq 6069$, then yes, there do exist $S$ and $T$ with the same number of coins with $S$ weighing "less than $X$ grams" and $T$ weighing "at least $X$ grams." Here's why:
But otherwise, as long as $X \neq 6069$, then yes, there do exist $S$ and $T$ with the same number of coins with $S$ weighing "less than $X$ grams" and $T$ weighing "at least $X$ grams." Here's why:
timblack
2023-05-23 20:09:36
Consider taking as many 2g coins as you can without going over $X$ grams (using all $2023$ 2g coins if necessary), and then adding to that as many 1g coins as you need to hit exactly $X$ grams. Let this set be $T$. Then, take away a 2g coin (there will be at least one 2g coin because $X \geq 2$) and replace it with a 1g coin (there will be at least one 1g coin left over because $X < 6069$). Let this set set be $S$; it weighs $X - 1$ grams.
Consider taking as many 2g coins as you can without going over $X$ grams (using all $2023$ 2g coins if necessary), and then adding to that as many 1g coins as you need to hit exactly $X$ grams. Let this set be $T$. Then, take away a 2g coin (there will be at least one 2g coin because $X \geq 2$) and replace it with a 1g coin (there will be at least one 1g coin left over because $X < 6069$). Let this set set be $S$; it weighs $X - 1$ grams.
timblack
2023-05-23 20:10:09
Since we don't know $X$, and we don't know which coins are 1g coins, and we don't know which coins are 2g coins, we cannot actually construct this specific $S$ and $T$, but all we need to know is that such an $S$ and $T$ exist. We weigh all $2^{4046}$ sets, find an appropriate $S$ and $T$ from that, then apply the lemma.
Since we don't know $X$, and we don't know which coins are 1g coins, and we don't know which coins are 2g coins, we cannot actually construct this specific $S$ and $T$, but all we need to know is that such an $S$ and $T$ exist. We weigh all $2^{4046}$ sets, find an appropriate $S$ and $T$ from that, then apply the lemma.
Curious_Droid
2023-05-23 20:10:34
epic
epic
timblack
2023-05-23 20:10:37
timblack
2023-05-23 20:10:44
That finishes part (a).
That finishes part (a).
timblack
2023-05-23 20:11:20
Although, again, it's not the only way to do part (a).
Although, again, it's not the only way to do part (a).
winstonDeGreef
2023-05-23 20:11:23
thats completely different to how I solved a
thats completely different to how I solved a
timblack
2023-05-23 20:11:41
Now let's move onto part (b).
Now let's move onto part (b).
timblack
2023-05-23 20:11:49
(b) Prove that you can find such a set in at most 10000 weighings.
(b) Prove that you can find such a set in at most 10000 weighings.
timblack
2023-05-23 20:12:03
We're not going to go for the absolute minimum number of weighings right now, though I'll make some comments on that at the end. We'll be content just to get the number under 10000. Which, incidentally, is a lot less than $2^{4046}$, so we have some work to do.
We're not going to go for the absolute minimum number of weighings right now, though I'll make some comments on that at the end. We'll be content just to get the number under 10000. Which, incidentally, is a lot less than $2^{4046}$, so we have some work to do.
timblack
2023-05-23 20:12:29
We will start with an empty scale. Then, we'll add coins to the scale one at a time. Each time we add a coin, we'll take a reading. As long as the scale keeps saying "less than $X$ grams," we'll keep going. The first time the scale reads "at least $X$ grams," we'll stop. Let $P$ be the set of coins on the scale when we reach this stopping point.
We will start with an empty scale. Then, we'll add coins to the scale one at a time. Each time we add a coin, we'll take a reading. As long as the scale keeps saying "less than $X$ grams," we'll keep going. The first time the scale reads "at least $X$ grams," we'll stop. Let $P$ be the set of coins on the scale when we reach this stopping point.
timblack
2023-05-23 20:12:48
Since we were adding coins one by one, and set $P$ was the first set that weighed "at least $X$ grams," can we say that $P$ weighs exactly $X$ grams?
Since we were adding coins one by one, and set $P$ was the first set that weighed "at least $X$ grams," can we say that $P$ weighs exactly $X$ grams?
GryFry
2023-05-23 20:13:23
no
no
winstonDeGreef
2023-05-23 20:13:23
no, it might weigh X+1
no, it might weigh X+1
TheBeast5520
2023-05-23 20:13:23
No, either X or X+1
No, either X or X+1
MathFun1000
2023-05-23 20:13:23
no it could weight $X$ or $X+1$ grams
no it could weight $X$ or $X+1$ grams
bburubburu
2023-05-23 20:13:23
no, it could be x+1
no, it could be x+1
timblack
2023-05-23 20:13:53
That's right. No, we can't. Set $P$ might weigh exactly $X$ grams, but it might instead weigh $X + 1$ grams. That could happen if the scale previously weighed $X - 1$ grams (which reads as "less than $X$ grams") and then we add a 2g coin, resulting in $X + 1$ grams (which reads as "at least $X$ grams").
That's right. No, we can't. Set $P$ might weigh exactly $X$ grams, but it might instead weigh $X + 1$ grams. That could happen if the scale previously weighed $X - 1$ grams (which reads as "less than $X$ grams") and then we add a 2g coin, resulting in $X + 1$ grams (which reads as "at least $X$ grams").
timblack
2023-05-23 20:14:04
The good news is that set $P$ can only read either $X$ grams or $X + 1$ grams. We know that it's at least $X$ because the scale told us so. And, we know that it's at most $X + 1$, because prior to the addition, the scale weighed at most $X - 1$ grams, and then we added one more coin weighing at most 2g, so the weight of the pile is at most $(X - 1) + 2 = X + 1$.
The good news is that set $P$ can only read either $X$ grams or $X + 1$ grams. We know that it's at least $X$ because the scale told us so. And, we know that it's at most $X + 1$, because prior to the addition, the scale weighed at most $X - 1$ grams, and then we added one more coin weighing at most 2g, so the weight of the pile is at most $(X - 1) + 2 = X + 1$.
timblack
2023-05-23 20:14:29
From here, we're going to split into two cases:
- Case 1: $P$ consists of at least $2024$ coins.
- Case 2: $P$ consists of at most $2023$ coins.
We'll see why we're splitting it this way in a moment. We'll start with case 1.
From here, we're going to split into two cases:
- Case 1: $P$ consists of at least $2024$ coins.
- Case 2: $P$ consists of at most $2023$ coins.
We'll see why we're splitting it this way in a moment. We'll start with case 1.
timblack
2023-05-23 20:15:08
Getting this set $P$ that weighs $X$ or $X+1$ is key, but somehow it's still some work to narrow it down to just $X$.
Getting this set $P$ that weighs $X$ or $X+1$ is key, but somehow it's still some work to narrow it down to just $X$.
timblack
2023-05-23 20:15:25
Case 1: $P$ consists of at least $2024$ coins.
Case 1: $P$ consists of at least $2024$ coins.
timblack
2023-05-23 20:15:33
In this case, start with $P$ on the scale. Remove one coin from the scale, weigh the remainder, and then put the coin back so that you again have $P$ on the scale. Do this for every coin in $P$.
In this case, start with $P$ on the scale. Remove one coin from the scale, weigh the remainder, and then put the coin back so that you again have $P$ on the scale. Do this for every coin in $P$.
timblack
2023-05-23 20:15:37
Equivalently, in set notation, weigh $P \smallsetminus \{c\}$ for each coin $c$ in $P$.
Equivalently, in set notation, weigh $P \smallsetminus \{c\}$ for each coin $c$ in $P$.
timblack
2023-05-23 20:16:00
Now, since $P$ weighs either $X$ or just barely more than $X$, you would think that typically that $P$ minus one coin would weigh less than $X$ grams. However, not always. If $P$ minus some coin weighs "at least $X$ grams," what can you conclude?
Now, since $P$ weighs either $X$ or just barely more than $X$, you would think that typically that $P$ minus one coin would weigh less than $X$ grams. However, not always. If $P$ minus some coin weighs "at least $X$ grams," what can you conclude?
vrondoS
2023-05-23 20:16:48
it is exactly X
it is exactly X
akmathisfun2020
2023-05-23 20:16:48
we have X grams
we have X grams
zheng_ann
2023-05-23 20:16:48
those coins are 1g
those coins are 1g
Chameleon07
2023-05-23 20:16:48
You've hit X after removing coin
You've hit X after removing coin
happypi31415
2023-05-23 20:16:48
the coin was worth 1
the coin was worth 1
snow52
2023-05-23 20:16:48
it is exactly X grams
it is exactly X grams
UnknownMonkey
2023-05-23 20:16:48
That coin you removed weighs 1 gram
That coin you removed weighs 1 gram
AoPSyang
2023-05-23 20:16:48
it must equal to X grams
it must equal to X grams
timblack
2023-05-23 20:16:54
Indeed. Since $P$ weighs at most $X + 1$ grams, and each coin weighs at least 1g, then $P$ minus a coin must weigh at most $(X + 1) - 1 = X$ grams. So if it also weighs at least $X$ grams, we can conclude that $P$ minus that coin weighs exactly $X$ grams.
Indeed. Since $P$ weighs at most $X + 1$ grams, and each coin weighs at least 1g, then $P$ minus a coin must weigh at most $(X + 1) - 1 = X$ grams. So if it also weighs at least $X$ grams, we can conclude that $P$ minus that coin weighs exactly $X$ grams.
timblack
2023-05-23 20:17:12
So, if there is any coin in $P$ for which $P$ minus that coin weighs "at least $X$ grams," then $P$ minus that coin weighs exactly $X$ grams, and we are done. Yay!
So, if there is any coin in $P$ for which $P$ minus that coin weighs "at least $X$ grams," then $P$ minus that coin weighs exactly $X$ grams, and we are done. Yay!
DU4532
2023-05-23 20:17:21
yey
yey
timblack
2023-05-23 20:17:33
That means that from now on we only need to worry about what happens when $P$ minus a coin weighs "less than $X$ grams" for every coin in $P$.
That means that from now on we only need to worry about what happens when $P$ minus a coin weighs "less than $X$ grams" for every coin in $P$.
timblack
2023-05-23 20:18:06
But also, since $P$ has at least $2024$ coins, it must contain at least one 1g coin. Why?
But also, since $P$ has at least $2024$ coins, it must contain at least one 1g coin. Why?
shihan
2023-05-23 20:18:43
pigeonhole principle
pigeonhole principle
wilsonstmartin
2023-05-23 20:18:43
only $2023$ 2 weight coins
only $2023$ 2 weight coins
ThousandthStar
2023-05-23 20:18:43
There are 2023 2g coins
There are 2023 2g coins
cinnamoncrunch
2023-05-23 20:18:43
Because there are 2023 2g coins
Because there are 2023 2g coins
Rinnypig
2023-05-23 20:18:43
Because there are only 2023 2g coins.
Because there are only 2023 2g coins.
FlyingPig7
2023-05-23 20:18:43
because there are only 2023 2g coins
because there are only 2023 2g coins
timblack
2023-05-23 20:18:55
There are only $2023$ 2g coins, so there just aren't enough of them for all of $P$ to be 2g coins.
There are only $2023$ 2g coins, so there just aren't enough of them for all of $P$ to be 2g coins.
timblack
2023-05-23 20:19:06
This, incidentally, is why I wanted to split off the case that $P$ consists of at least $2024$ coins.
This, incidentally, is why I wanted to split off the case that $P$ consists of at least $2024$ coins.
timblack
2023-05-23 20:19:30
Okay, so $P$ has a 1g coin. Which means that $P$ minus a 1g coin weighs "less than X," So $P$ itself weighs less than $X + 1$ grams. But since $P$ weighs at least $X$ grams, that means it weighs exactly $X$ grams.
Okay, so $P$ has a 1g coin. Which means that $P$ minus a 1g coin weighs "less than X," So $P$ itself weighs less than $X + 1$ grams. But since $P$ weighs at least $X$ grams, that means it weighs exactly $X$ grams.
timblack
2023-05-23 20:20:03
So then we can conclude that $P$ itself weighs $X$ grams exactly, so again we have found our set of coins!
So then we can conclude that $P$ itself weighs $X$ grams exactly, so again we have found our set of coins!
VanuTalin
2023-05-23 20:20:20
Horray!
Horray!
miguel00
2023-05-23 20:20:20
timblack
2023-05-23 20:20:23
So, that's how we find at set of weight exactly $X$ grams in case $1$. How many weighings does it take?
So, that's how we find at set of weight exactly $X$ grams in case $1$. How many weighings does it take?
miguel00
2023-05-23 20:21:24
At most 4046*2
At most 4046*2
Curious_Droid
2023-05-23 20:21:24
4046 + 4046 = 8092?
4046 + 4046 = 8092?
shihan
2023-05-23 20:21:24
$\le 8092$ weighings
$\le 8092$ weighings
timblack
2023-05-23 20:21:27
Adding one coin at a time to the scale to find $P$ takes at most $4046$, and removing (and then replacing) each coin in turn takes another $4046$ at most, so we use at most $4046 + 4046 = 8092$ weighings in total.
Adding one coin at a time to the scale to find $P$ takes at most $4046$, and removing (and then replacing) each coin in turn takes another $4046$ at most, so we use at most $4046 + 4046 = 8092$ weighings in total.
timblack
2023-05-23 20:21:40
(I see lots of other numbers in the chat, which may be right if you are careful about it)
(I see lots of other numbers in the chat, which may be right if you are careful about it)
timblack
2023-05-23 20:21:54
That wraps up case 1.
That wraps up case 1.
ThousandthStar
2023-05-23 20:22:28
Why does replacing a coin count as a weighing?
Why does replacing a coin count as a weighing?
timblack
2023-05-23 20:22:58
Replacing itself doesn't count as a weighing, but while the coin is removed we do a weighing
Replacing itself doesn't count as a weighing, but while the coin is removed we do a weighing
timblack
2023-05-23 20:23:20
Case 2: $P$ consists of at most $2023$ coins.
Case 2: $P$ consists of at most $2023$ coins.
timblack
2023-05-23 20:23:31
Let $k = \#P$. That is, let $k$ be the number of coins in $P$.
Let $k = \#P$. That is, let $k$ be the number of coins in $P$.
MathFun1000
2023-05-23 20:24:01
In this case the complement of $P$ is equivalent of $P$ in case 1
In this case the complement of $P$ is equivalent of $P$ in case 1
timblack
2023-05-23 20:24:16
What do we think? Can we just do the same thing with the complement of the set?
What do we think? Can we just do the same thing with the complement of the set?
timblack
2023-05-23 20:25:16
Well, maybe, but it would still take more work. This problem is not symmetric. For one, there is an asymmetry between "less than" and "at least" (note it's not "less than" and "greater than")
Well, maybe, but it would still take more work. This problem is not symmetric. For one, there is an asymmetry between "less than" and "at least" (note it's not "less than" and "greater than")
timblack
2023-05-23 20:25:31
And also, we don't get to "complement" $X$
And also, we don't get to "complement" $X$
timblack
2023-05-23 20:25:49
So, we'll really just have to do some more work
Lots of people tried that though
So, we'll really just have to do some more work
Lots of people tried that though
timblack
2023-05-23 20:26:08
Let $k = \#P$. That is, let $k$ be the size of $P$.
If $k = 1$, then since $X \geq 2$, the only way to have $P$ weigh at least $X$ grams is to have $X = 2$, and $P$ consists of a single 2g coin. Then we can conclude that $P$ weighs exactly $X$, and we are set.
Let $k = \#P$. That is, let $k$ be the size of $P$.
If $k = 1$, then since $X \geq 2$, the only way to have $P$ weigh at least $X$ grams is to have $X = 2$, and $P$ consists of a single 2g coin. Then we can conclude that $P$ weighs exactly $X$, and we are set.
timblack
2023-05-23 20:26:21
So, from this point on, we can take $k \geq 2$.
So, from this point on, we can take $k \geq 2$.
timblack
2023-05-23 20:26:46
Lots of ways to proceed. Here's one of my favorite.
Lots of ways to proceed. Here's one of my favorite.
timblack
2023-05-23 20:26:47
Make a pile of all the coins not in $P$, and add to this pile up to $k - 1$ coins from $P$ so that the pile has a multiple of $k$ coins. Partition this pile into sets $Q_1, Q_2, \dots, Q_\ell$.
Make a pile of all the coins not in $P$, and add to this pile up to $k - 1$ coins from $P$ so that the pile has a multiple of $k$ coins. Partition this pile into sets $Q_1, Q_2, \dots, Q_\ell$.
timblack
2023-05-23 20:27:12
Weigh each $Q_i$ on the broken scale. Let's say one of these $Q_i$ weighs "less than $X$ grams." What can we do?
Weigh each $Q_i$ on the broken scale. Let's say one of these $Q_i$ weighs "less than $X$ grams." What can we do?
shihan
2023-05-23 20:28:22
apply the lemma
apply the lemma
GryFry
2023-05-23 20:28:22
part a strategy
part a strategy
lpieleanu
2023-05-23 20:28:22
switch out coins until it has at least $X$
switch out coins until it has at least $X$
timblack
2023-05-23 20:28:29
Ooo maybe our lemma applies.
Ooo maybe our lemma applies.
timblack
2023-05-23 20:28:40
What are the sets we can use with the lemma?
What are the sets we can use with the lemma?
timblack
2023-05-23 20:29:29
We need a set that weighs at least $X$ grams, and another set of the same size that weighs less than $X$ grams...
We need a set that weighs at least $X$ grams, and another set of the same size that weighs less than $X$ grams...
NoahLeaf
2023-05-23 20:29:46
We have to get $Q_i$ to have exactly k coins, not just a multiple
We have to get $Q_i$ to have exactly k coins, not just a multiple
timblack
2023-05-23 20:30:06
Each $Q_i$ has size exactly $k$. Put together their size is a multiple of $k$.
Each $Q_i$ has size exactly $k$. Put together their size is a multiple of $k$.
Chameleon07
2023-05-23 20:30:32
P and the Qi?
P and the Qi?
ThousandthStar
2023-05-23 20:30:32
$S=Q_i$, $T=P$
$S=Q_i$, $T=P$
Curious_Droid
2023-05-23 20:30:32
so just P and that Q_i
so just P and that Q_i
timblack
2023-05-23 20:30:52
Yes, nice! We have a pile $Q_i$ weighing "less than $X$ grams," and a pile $P$ with the same number of coins weighing "at least $X$ grams." So, we can find a set weighing exactly $X$ grams using our lemma with $S = Q_i$ and $T = P$!
Yes, nice! We have a pile $Q_i$ weighing "less than $X$ grams," and a pile $P$ with the same number of coins weighing "at least $X$ grams." So, we can find a set weighing exactly $X$ grams using our lemma with $S = Q_i$ and $T = P$!
Shivasaurus
2023-05-23 20:31:15
ohhhh
ohhhh
lrjr24
2023-05-23 20:31:17
wait why can't you go from X-1 to X+1 in this lemma and skip over a set that weighs exactly X grams
wait why can't you go from X-1 to X+1 in this lemma and skip over a set that weighs exactly X grams
timblack
2023-05-23 20:32:07
If we just removed a coin, could change weight by 1g or 2g. But since we replace the coin, the difference between two coins is only at most 1g (if one is a 1g coin and the other is a 2g coin).
If we just removed a coin, could change weight by 1g or 2g. But since we replace the coin, the difference between two coins is only at most 1g (if one is a 1g coin and the other is a 2g coin).
timblack
2023-05-23 20:32:16
So now there's only one remaining sticking point: We just need to handle the situation where every $Q_i$ weighs "at least $X$ grams."
So now there's only one remaining sticking point: We just need to handle the situation where every $Q_i$ weighs "at least $X$ grams."
timblack
2023-05-23 20:32:36
I claim that in this situation, $P$ contains at least one 1g coin. Two questions:
1. Why is this true?
2. Why do I care?
Let's start with question 2: Why is it helpful to know that $P$ contains a 1g coin?
I claim that in this situation, $P$ contains at least one 1g coin. Two questions:
1. Why is this true?
2. Why do I care?
Let's start with question 2: Why is it helpful to know that $P$ contains a 1g coin?
ThousandthStar
2023-05-23 20:33:48
If $P$ has a 1g coin, we can do the same as with case 1
If $P$ has a 1g coin, we can do the same as with case 1
vrondoS
2023-05-23 20:33:48
then we can remove each coin one at a time
then we can remove each coin one at a time
timblack
2023-05-23 20:33:55
Exactly. We can use the same trick as in part 1: We weigh $P$ minus one coin for each coin in $P$. Either one of these weighings gives "at least $X$ grams" which we saw implies exactly $X$ grams, or all of the weighings give "less than $X$ grams," which we saw implies that $P$ minus 1g weighs less than $X$ grams which further implies $P$ weighs exactly $X$ grams.
Exactly. We can use the same trick as in part 1: We weigh $P$ minus one coin for each coin in $P$. Either one of these weighings gives "at least $X$ grams" which we saw implies exactly $X$ grams, or all of the weighings give "less than $X$ grams," which we saw implies that $P$ minus 1g weighs less than $X$ grams which further implies $P$ weighs exactly $X$ grams.
timblack
2023-05-23 20:34:22
Which brings us back to question 1: If all the $Q_i$ weigh "at least $X$ grams," why does that imply that $P$ contains a 1g coin? We'll proceed by contradiction.
Which brings us back to question 1: If all the $Q_i$ weigh "at least $X$ grams," why does that imply that $P$ contains a 1g coin? We'll proceed by contradiction.
timblack
2023-05-23 20:34:32
Suppose that $P$ consisted entirely of 2g coins. Then, each $Q_i$ has at most one 1g coin: if it had two or more 1g coins, then it would weigh at least 2g less than $P$, so would weigh at most $X + 1 - 2 = X - 1$ grams, but we know that $Q_i$ weighs "at least $X$ grams."
Suppose that $P$ consisted entirely of 2g coins. Then, each $Q_i$ has at most one 1g coin: if it had two or more 1g coins, then it would weigh at least 2g less than $P$, so would weigh at most $X + 1 - 2 = X - 1$ grams, but we know that $Q_i$ weighs "at least $X$ grams."
Shivasaurus
2023-05-23 20:34:57
and X-1 is not at least X
and X-1 is not at least X
timblack
2023-05-23 20:35:02
Exactly.
Exactly.
timblack
2023-05-23 20:35:03
So, each $Q_i$ has at most one 1g coin, so all the $Q_i$ together contain at most $\ell$ coins of 1g, where $\ell < \frac{4046}{k} \leq \frac{4046}{2} = 2023$ coins of 1g. Do you see the contradiction?
So, each $Q_i$ has at most one 1g coin, so all the $Q_i$ together contain at most $\ell$ coins of 1g, where $\ell < \frac{4046}{k} \leq \frac{4046}{2} = 2023$ coins of 1g. Do you see the contradiction?
timblack
2023-05-23 20:35:49
We're assuming $P$ doesn't contain any 1g coins, so all the $Q_i$ together contain all $2023$ coins of 1g. So the $Q_i$ all together must simultaneously contain less than $2023$ and exactly $2023$ coins of one gram. Contradiction!
We're assuming $P$ doesn't contain any 1g coins, so all the $Q_i$ together contain all $2023$ coins of 1g. So the $Q_i$ all together must simultaneously contain less than $2023$ and exactly $2023$ coins of one gram. Contradiction!
timblack
2023-05-23 20:36:03
So, our assumption was false: $P$ must contain at least one 1g coin when every $Q_i$ weighs "at least $X$ grams."
So, our assumption was false: $P$ must contain at least one 1g coin when every $Q_i$ weighs "at least $X$ grams."
timblack
2023-05-23 20:36:19
That's how we find a set of weigh exactly $X$ in case 2. How many weighings does this take?
That's how we find a set of weigh exactly $X$ in case 2. How many weighings does this take?
timblack
2023-05-23 20:36:27
- It takes $k \leq 2023$ weighings to find $P$.
- It takes $\ell < \frac{4046}{k} \leq \frac{4046}{2} = 2023$ weighings to weigh each $Q_i$.
- It takes $k \leq 2023$ to weigh $P$ one coin for each coin in turn.
So, the total number of weighings is at most $2023 + 2023 + 2023 = 6069 < 10000$.
- It takes $k \leq 2023$ weighings to find $P$.
- It takes $\ell < \frac{4046}{k} \leq \frac{4046}{2} = 2023$ weighings to weigh each $Q_i$.
- It takes $k \leq 2023$ to weigh $P$ one coin for each coin in turn.
So, the total number of weighings is at most $2023 + 2023 + 2023 = 6069 < 10000$.
timblack
2023-05-23 20:36:46
So we're done with case 2, and thus with the problem!
So we're done with case 2, and thus with the problem!
timblack
2023-05-23 20:36:50
timblack
2023-05-23 20:36:56
The problem only asks you to use less than 10000 weighings. But if you wanted to use even fewer weighings, there are a few things you can do. Any ideas?
The problem only asks you to use less than 10000 weighings. But if you wanted to use even fewer weighings, there are a few things you can do. Any ideas?
NoahLeaf
2023-05-23 20:37:01
yay!
yay!
Curious_Droid
2023-05-23 20:37:01
beautiful
beautiful
Curious_Droid
2023-05-23 20:37:16
binary search?
binary search?
rithek.shankar
2023-05-23 20:37:16
binary search
binary search
GryFry
2023-05-23 20:37:16
binary search
binary search
ThousandthStar
2023-05-23 20:37:21
A sort of binary search to find $P$
A sort of binary search to find $P$
timblack
2023-05-23 20:37:28
Good idea! For the first step where you find $P$, instead of adding coins one at a time, you can use a "binary search." Line up all $4046$ coins in a row, and let $C_i$ be the set consisting of the first $i$ coins. We want to find the magic number $k$ such that $C_k = P$ weighs "at least $X$ grams," while $C_{k - 1}$ weighs "less than $X$ grams."
Good idea! For the first step where you find $P$, instead of adding coins one at a time, you can use a "binary search." Line up all $4046$ coins in a row, and let $C_i$ be the set consisting of the first $i$ coins. We want to find the magic number $k$ such that $C_k = P$ weighs "at least $X$ grams," while $C_{k - 1}$ weighs "less than $X$ grams."
timblack
2023-05-23 20:37:43
What we did before was to weigh $C_1$, then $C_2$, then $C_3$, and so on, until we finally got to $k$. We can do this instead: We know our magic $k$ is somwhere between $1$ and $4046$ inclusive. Start right in the middle: weigh $C_{2023}$. If you get "at least $X$", that means lets you narrow down the range of $k$ to somewhere between $1$ and $2023$ inclusive, so you should next try right in the middle of that: weigh $C_{1012}$ next. If you instead are told that $C_{2023}$ weighs "less than X," that tells you that $k$ is somewhere between $2024$ and $4046$, so you should next try the middle of that range: weigh $C_{3035}$ next.
What we did before was to weigh $C_1$, then $C_2$, then $C_3$, and so on, until we finally got to $k$. We can do this instead: We know our magic $k$ is somwhere between $1$ and $4046$ inclusive. Start right in the middle: weigh $C_{2023}$. If you get "at least $X$", that means lets you narrow down the range of $k$ to somewhere between $1$ and $2023$ inclusive, so you should next try right in the middle of that: weigh $C_{1012}$ next. If you instead are told that $C_{2023}$ weighs "less than X," that tells you that $k$ is somewhere between $2024$ and $4046$, so you should next try the middle of that range: weigh $C_{3035}$ next.
timblack
2023-05-23 20:38:00
With each weighing, you can narrow down the range of possible $k$ by half. If you cut the original range of size $4046$ in half just $12$ times, you can get down to just a single remaining possiblity for $k$. Thus, you can find $k$ in just $12$ weighings instead of $4046$ weighings.
With each weighing, you can narrow down the range of possible $k$ by half. If you cut the original range of size $4046$ in half just $12$ times, you can get down to just a single remaining possiblity for $k$. Thus, you can find $k$ in just $12$ weighings instead of $4046$ weighings.
timblack
2023-05-23 20:38:16
Anything else you can do to use fewer weighings?
Anything else you can do to use fewer weighings?
wilsonstmartin
2023-05-23 20:39:08
Do you need to test 4046 coins? Is 2024 enough?
Do you need to test 4046 coins? Is 2024 enough?
timblack
2023-05-23 20:39:17
Nice! In case 1, for the second step where you weigh $P$ minus a coin, you don't have to try every coin in $P$. Once you've tried $2024$ coins, you know that at least one of the coins you tried weighs 1g, so you can stop there with only $2024$ weighings for that step instead of up to $4046$.
Nice! In case 1, for the second step where you weigh $P$ minus a coin, you don't have to try every coin in $P$. Once you've tried $2024$ coins, you know that at least one of the coins you tried weighs 1g, so you can stop there with only $2024$ weighings for that step instead of up to $4046$.
timblack
2023-05-23 20:39:36
I've thought a bit more about this problem, and I believe that if you take care in a few more places, you can get the number of weighings all the way down to $2026$. But also, $2026$ is the minimum; I believe it is impossible to reliably find a set of weight exactly $X$ in $2025$ weighings. But I haven't written up my solution; feel free to try it for yourself!
I've thought a bit more about this problem, and I believe that if you take care in a few more places, you can get the number of weighings all the way down to $2026$. But also, $2026$ is the minimum; I believe it is impossible to reliably find a set of weight exactly $X$ in $2025$ weighings. But I haven't written up my solution; feel free to try it for yourself!
timblack
2023-05-23 20:40:01
That concludes problem 3!
That concludes problem 3!
ThousandthStar
2023-05-23 20:40:11
Solocraftsolo
2023-05-23 20:40:11
Horray!
Horray!
VanuTalin
2023-05-23 20:40:31
I am ecstatic for Queston 4!!
I am ecstatic for Queston 4!!
rithek.shankar
2023-05-23 20:40:31
Problem 4 is weird
Problem 4 is weird
VanuTalin
2023-05-23 20:40:31
Number 4 Looks fun!
Number 4 Looks fun!
timblack
2023-05-23 20:40:33
Excellent, on that note, Dan is going to take over to talk about problems 4 through 6!
Excellent, on that note, Dan is going to take over to talk about problems 4 through 6!
dgulotta
2023-05-23 20:40:57
Hi everyone!
Hi everyone!
dgulotta
2023-05-23 20:41:51
4. You are exploring the maze below. The red and blue doors are locked, but you know that there is a Red Key in a treasure chest in one of the rooms, and a Blue Key in a different treasure chest. Once you have the Red Key, you can open all of the red doors. Likewise, once you have the Blue Key, you can open all of the blue doors.
4. You are exploring the maze below. The red and blue doors are locked, but you know that there is a Red Key in a treasure chest in one of the rooms, and a Blue Key in a different treasure chest. Once you have the Red Key, you can open all of the red doors. Likewise, once you have the Blue Key, you can open all of the blue doors.
dgulotta
2023-05-23 20:42:15
(a) If I chose two random treasure chests to put the keys in, most likely you will not be able to get to them. Suppose I choose randomly from only the valid assignments: those in which you can get to all of the treasure chests. What is the probability that the Red Key will be in the first treasure chest you open?
(a) If I chose two random treasure chests to put the keys in, most likely you will not be able to get to them. Suppose I choose randomly from only the valid assignments: those in which you can get to all of the treasure chests. What is the probability that the Red Key will be in the first treasure chest you open?
dgulotta
2023-05-23 20:42:31
We'd like to enumerate all of the valid assignments - how would you do that?
We'd like to enumerate all of the valid assignments - how would you do that?
AoPSyang
2023-05-23 20:43:47
case work
case work
impromptuA
2023-05-23 20:43:47
there are 2 cases, if the red key is in the first room or if it's in the room behind the blue door (1 room away from the first room)
there are 2 cases, if the red key is in the first room or if it's in the room behind the blue door (1 room away from the first room)
timchen
2023-05-23 20:43:47
Three cases, depending on what keys are in the first room?
Three cases, depending on what keys are in the first room?
GryFry
2023-05-23 20:43:47
case 1: open red door first, case 2: open blue door first
case 1: open red door first, case 2: open blue door first
dgulotta
2023-05-23 20:44:37
At least one of the keys has to be in the starting room.
At least one of the keys has to be in the starting room.
dgulotta
2023-05-23 20:44:57
So they can both be in the starting room, or the red one can be behind the blue door, or the blue one can be behind the red door.
So they can both be in the starting room, or the red one can be behind the blue door, or the blue one can be behind the red door.
dgulotta
2023-05-23 20:45:52
There are $3 \cdot 2 = 6$ ways of putting both keys in the starting room, $3 \cdot 3 = 9$ ways of putting the red key in the starting room and the blue key in the room behind the red door, and $3 \cdot 2 = 6$ ways of putting the blue key in the starting room and the red key in the room behind the blue door.
There are $3 \cdot 2 = 6$ ways of putting both keys in the starting room, $3 \cdot 3 = 9$ ways of putting the red key in the starting room and the blue key in the room behind the red door, and $3 \cdot 2 = 6$ ways of putting the blue key in the starting room and the red key in the room behind the blue door.
dgulotta
2023-05-23 20:46:01
So the fraction of assignments that have the red key in the starting room is $(6+9)/(6+9+6) = 15/21 = 5/7$.
So the fraction of assignments that have the red key in the starting room is $(6+9)/(6+9+6) = 15/21 = 5/7$.
dgulotta
2023-05-23 20:46:31
If the red key is in the starting room, what is the probability that the chest with the red key is the first one you open?
If the red key is in the starting room, what is the probability that the chest with the red key is the first one you open?
ProCounter44
2023-05-23 20:46:55
1/3
1/3
Curious_Droid
2023-05-23 20:46:55
1/3
1/3
Rinnypig
2023-05-23 20:46:55
1/3
1/3
majix0418
2023-05-23 20:46:55
1/3
1/3
UnknownMonkey
2023-05-23 20:46:55
$\frac{1}{3}$
$\frac{1}{3}$
dgulotta
2023-05-23 20:47:08
Right.
Right.
rithek.shankar
2023-05-23 20:47:17
So 5/21
So 5/21
dgulotta
2023-05-23 20:47:42
So the overall chance of the red key being in the first chest opened is $5/7 \cdot 1/3 = 5/21$.
So the overall chance of the red key being in the first chest opened is $5/7 \cdot 1/3 = 5/21$.
Rinnypig
2023-05-23 20:48:08
Yay! Those aren't super great odds.
Yay! Those aren't super great odds.
wilsonstmartin
2023-05-23 20:48:48
Quick question: Is the only way for an assignment to be invalid is if it is behind a door of its own color?
Quick question: Is the only way for an assignment to be invalid is if it is behind a door of its own color?
dgulotta
2023-05-23 20:49:12
I think more complicated things could happen, but offhand I'm not 100% sure.
I think more complicated things could happen, but offhand I'm not 100% sure.
dgulotta
2023-05-23 20:49:27
So that's part (a
So that's part (a
winstonDeGreef
2023-05-23 20:49:55
no, there can be a chain where red is behind blue and blue behind red
no, there can be a chain where red is behind blue and blue behind red
Malinar
2023-05-23 20:49:55
You could have the blue key behind the red door, and the red key behind the blue door, and none in the starting room - that's an invalid assignment
You could have the blue key behind the red door, and the red key behind the blue door, and none in the starting room - that's an invalid assignment
dgulotta
2023-05-23 20:50:11
(b) Suppose I choose a random key, and put it in a random treasure chest that you can get to. Then I repeat with the other key, but allow it to be placed in any other treasure chest that you can get to after picking up the first key I placed. What is the probability that the Red Key will be in the first treasure chest you open?
(b) Suppose I choose a random key, and put it in a random treasure chest that you can get to. Then I repeat with the other key, but allow it to be placed in any other treasure chest that you can get to after picking up the first key I placed. What is the probability that the Red Key will be in the first treasure chest you open?
dgulotta
2023-05-23 20:50:34
If I place the red key first, I will have to place it in the starting room. If I place the blue key first, what is the probability that the red key will be placed in the starting room?
If I place the red key first, I will have to place it in the starting room. If I place the blue key first, what is the probability that the red key will be placed in the starting room?
oyc_1975
2023-05-23 20:51:14
1/2
1/2
Curious_Droid
2023-05-23 20:51:14
1/2
1/2
impromptuA
2023-05-23 20:51:14
1/2
1/2
Malinar
2023-05-23 20:51:14
1/2. There are four chests left, two in the starting room.
1/2. There are four chests left, two in the starting room.
dgulotta
2023-05-23 20:51:23
Right.
Right.
dgulotta
2023-05-23 20:51:38
So, overall, what is the probability of the red key being in the starting room?
So, overall, what is the probability of the red key being in the starting room?
timchen
2023-05-23 20:52:06
$\frac{3}{4}$
$\frac{3}{4}$
winstonDeGreef
2023-05-23 20:52:06
3/4
3/4
Malinar
2023-05-23 20:52:06
3/4
3/4
dgulotta
2023-05-23 20:52:18
I am equally likely to place the red or blue key first, so the overall probability of the red key being in the starting room is $1/2 \cdot (1 + 1/2) = 3/4$.
I am equally likely to place the red or blue key first, so the overall probability of the red key being in the starting room is $1/2 \cdot (1 + 1/2) = 3/4$.
dgulotta
2023-05-23 20:52:32
Then the probability of the red key being in the first chest opened is $3/4 \cdot 1/3 = 1/4$.
Then the probability of the red key being in the first chest opened is $3/4 \cdot 1/3 = 1/4$.
dgulotta
2023-05-23 20:53:16
So that is part (b).
So that is part (b).
dgulotta
2023-05-23 20:53:33
(c) The two methods from (a) and (b) give different probabilities, but they're very close together. Can you draw a different map in which the method of (a) gives a probability of picking up the Red Key from the first chest you open of less than 1\%, but the method of (b) gives a probability more than 99\%? Your map may have any number of doors, treasure chests, and colors — but no other types of obstacle, and only one key of each color.
(c) The two methods from (a) and (b) give different probabilities, but they're very close together. Can you draw a different map in which the method of (a) gives a probability of picking up the Red Key from the first chest you open of less than 1\%, but the method of (b) gives a probability more than 99\%? Your map may have any number of doors, treasure chests, and colors — but no other types of obstacle, and only one key of each color.
dgulotta
2023-05-23 20:53:43
(To generalize the method from (b), I place the keys in random order, and place the $k$th key in an empty treasure chest you can get to if you have the first $k-1$ keys. If all the treasure chests you can get to are full when I try to place the $k$th key, I take back all the keys placed and start over, once again randomly choosing an order for the keys.)
(To generalize the method from (b), I place the keys in random order, and place the $k$th key in an empty treasure chest you can get to if you have the first $k-1$ keys. If all the treasure chests you can get to are full when I try to place the $k$th key, I take back all the keys placed and start over, once again randomly choosing an order for the keys.)
dgulotta
2023-05-23 20:56:47
First, how might you design the maze so that it is very likely that the method in (b) results in the red key being in the first chest opened?
First, how might you design the maze so that it is very likely that the method in (b) results in the red key being in the first chest opened?
TheBeast5520
2023-05-23 20:58:22
Initial room has to have at most one treasure box. Otherwise probability is capped at 1/n for both methods (where there are n boxes)
Initial room has to have at most one treasure box. Otherwise probability is capped at 1/n for both methods (where there are n boxes)
Solocraftsolo
2023-05-23 20:58:32
1 treasure chest in the starting room
1 treasure chest in the starting room
wilsonstmartin
2023-05-23 20:59:45
Having a single chest in the first room, and the red key must be in the first room
Having a single chest in the first room, and the red key must be in the first room
oyc_1975
2023-05-23 20:59:45
forcing the first key placed to be red, and also having one chest in the starting room
forcing the first key placed to be red, and also having one chest in the starting room
timchen
2023-05-23 20:59:45
other doors have very few chests behind them
other doors have very few chests behind them
JigglypuffDaBest
2023-05-23 20:59:45
make it so that any method that doesn't have red as its first key be a method thats invalid
make it so that any method that doesn't have red as its first key be a method thats invalid
dgulotta
2023-05-23 20:59:55
There needs to be only one chest in the starting room. Furthermore, if I try to place a non-red key first, it needs to be very likely that I get stuck and have to start over.
There needs to be only one chest in the starting room. Furthermore, if I try to place a non-red key first, it needs to be very likely that I get stuck and have to start over.
dgulotta
2023-05-23 21:00:43
Can you come up with an example maze where the method of (b) gives a very high, but not quite 100%, chance of the red key being in the first chest opened?
Can you come up with an example maze where the method of (b) gives a very high, but not quite 100%, chance of the red key being in the first chest opened?
dgulotta
2023-05-23 21:00:57
(If the chance was 100%, then the method of (a) would also give 100%.)
(If the chance was 100%, then the method of (a) would also give 100%.)
dgulotta
2023-05-23 21:02:31
I can have the red door lead to a room with enough chests for all of the keys, and another door that leads to a room with only one chest. For example:
I can have the red door lead to a room with enough chests for all of the keys, and another door that leads to a room with only one chest. For example:
dgulotta
2023-05-23 21:02:50
If I place the red key first, what is the probability that I succeed in placing all of the keys?
If I place the red key first, what is the probability that I succeed in placing all of the keys?
MathFun1000
2023-05-23 21:03:20
$1$
$1$
oyc_1975
2023-05-23 21:03:20
1; it will always work
1; it will always work
dgulotta
2023-05-23 21:03:24
Right.
Right.
dgulotta
2023-05-23 21:03:43
If I place the blue key first, what is the probability?
If I place the blue key first, what is the probability?
timchen
2023-05-23 21:04:26
$\frac{1}{100}$
$\frac{1}{100}$
MathFun1000
2023-05-23 21:04:26
$\dfrac{1}{100}$
$\dfrac{1}{100}$
dgulotta
2023-05-23 21:04:36
$1/100$, since I succeed only if I place the red key second.
$1/100$, since I succeed only if I place the red key second.
dgulotta
2023-05-23 21:05:08
If I place another (not red or blue) key first, what is the probability?
If I place another (not red or blue) key first, what is the probability?
timchen
2023-05-23 21:05:22
0
0
TheBeast5520
2023-05-23 21:05:22
0
0
Chameleon07
2023-05-23 21:05:22
0
0
MathFun1000
2023-05-23 21:05:22
$0$
$0$
oyc_1975
2023-05-23 21:05:22
0; you can't place any other keys
0; you can't place any other keys
dgulotta
2023-05-23 21:05:26
Right.
Right.
dgulotta
2023-05-23 21:05:38
So what is the chance that, when I finally succeed in placing the keys, I place the red key in the starting room?
So what is the chance that, when I finally succeed in placing the keys, I place the red key in the starting room?
timchen
2023-05-23 21:06:20
$\frac{100}{101}$
$\frac{100}{101}$
impromptuA
2023-05-23 21:06:20
100/101
100/101
MathFun1000
2023-05-23 21:06:20
$\tfrac{100}{101}$
$\tfrac{100}{101}$
dgulotta
2023-05-23 21:06:33
$1/(1 + 1/100 + 99 \cdot 0) = 100/101$, which is greater than 99%
$1/(1 + 1/100 + 99 \cdot 0) = 100/101$, which is greater than 99%
dgulotta
2023-05-23 21:07:23
So we found a way to make it very likely that the method of part (b) will place the red key in the starting room. Now, we'd like to come up with a variation where most of the valid configurations do not place the red key in the starting room. Any ideas on how to do this?
So we found a way to make it very likely that the method of part (b) will place the red key in the starting room. Now, we'd like to come up with a variation where most of the valid configurations do not place the red key in the starting room. Any ideas on how to do this?
winstonDeGreef
2023-05-23 21:09:11
add another door to the room with one chest and put an enormous amount of chests behind it
add another door to the room with one chest and put an enormous amount of chests behind it
dgulotta
2023-05-23 21:09:26
If we have a room that can only be reached using all of the non-red keys, then only the red key can be in that room. If the room is sufficiently huge, then most of the valid assignments will have the red key in that room.
If we have a room that can only be reached using all of the non-red keys, then only the red key can be in that room. If the room is sufficiently huge, then most of the valid assignments will have the red key in that room.
dgulotta
2023-05-23 21:09:46
Here is an example:
Here is an example:
dgulotta
2023-05-23 21:10:15
First, let's check that the method of part (b) still places the red key in the starting room more than 99% of the time.
First, let's check that the method of part (b) still places the red key in the starting room more than 99% of the time.
dgulotta
2023-05-23 21:12:03
If the first key placed is red, then I'm still guaranteed to be able to place all of the keys, and if it's not red or blue, then I still get stuck right away. If it's blue, what is the probability that I succeed in placing all of the keys?
If the first key placed is red, then I'm still guaranteed to be able to place all of the keys, and if it's not red or blue, then I still get stuck right away. If it's blue, what is the probability that I succeed in placing all of the keys?
MathFun1000
2023-05-23 21:12:47
$\tfrac{2}{199}$
$\tfrac{2}{199}$
dgulotta
2023-05-23 21:12:52
$2/199$, since I succeed only if I place the red or silver key second.
$2/199$, since I succeed only if I place the red or silver key second.
dgulotta
2023-05-23 21:13:20
So the chance that the method of part (b) places the red key in the starting room is $1/(1+2/199+198\cdot 0) = 199/201$.
So the chance that the method of part (b) places the red key in the starting room is $1/(1+2/199+198\cdot 0) = 199/201$.
dgulotta
2023-05-23 21:13:37
Now for the method of part (a). What is an upper bound for the number of valid configurations with the red key in the starting room?
Now for the method of part (a). What is an upper bound for the number of valid configurations with the red key in the starting room?
dgulotta
2023-05-23 21:15:16
If the red key is placed in the starting room, then there are $199+1+197=397$ possible spots for the remaining $199$ keys. So the number of ways of placing the remaining keys is at most ${}_{397}P_{199}=\frac{397!}{198!}$.
If the red key is placed in the starting room, then there are $199+1+197=397$ possible spots for the remaining $199$ keys. So the number of ways of placing the remaining keys is at most ${}_{397}P_{199}=\frac{397!}{198!}$.
dgulotta
2023-05-23 21:16:04
How many valid configurations have the red key in the rightmost room?
How many valid configurations have the red key in the rightmost room?
dgulotta
2023-05-23 21:16:54
There are $\frac{399!}{198!}$ places for the red key, and $197!$ ways to arrange the remaining keys. So there are $\frac{399!}{198!} \cdot 197!$ configurations that have the red key in the rightmost room.
There are $\frac{399!}{198!}$ places for the red key, and $197!$ ways to arrange the remaining keys. So there are $\frac{399!}{198!} \cdot 197!$ configurations that have the red key in the rightmost room.
dgulotta
2023-05-23 21:18:22
So there are at least 197! times more configurations with the red key in the rightmost room than in the starting room.
So there are at least 197! times more configurations with the red key in the rightmost room than in the starting room.
dgulotta
2023-05-23 21:18:43
And $1/(1+197!)$ is a lot less than 1%.
And $1/(1+197!)$ is a lot less than 1%.
winstonDeGreef
2023-05-23 21:19:19
does |199 chests |red door| start, 1 chest | blue door | 1 chest | grey door| 4 000 000 chests| also work? (again with 200 key colors)
does |199 chests |red door| start, 1 chest | blue door | 1 chest | grey door| 4 000 000 chests| also work? (again with 200 key colors)
dgulotta
2023-05-23 21:20:50
Hmm, I don't know offhand. That configuration allows the other 197 colors in the large room so it's a different calculation.
Hmm, I don't know offhand. That configuration allows the other 197 colors in the large room so it's a different calculation.
JigglypuffDaBest
2023-05-23 21:20:54
can you clarify "1/(1 + 2/199 + 198 * 0)" more? I'm confused how the probabilities from selecting each key ended up in the denominator. . .
can you clarify "1/(1 + 2/199 + 198 * 0)" more? I'm confused how the probabilities from selecting each key ended up in the denominator. . .
dgulotta
2023-05-23 21:22:32
Let's say I attempted to place the keys 200*199 times. I'd expect to attempt to place the red key first 199 times, blue key first 199 times, etc.
Let's say I attempted to place the keys 200*199 times. I'd expect to attempt to place the red key first 199 times, blue key first 199 times, etc.
dgulotta
2023-05-23 21:22:50
The 199 times with the red key all succeed.
The 199 times with the red key all succeed.
dgulotta
2023-05-23 21:23:01
I only expect to succeed twice with the blue key.
I only expect to succeed twice with the blue key.
dgulotta
2023-05-23 21:23:06
I never succeed with the other keys.
I never succeed with the other keys.
dgulotta
2023-05-23 21:23:31
So I expect to get 201 successes, 199 of which have the red key in the starting room.
So I expect to get 201 successes, 199 of which have the red key in the starting room.
dgulotta
2023-05-23 21:24:18
$1/(1 + 2/199 + 198 * 0)$ is essentially the same calculation, just with the numerator and denominator divided by 200*199.
$1/(1 + 2/199 + 198 * 0)$ is essentially the same calculation, just with the numerator and denominator divided by 200*199.
dgulotta
2023-05-23 21:24:21
Does that make sense?
Does that make sense?
dgulotta
2023-05-23 21:25:36
Anyway, we have shown that this map is a valid solution to 4c. I'll pause for a bit in case there are any other questions or comments.
Anyway, we have shown that this map is a valid solution to 4c. I'll pause for a bit in case there are any other questions or comments.
dgulotta
2023-05-23 21:28:06
5. Narmada and Travis are playing a game in turns; Narmada goes first. Each player stands on their own number line, which has spaces numbered $1$ through $n$ for some integer $n \ge 3$. Narmada starts at position 1 on her number line, and Travis starts at position n on his. On each player's turn, that player must move to another number on their number line. (The new number need not be adjacent to the old one.) But no repetitions are allowed in the pair of positions: if Narmada moves back to position $1$, then Travis cannot move back to position $n$ on his next move, because the ordered pair $(1,n)$ has already occurred. The first player who cannot move loses. Assume both players play optimally.
5. Narmada and Travis are playing a game in turns; Narmada goes first. Each player stands on their own number line, which has spaces numbered $1$ through $n$ for some integer $n \ge 3$. Narmada starts at position 1 on her number line, and Travis starts at position n on his. On each player's turn, that player must move to another number on their number line. (The new number need not be adjacent to the old one.) But no repetitions are allowed in the pair of positions: if Narmada moves back to position $1$, then Travis cannot move back to position $n$ on his next move, because the ordered pair $(1,n)$ has already occurred. The first player who cannot move loses. Assume both players play optimally.
dgulotta
2023-05-23 21:28:15
(a) For each $n$, who wins?
(a) For each $n$, who wins?
dgulotta
2023-05-23 21:28:54
This is a problem where trial and error is useful. I assume many of you have played the game - what did you find?
This is a problem where trial and error is useful. I assume many of you have played the game - what did you find?
JigglypuffDaBest
2023-05-23 21:30:04
narmada wins for a
narmada wins for a
rithek.shankar
2023-05-23 21:30:04
Narmada always won
Narmada always won
winstonDeGreef
2023-05-23 21:30:04
narmada can keep moving between 1 and 2 and always have a number to go to
narmada can keep moving between 1 and 2 and always have a number to go to
dgulotta
2023-05-23 21:30:27
Narmada can win by moving back and forth between $1$ and $2$.
Narmada can win by moving back and forth between $1$ and $2$.
dgulotta
2023-05-23 21:30:37
Whenever Travis moves to a position $T$, Narmada's next move guarantees that $(1,T)$ and $(2,T)$ are both taken, so Travis never gets an opportunity to move back to $T$. He has to move to a different number each time, and eventually runs out of numbers.
Whenever Travis moves to a position $T$, Narmada's next move guarantees that $(1,T)$ and $(2,T)$ are both taken, so Travis never gets an opportunity to move back to $T$. He has to move to a different number each time, and eventually runs out of numbers.
rithek.shankar
2023-05-23 21:30:52
Could we visualize this on the coordinate plane with Narmada as the x-axis and Travis on the y-axis?
Could we visualize this on the coordinate plane with Narmada as the x-axis and Travis on the y-axis?
Rinnypig
2023-05-23 21:30:52
It is also really helpful to graph this process.
It is also really helpful to graph this process.
dgulotta
2023-05-23 21:31:16
That's a good point! I'll use some graphs in part c.
That's a good point! I'll use some graphs in part c.
dgulotta
2023-05-23 21:31:52
(b) Now suppose they are on the same number line, and cannot simultaneously occupy the same spot. (So if Narmada is at $1$ and Travis is at $3$, Narmada can move to $2, 4, 5, \dotsc, n$ but not $1$ or $3$.) Furthermore, a position is considered the same if the same spots are occupied (so $N=1$, $T=3$ is a repetition of $N=3$, $T=1$). For each $n$, who wins?
(b) Now suppose they are on the same number line, and cannot simultaneously occupy the same spot. (So if Narmada is at $1$ and Travis is at $3$, Narmada can move to $2, 4, 5, \dotsc, n$ but not $1$ or $3$.) Furthermore, a position is considered the same if the same spots are occupied (so $N=1$, $T=3$ is a repetition of $N=3$, $T=1$). For each $n$, who wins?
dgulotta
2023-05-23 21:32:12
Is the strategy from part (a) helpful here?
Is the strategy from part (a) helpful here?
Rinnypig
2023-05-23 21:33:00
Yes it is!
Yes it is!
rithek.shankar
2023-05-23 21:33:00
Yes, but for Travis
Yes, but for Travis
timchen
2023-05-23 21:33:00
kind of, Travis wins because he can cycle back and forth from the bottom to the top
kind of, Travis wins because he can cycle back and forth from the bottom to the top
dgulotta
2023-05-23 21:33:16
Now Travis can win by moving back and forth between $n$ and $1$. Narmada can't block him by moving to $1$ or $n$ since $(1,n)$ is already taken. Whenever Narmada moves to a new position $N$, Travis guarantees that $(N,1)$ and $(N,n)$ are both taken, so Narmada can never move back to $N$. She has to move to a new number each time, and eventually runs out of numbers.
Now Travis can win by moving back and forth between $n$ and $1$. Narmada can't block him by moving to $1$ or $n$ since $(1,n)$ is already taken. Whenever Narmada moves to a new position $N$, Travis guarantees that $(N,1)$ and $(N,n)$ are both taken, so Narmada can never move back to $N$. She has to move to a new number each time, and eventually runs out of numbers.
dgulotta
2023-05-23 21:34:08
So that solves part (b).
So that solves part (b).
dgulotta
2023-05-23 21:34:21
(c) Same as (b), but the players are considered distinct (so $N=1$, $T=3$ isn't a repetition of $N=3$, $T=1$).
(c) Same as (b), but the players are considered distinct (so $N=1$, $T=3$ isn't a repetition of $N=3$, $T=1$).
dgulotta
2023-05-23 21:34:38
If you have played a lot of games, you probably noticed something. What jumped out at you?
If you have played a lot of games, you probably noticed something. What jumped out at you?
winstonDeGreef
2023-05-23 21:36:32
for odd n narmada wins
for odd n narmada wins
dgulotta
2023-05-23 21:36:41
I'm looking for something slightly more specific.
I'm looking for something slightly more specific.
dgulotta
2023-05-23 21:38:50
Not only does Narmada have a winning strategy, it turns out that *any* strategy is a winning strategy for Narmada! If you run a bunch of simulations with random moves, you will see that she wins every time.
Not only does Narmada have a winning strategy, it turns out that *any* strategy is a winning strategy for Narmada! If you run a bunch of simulations with random moves, you will see that she wins every time.
dgulotta
2023-05-23 21:39:01
(for odd n)
(for odd n)
dgulotta
2023-05-23 21:39:58
To figure out why Narmada always wins, it's helpful to look at a game more closely. Here is a sample game, shown move-by-move. The $N$ or $T$ in the grid represents the current position ($N$ if it's Narmada's turn, $T$ if it's Travis's). The circles represent positions that have not occurred yet. On Narmada's turn, she moves to a new position in the same row, and on Travis's turn, he moves to a new position in the same column.
To figure out why Narmada always wins, it's helpful to look at a game more closely. Here is a sample game, shown move-by-move. The $N$ or $T$ in the grid represents the current position ($N$ if it's Narmada's turn, $T$ if it's Travis's). The circles represent positions that have not occurred yet. On Narmada's turn, she moves to a new position in the same row, and on Travis's turn, he moves to a new position in the same column.
dgulotta
2023-05-23 21:40:09
MathFun1000
2023-05-23 21:40:41
parity matters
parity matters
Curious_Droid
2023-05-23 21:40:41
narmada has an odd number of squares she can go to at any time, so she can never have 0 squares left to move to
narmada has an odd number of squares she can go to at any time, so she can never have 0 squares left to move to
dgulotta
2023-05-23 21:41:02
Yes, Narmada always has an odd number of available moves.
Yes, Narmada always has an odd number of available moves.
dgulotta
2023-05-23 21:41:16
We'd like to come up with a statement that we can prove by induction, that explains why Narmada always wins. It certainly
seems important that Narmada has an odd number of available moves, but we can't quite use that as an induction hypothesis.
We need to find a stronger statement. Do you notice anything else?
We'd like to come up with a statement that we can prove by induction, that explains why Narmada always wins. It certainly
seems important that Narmada has an odd number of available moves, but we can't quite use that as an induction hypothesis.
We need to find a stronger statement. Do you notice anything else?
dgulotta
2023-05-23 21:41:28
Here are the counts of the number of unused positions in each row.
Here are the counts of the number of unused positions in each row.
dgulotta
2023-05-23 21:41:38
Curious_Droid
2023-05-23 21:43:34
the number of unused positions in every row is even when it is travis' turn?
the number of unused positions in every row is even when it is travis' turn?
dgulotta
2023-05-23 21:43:45
Yes. And when it's Narmada's turn?
Yes. And when it's Narmada's turn?
Curious_Droid
2023-05-23 21:44:20
only the row that she is in has an odd number of unused squares
only the row that she is in has an odd number of unused squares
dgulotta
2023-05-23 21:44:26
Right.
Right.
dgulotta
2023-05-23 21:44:38
The counts are even, except that when it's Narmada's turn, the row containing the current position has an odd number of dots.
The counts are even, except that when it's Narmada's turn, the row containing the current position has an odd number of dots.
dgulotta
2023-05-23 21:44:52
This is something that can be proved by induction.
This is something that can be proved by induction.
dgulotta
2023-05-23 21:45:40
And in particular, that implies that Narmada always has an odd number of moves, so she can't lose.
And in particular, that implies that Narmada always has an odd number of moves, so she can't lose.
dgulotta
2023-05-23 21:47:16
So that solves the odd case.
So that solves the odd case.
dgulotta
2023-05-23 21:47:24
Now let's turn our attention to $n$ even. It turns out that if the players play randomly, then either player can win, but Travis seems to win more often.
Now let's turn our attention to $n$ even. It turns out that if the players play randomly, then either player can win, but Travis seems to win more often.
dgulotta
2023-05-23 21:47:39
Here are two games for $n=4$.
In the first game, Travis wins:
Here are two games for $n=4$.
In the first game, Travis wins:
dgulotta
2023-05-23 21:47:51
dgulotta
2023-05-23 21:48:09
In the second, Narmada wins:
In the second, Narmada wins:
dgulotta
2023-05-23 21:48:22
dgulotta
2023-05-23 21:49:03
What do you notice?
What do you notice?
rithek.shankar
2023-05-23 21:51:06
Travis didn't need to lose the second one
Travis didn't need to lose the second one
rithek.shankar
2023-05-23 21:51:06
He could have moved to 2 instead of 1 on the middle right box.
He could have moved to 2 instead of 1 on the middle right box.
dgulotta
2023-05-23 21:52:11
We see a pattern similar to the one that we saw in the even case. But there's something weird about position $1$. And moving to position $1$ seems to have cost Travis the game shown above. So what should he do?
We see a pattern similar to the one that we saw in the even case. But there's something weird about position $1$. And moving to position $1$ seems to have cost Travis the game shown above. So what should he do?
JigglypuffDaBest
2023-05-23 21:53:26
he should never move to position 1 because that line is different from others; it had a point already filled out
he should never move to position 1 because that line is different from others; it had a point already filled out
dgulotta
2023-05-23 21:53:42
If Travis forgets that he's allowed to move to $1$, here's what the first game looks like:
If Travis forgets that he's allowed to move to $1$, here's what the first game looks like:
dgulotta
2023-05-23 21:53:55
dgulotta
2023-05-23 21:54:16
It's the same pattern as before. The count in each column is even, except that when it's Travis's turn, the column containing the current position has an odd number of dots. We can prove by induction that this observation always holds.
It's the same pattern as before. The count in each column is even, except that when it's Travis's turn, the column containing the current position has an odd number of dots. We can prove by induction that this observation always holds.
dgulotta
2023-05-23 21:54:41
In particular, if Travis forbids himself from moving to $1$, then he always has an odd number of moves available, so he can't lose.
In particular, if Travis forbids himself from moving to $1$, then he always has an odd number of moves available, so he can't lose.
dgulotta
2023-05-23 21:55:40
So we have proved that Narmada wins when $n$ is odd, and Travis wins when $n$ is even.
So we have proved that Narmada wins when $n$ is odd, and Travis wins when $n$ is even.
dgulotta
2023-05-23 21:56:33
Incidentally, a parity argument also works for part (a). If Narmada chooses a subset of $\{1,2,\dotsc,n\}$ of even size and only allows herself to move within that subset, then she always has an odd number of available moves. The strategy that we gave above is just the special case of the subset $\{1,2\}$.
Incidentally, a parity argument also works for part (a). If Narmada chooses a subset of $\{1,2,\dotsc,n\}$ of even size and only allows herself to move within that subset, then she always has an odd number of available moves. The strategy that we gave above is just the special case of the subset $\{1,2\}$.
dgulotta
2023-05-23 21:57:33
So that's problem 5. I'll pause for a bit before moving on to problem 6.
So that's problem 5. I'll pause for a bit before moving on to problem 6.
dgulotta
2023-05-23 21:59:29
Problem 6: The first quadrant is lava. The rest of the plane (including the $x$ and $y$ axes) is safe. To traverse the lava, you can place a board, which is a line segment of length at most $1$, between two safe endpoints. Once a board is placed, the line segment becomes safe, and points on it may be used as endpoints of a subsequent board. Your goal is to reach the point $(2023, 2023)$.
Problem 6: The first quadrant is lava. The rest of the plane (including the $x$ and $y$ axes) is safe. To traverse the lava, you can place a board, which is a line segment of length at most $1$, between two safe endpoints. Once a board is placed, the line segment becomes safe, and points on it may be used as endpoints of a subsequent board. Your goal is to reach the point $(2023, 2023)$.
dgulotta
2023-05-23 21:59:53
(a) Prove that one million boards aren't enough.
(a) Prove that one million boards aren't enough.
dgulotta
2023-05-23 22:00:13
One way to approach this problem is to find a quantity that changes by only a small amount each time you place a board, but needs to change by a large amount in order for $(2023, 2023)$ to be reached. Can you think of such a quantity?
One way to approach this problem is to find a quantity that changes by only a small amount each time you place a board, but needs to change by a large amount in order for $(2023, 2023)$ to be reached. Can you think of such a quantity?
iamhungry
2023-05-23 22:01:00
Area
Area
timchen
2023-05-23 22:01:00
The area under the curve.
The area under the curve.
impromptuA
2023-05-23 22:01:00
the area of the region surrounded by boards and the x and y axes?
the area of the region surrounded by boards and the x and y axes?
dgulotta
2023-05-23 22:01:25
Yes, it turns out that area is such a quantity.
Yes, it turns out that area is such a quantity.
dgulotta
2023-05-23 22:02:03
So are $\max(xy)$ and the minimum distance squared to (2023,2023). But I'll focus on area, because that is useful for part (c).
So are $\max(xy)$ and the minimum distance squared to (2023,2023). But I'll focus on area, because that is useful for part (c).
rithek.shankar
2023-05-23 22:02:46
what is max(x,y)
what is max(x,y)
dgulotta
2023-05-23 22:03:10
By $max(xy)$, I just mean the largest value of $xy$ among all points on boards.
By $max(xy)$, I just mean the largest value of $xy$ among all points on boards.
dgulotta
2023-05-23 22:03:51
Anyway, I should say exactly what I mean by area.
There is an infinite region of lava. When we place a board, it may cut off some lava from the infinite region. We measure the area of the lava cut off from the infinite region.
Anyway, I should say exactly what I mean by area.
There is an infinite region of lava. When we place a board, it may cut off some lava from the infinite region. We measure the area of the lava cut off from the infinite region.
dgulotta
2023-05-23 22:05:02
In order to bound the area, we first need to make an observation. Does anything stand out to you?
In order to bound the area, we first need to make an observation. Does anything stand out to you?
timchen
2023-05-23 22:07:08
We need to reach the square from $(0,0)$ to $(2023,2023)$ to get to that point
We need to reach the square from $(0,0)$ to $(2023,2023)$ to get to that point
winstonDeGreef
2023-05-23 22:07:08
the shape must be concave
the shape must be concave
Curious_Droid
2023-05-23 22:07:08
the unbounded region is "convex"
the unbounded region is "convex"
dgulotta
2023-05-23 22:09:40
The shape formed by the boards is always concave. We could also prove a weaker statement, that as we go along the boundary, the x-coordinates increase and the y-coordinates decrease.
The shape formed by the boards is always concave. We could also prove a weaker statement, that as we go along the boundary, the x-coordinates increase and the y-coordinates decrease.
dgulotta
2023-05-23 22:10:08
How would we prove one of these statements?
How would we prove one of these statements?
iamhungry
2023-05-23 22:10:27
Induction?
Induction?
dgulotta
2023-05-23 22:11:19
Yes, induction is a good strategy.
If a board cuts off some lava from the infinite region, then it must intersect the previous boundary at two points. As you travel along the previous boundary from one intersection point to the other, the $x$-coordinate is monotone increasing while the $y$-coordinate is monotone decreasing. So the same must be true of the board that you just placed.
Yes, induction is a good strategy.
If a board cuts off some lava from the infinite region, then it must intersect the previous boundary at two points. As you travel along the previous boundary from one intersection point to the other, the $x$-coordinate is monotone increasing while the $y$-coordinate is monotone decreasing. So the same must be true of the board that you just placed.
dgulotta
2023-05-23 22:12:03
Now how do we bound the area cut off by a single board?
Now how do we bound the area cut off by a single board?
vrondoS
2023-05-23 22:14:24
the area is a triangle
the area is a triangle
winstonDeGreef
2023-05-23 22:14:24
this area that is added by one board is at most 0.25, which is the maximum area of a right angle triangle with hypotenuse 1 bounding the new area
this area that is added by one board is at most 0.25, which is the maximum area of a right angle triangle with hypotenuse 1 bounding the new area
dgulotta
2023-05-23 22:14:57
Since the boards on the boundary have negative slopes, the region cut off by a single board must be contained in a right triangle with hypotenuse at most $1$. The height of the triangle must be at most $1/2$ (which you can see by inscribing the triangle in a circle). Therefore, the area cut off is at most $(1/2)(1)(1/2) = 1/4$.
Since the boards on the boundary have negative slopes, the region cut off by a single board must be contained in a right triangle with hypotenuse at most $1$. The height of the triangle must be at most $1/2$ (which you can see by inscribing the triangle in a circle). Therefore, the area cut off is at most $(1/2)(1)(1/2) = 1/4$.
dgulotta
2023-05-23 22:15:18
How much area do we need to cut off in order to reach $(2023, 2023)$?
How much area do we need to cut off in order to reach $(2023, 2023)$?
vrondoS
2023-05-23 22:16:13
at least 2023^2
at least 2023^2
timchen
2023-05-23 22:16:13
$2\cdot2023^2$
$2\cdot2023^2$
winstonDeGreef
2023-05-23 22:16:13
at least 2 * 2023^2
at least 2 * 2023^2
dgulotta
2023-05-23 22:16:28
At the very least, we need to cut off a $2023 \times 2023$ square, which has an area of $2023^2$.
At the very least, we need to cut off a $2023 \times 2023$ square, which has an area of $2023^2$.
dgulotta
2023-05-23 22:16:59
If you're a bit more careful, you can get $2\cdot 2023^2$, but it's not necessary to solve the problem.
If you're a bit more careful, you can get $2\cdot 2023^2$, but it's not necessary to solve the problem.
rithek.shankar
2023-05-23 22:17:46
because the slope has to be negative?
because the slope has to be negative?
dgulotta
2023-05-23 22:17:52
yes
yes
dgulotta
2023-05-23 22:19:15
So we need to fill in an area of at least $2023^2$, but placing a board adds at most $1/4$ to the area. So there's no way to fill the area with 1 million boards.
So we need to fill in an area of at least $2023^2$, but placing a board adds at most $1/4$ to the area. So there's no way to fill the area with 1 million boards.
dgulotta
2023-05-23 22:19:53
Part (b) is somewhat disjoint from part (a), so I'll take questions on part (a) now.
Part (b) is somewhat disjoint from part (a), so I'll take questions on part (a) now.
timchen
2023-05-23 22:21:33
How did we rigorously prove that the max area was $\frac{1}{4}?$
How did we rigorously prove that the max area was $\frac{1}{4}?$
dgulotta
2023-05-23 22:22:52
The boards on the boundary have negative slope. When you place a new board, the area cut off is therefore contained in a right triangle with that board as its hypotenuse.
The boards on the boundary have negative slope. When you place a new board, the area cut off is therefore contained in a right triangle with that board as its hypotenuse.
dgulotta
2023-05-23 22:23:09
The hypotenuse has length at most 1.
The hypotenuse has length at most 1.
dgulotta
2023-05-23 22:23:56
The height must be at most 1/2, since the triangle fits in a circle of radius 1/2, with the hypotenuse as a diameter.
The height must be at most 1/2, since the triangle fits in a circle of radius 1/2, with the hypotenuse as a diameter.
Curious_Droid
2023-05-23 22:24:41
comment: I did 6a in the morning half-awake after I woke up with the idea, glad to hear that it was correct lol
comment: I did 6a in the morning half-awake after I woke up with the idea, glad to hear that it was correct lol
MasterInTheMaking
2023-05-23 22:24:44
I love problem 6b
. It was my favorite by far.
I love problem 6b
. It was my favorite by far.
irobot
2023-05-23 22:26:03
how can we prove that the slopes are always negative?
how can we prove that the slopes are always negative?
dgulotta
2023-05-23 22:26:34
We showed by induction that, as you go along the boundary, the x-coordinates increase while the y-coordinates decrease.
We showed by induction that, as you go along the boundary, the x-coordinates increase while the y-coordinates decrease.
dgulotta
2023-05-23 22:26:46
(b) Give a specific number of boards with which you can reach $(2023, 2023)$.
(b) Give a specific number of boards with which you can reach $(2023, 2023)$.
dgulotta
2023-05-23 22:27:17
We saw quite a few different solutions to this problem. I'll just go over one that is relatively short. If there is interest, I can post additional solutions to parts (a) and (b) in the AoPS forums after the Math Jam is over.
We saw quite a few different solutions to this problem. I'll just go over one that is relatively short. If there is interest, I can post additional solutions to parts (a) and (b) in the AoPS forums after the Math Jam is over.
dgulotta
2023-05-23 22:27:33
Let's say that for some $a$, you have made the line $x+y = a$ safe. Any ideas on how to make the line $x+y=a+\epsilon$ safe, for some $\epsilon$?
Let's say that for some $a$, you have made the line $x+y = a$ safe. Any ideas on how to make the line $x+y=a+\epsilon$ safe, for some $\epsilon$?
dgulotta
2023-05-23 22:29:14
dgulotta
2023-05-23 22:29:26
You can place a sequence of boards so that each board has one endpoint on the line $x+y=a$, the first board has its other endpoint at $(0,a+1/2)$, and each subsequent board has its other endpoint at the midpoint of the previous board.
You can place a sequence of boards so that each board has one endpoint on the line $x+y=a$, the first board has its other endpoint at $(0,a+1/2)$, and each subsequent board has its other endpoint at the midpoint of the previous board.
dgulotta
2023-05-23 22:29:58
You can do the same thing starting from $(a+1/2,0)$. Eventually, the boards meet in the middle. What is a bound for the number of boards used?
You can do the same thing starting from $(a+1/2,0)$. Eventually, the boards meet in the middle. What is a bound for the number of boards used?
winstonDeGreef
2023-05-23 22:31:09
2a+1
2a+1
Curious_Droid
2023-05-23 22:31:09
2a?
2a?
vrondoS
2023-05-23 22:31:09
<=2a
<=2a
jbataops
2023-05-23 22:31:57
2sqrt(2) a
2sqrt(2) a
timchen
2023-05-23 22:31:57
each board takes up at least $\frac{1}{2}$ space on the boundary, and the total boundary length is $a\sqrt{2},$ so we have $2\sqrt{2}a$
each board takes up at least $\frac{1}{2}$ space on the boundary, and the total boundary length is $a\sqrt{2},$ so we have $2\sqrt{2}a$
dgulotta
2023-05-23 22:33:10
The bound that I came up with was $(a+1/2)/\sqrt{7/8}$ on each side.
The bound that I came up with was $(a+1/2)/\sqrt{7/8}$ on each side.
dgulotta
2023-05-23 22:33:52
The first board extends $\sqrt{7/8}$ in the direction parallel to the line, and subsequent boards extend further.
The first board extends $\sqrt{7/8}$ in the direction parallel to the line, and subsequent boards extend further.
dgulotta
2023-05-23 22:34:51
I won't attempt to simplify it, since I have some numbers pre-computed.
I won't attempt to simplify it, since I have some numbers pre-computed.
timchen
2023-05-23 22:35:33
Wait why $\sqrt{\frac{7}{8}},$ since if you use the Law of Cosines, then I don't believe that's the answer
Wait why $\sqrt{\frac{7}{8}},$ since if you use the Law of Cosines, then I don't believe that's the answer
dgulotta
2023-05-23 22:38:12
$(0,a+1/2)$ has distance $1/2 *sqrt(2)/2 = sqrt(1/8)$ from the line $x+y=a$, which leaves $sqrt(7/8)$ in the perpendicular direction
$(0,a+1/2)$ has distance $1/2 *sqrt(2)/2 = sqrt(1/8)$ from the line $x+y=a$, which leaves $sqrt(7/8)$ in the perpendicular direction
shihan
2023-05-23 22:38:46
It doesn't really matter; should we just say it is $\le ka$ where $k<4$?
It doesn't really matter; should we just say it is $\le ka$ where $k<4$?
dgulotta
2023-05-23 22:39:04
Fair enough, the numbers will change slightly, but the argument is the same,
Fair enough, the numbers will change slightly, but the argument is the same,
dgulotta
2023-05-23 22:40:10
Anyway, if $a \ge 4046$, then we have reached $(2023,2023)$. So we can assume $a < 4046$.
Anyway, if $a \ge 4046$, then we have reached $(2023,2023)$. So we can assume $a < 4046$.
dgulotta
2023-05-23 22:41:29
Then $(4046+1/2)/\sqrt{7/8} \le 4236$.
Then $(4046+1/2)/\sqrt{7/8} \le 4236$.
dgulotta
2023-05-23 22:41:50
Sorry, 4326.
Sorry, 4326.
dgulotta
2023-05-23 22:42:00
So we need at most 4326 boards on each side.
So we need at most 4326 boards on each side.
dgulotta
2023-05-23 22:42:16
When the boards meet in the middle, the intersection lies on the line $x+y=a+\epsilon$, for some
$\epsilon$. What is a bound on $\epsilon$?
When the boards meet in the middle, the intersection lies on the line $x+y=a+\epsilon$, for some
$\epsilon$. What is a bound on $\epsilon$?
timchen
2023-05-23 22:43:25
there are approximately a boards on each side, so $\frac{1}{2^a}$?
there are approximately a boards on each side, so $\frac{1}{2^a}$?
dgulotta
2023-05-23 22:43:38
The endpoint of the first board is on the line $x+y=a+1/2$, and each board sticks out half as far as the previous one, so we can take $\epsilon = 2^{-4326-1}=2^{-4327}$.
The endpoint of the first board is on the line $x+y=a+1/2$, and each board sticks out half as far as the previous one, so we can take $\epsilon = 2^{-4326-1}=2^{-4327}$.
yiningwang
2023-05-23 22:44:07
that is very small
that is very small
dgulotta
2023-05-23 22:45:15
Now we can place boards along the line $x+y=a+\epsilon$. (However, this isn't strictly necessary - can you see why?)
Now we can place boards along the line $x+y=a+\epsilon$. (However, this isn't strictly necessary - can you see why?)
Curious_Droid
2023-05-23 22:45:52
some boards are actually beyond the line, like the ones at the edges
some boards are actually beyond the line, like the ones at the edges
timchen
2023-05-23 22:45:52
we already made extra progress (a lot, in fact)
we already made extra progress (a lot, in fact)
dgulotta
2023-05-23 22:46:02
Let's say you have a plan for placing boards along the line $x+y=a$, but instead of the line $x+y=a$ being safe, some chain of segments lying above the line is safe. You can just shorten your boards to end on the safe chain. (Or possibly just not place the board at all, if it lies entirely below the chain.)
Let's say you have a plan for placing boards along the line $x+y=a$, but instead of the line $x+y=a$ being safe, some chain of segments lying above the line is safe. You can just shorten your boards to end on the safe chain. (Or possibly just not place the board at all, if it lies entirely below the chain.)
dgulotta
2023-05-23 22:46:57
Anyway, each time we execute our plan, we increase $a$ by $2^{-4327}$.
Anyway, each time we execute our plan, we increase $a$ by $2^{-4327}$.
dgulotta
2023-05-23 22:47:37
After $4046 \cdot 2^{-4327}$ implementations, we reach the line $x+y=4046$, which contains $(2023,2023)$.
After $4046 \cdot 2^{-4327}$ implementations, we reach the line $x+y=4046$, which contains $(2023,2023)$.
impromptuA
2023-05-23 22:48:08
$4046*2^{4327}$
$4046*2^{4327}$
dgulotta
2023-05-23 22:48:12
Right, sorry.
Right, sorry.
dgulotta
2023-05-23 22:48:45
Each implementation uses at most $2 \cdot 4326$ boards.
Each implementation uses at most $2 \cdot 4326$ boards.
dgulotta
2023-05-23 22:49:04
So that's a total of $2 \cdot 4326 \cdot 4046 \cdot 2^{4327}$ boards.
So that's a total of $2 \cdot 4326 \cdot 4046 \cdot 2^{4327}$ boards.
dgulotta
2023-05-23 22:49:22
That's quite a lot!
That's quite a lot!
timchen
2023-05-23 22:50:06
Not as much as my count
Not as much as my count
winstonDeGreef
2023-05-23 22:50:06
I found a way to do it with just 2,644,863,458,071,694
I found a way to do it with just 2,644,863,458,071,694
dgulotta
2023-05-23 22:50:24
It's possible to prove a much better bound-the best bound that I know of is around 1.2 trillion.
It's possible to prove a much better bound-the best bound that I know of is around 1.2 trillion.
dgulotta
2023-05-23 22:50:40
I'll post that solution and a bunch of others at the end of the Math Jam.
I'll post that solution and a bunch of others at the end of the Math Jam.
MasterInTheMaking
2023-05-23 22:51:31
I'd love to see that 1.2 trillion construction!
I'd love to see that 1.2 trillion construction!
MasterInTheMaking
2023-05-23 22:51:31
my bound was liek 2^{17128} lol
my bound was liek 2^{17128} lol
dgulotta
2023-05-23 22:51:49
I'll pause before moving on to part c.
I'll pause before moving on to part c.
john0512
2023-05-23 22:52:55
Is there a polynomial upper bound (in terms of the 2023)
Is there a polynomial upper bound (in terms of the 2023)
dgulotta
2023-05-23 22:53:35
Yes, the number of boards required to reach $(n,n)$ is cubic in $n$.
Yes, the number of boards required to reach $(n,n)$ is cubic in $n$.
dgulotta
2023-05-23 22:54:52
One more part to go.
One more part to go.
dgulotta
2023-05-23 22:54:54
(c) Prove that one billion boards aren't enough.
(c) Prove that one billion boards aren't enough.
dgulotta
2023-05-23 22:55:12
In part (a), we used area. Are there any other quantities that we could consider?
In part (a), we used area. Are there any other quantities that we could consider?
vrondoS
2023-05-23 22:55:36
perimeter?
perimeter?
ninjatutle
2023-05-23 22:55:41
perimeter?
perimeter?
dgulotta
2023-05-23 22:55:55
Let's see what we can learn by considering the perimeter. Again, we need to say what we mean by "perimeter".
Let's see what we can learn by considering the perimeter. Again, we need to say what we mean by "perimeter".
dgulotta
2023-05-23 22:56:09
If we place a board from $(\sqrt{2}/2,0)$ to $(0,\sqrt{2}/2)$, then we removed two segments of
length $\sqrt{2}/2$ from the infinite lava region, and added a segment of length $1$. We say that the change in perimeter is $\sqrt{2}/2+\sqrt{2}/2-1 = \sqrt{2}-1$.
If we place a board from $(\sqrt{2}/2,0)$ to $(0,\sqrt{2}/2)$, then we removed two segments of
length $\sqrt{2}/2$ from the infinite lava region, and added a segment of length $1$. We say that the change in perimeter is $\sqrt{2}/2+\sqrt{2}/2-1 = \sqrt{2}-1$.
dgulotta
2023-05-23 22:56:12
Make sense?
Make sense?
GuylikesMath
2023-05-23 22:56:51
yes
yes
Curious_Droid
2023-05-23 22:56:51
:thumbsup:
:thumbsup:
ninjatutle
2023-05-23 22:56:51
mhm
mhm
dgulotta
2023-05-23 22:57:05
In general, if the boundary is a chain of segments ending at $(0,y)$ and $(x,0)$, then we say that the change in perimeter is $x+y$ minus the length of the chain.
In general, if the boundary is a chain of segments ending at $(0,y)$ and $(x,0)$, then we say that the change in perimeter is $x+y$ minus the length of the chain.
dgulotta
2023-05-23 22:57:19
Assuming the boundary passes through $(2023,2023)$, can you bound the perimeter?
Assuming the boundary passes through $(2023,2023)$, can you bound the perimeter?
dgulotta
2023-05-23 22:58:31
dgulotta
2023-05-23 22:58:57
This picture shows that it's at most $2 \cdot 2023$. (Remember, you add the horizontal and vertical segments and subtract the diagonal ones.)
This picture shows that it's at most $2 \cdot 2023$. (Remember, you add the horizontal and vertical segments and subtract the diagonal ones.)
dgulotta
2023-05-23 22:59:47
Previously, we showed that if the boundary passes through $(2023,2023)$, the area must be at least $4 \cdot 2023^2$. So we want to show that if the area is at least $4 \cdot 2023^2$ and the perimeter is at most $2 \cdot 2023$, then more than a billion boards must have been placed.
Previously, we showed that if the boundary passes through $(2023,2023)$, the area must be at least $4 \cdot 2023^2$. So we want to show that if the area is at least $4 \cdot 2023^2$ and the perimeter is at most $2 \cdot 2023$, then more than a billion boards must have been placed.
dgulotta
2023-05-23 23:00:23
Previously, we bounded the area cut off by a single board. Now let's consider the change in perimeter when we place a single board. Let $b$ be the length of the board, let $h$ be the maximum distance from the board to a point in the region cut off.
Let $k$ be the change in area. How large can $k$ be in terms of $b$ and $h$?
Previously, we bounded the area cut off by a single board. Now let's consider the change in perimeter when we place a single board. Let $b$ be the length of the board, let $h$ be the maximum distance from the board to a point in the region cut off.
Let $k$ be the change in area. How large can $k$ be in terms of $b$ and $h$?
Curious_Droid
2023-05-23 23:01:16
change in area or perimeter?
change in area or perimeter?
dgulotta
2023-05-23 23:01:30
That was a bit awkwardly worded, but I did mean area - we'll get to perimeter
That was a bit awkwardly worded, but I did mean area - we'll get to perimeter
dgulotta
2023-05-23 23:02:32
The cut off region is contained in a rectangle of length $b$ and height $h$ (again because all slopes are negative). So the area is at most $bh$.
The cut off region is contained in a rectangle of length $b$ and height $h$ (again because all slopes are negative). So the area is at most $bh$.
dgulotta
2023-05-23 23:02:49
Let $p$ be the "change in perimeter". The cut off region has one side of length $b$ (the board that was just placed). What is the sum of the lengths of the other sides in terms of $p$ and $b$?
Let $p$ be the "change in perimeter". The cut off region has one side of length $b$ (the board that was just placed). What is the sum of the lengths of the other sides in terms of $p$ and $b$?
Curious_Droid
2023-05-23 23:04:48
p+b?
p+b?
dgulotta
2023-05-23 23:04:53
Right.
Right.
dgulotta
2023-05-23 23:05:45
We're removing some segments of total length $p+b$ from the boundary, and adding a segment of length $b$, for a difference of $p$.
We're removing some segments of total length $p+b$ from the boundary, and adding a segment of length $b$, for a difference of $p$.
dgulotta
2023-05-23 23:06:05
Now, can we write down an inequality involving $p$, $b$, and $h$?
Now, can we write down an inequality involving $p$, $b$, and $h$?
dgulotta
2023-05-23 23:06:44
Curious_Droid
2023-05-23 23:08:00
b+p <= 2h+b? so p <= 2h
b+p <= 2h+b? so p <= 2h
Curious_Droid
2023-05-23 23:08:24
$b+p \le \sqrt{b^2 + 4h^2}$
$b+p \le \sqrt{b^2 + 4h^2}$
dgulotta
2023-05-23 23:08:41
Almost right, it should be $\ge$.
Almost right, it should be $\ge$.
dgulotta
2023-05-23 23:09:35
$b+p$ is at least the length of the hypotenuse of a right triangle with legs $b$ and $2h$. So $(b+p)^2 \ge b^2 +4h^2$.
$b+p$ is at least the length of the hypotenuse of a right triangle with legs $b$ and $2h$. So $(b+p)^2 \ge b^2 +4h^2$.
dgulotta
2023-05-23 23:09:59
Equivalently, $2bp + p^2 \ge 4h^2$.
Equivalently, $2bp + p^2 \ge 4h^2$.
dgulotta
2023-05-23 23:10:34
Now, that's not the easiest formula to work with; we'd like something simpler.
Now, that's not the easiest formula to work with; we'd like something simpler.
dgulotta
2023-05-23 23:11:12
One way to simplify it is to split into two cases, depending on whether $p$ is large or small compared to $b$.
One way to simplify it is to split into two cases, depending on whether $p$ is large or small compared to $b$.
dgulotta
2023-05-23 23:11:45
When $p \le b$, we have $4h^2 \le p^2 + 2pb \le pb + 2pb = 3pb$. So $p \ge 4h^2/3b \ge (4/3)h^2b^2 \ge (4/3)k^2$.
When $p \le b$, we have $4h^2 \le p^2 + 2pb \le pb + 2pb = 3pb$. So $p \ge 4h^2/3b \ge (4/3)h^2b^2 \ge (4/3)k^2$.
dgulotta
2023-05-23 23:12:24
For $p \ge b$, we have $p \ge b \ge b^4 \ge 16k^2$.
For $p \ge b$, we have $p \ge b \ge b^4 \ge 16k^2$.
dgulotta
2023-05-23 23:13:19
(Previously, when we showed that $k \le 1/4$, the argument actually proved that $k \le b^2/4$.)
(Previously, when we showed that $k \le 1/4$, the argument actually proved that $k \le b^2/4$.)
dgulotta
2023-05-23 23:13:42
Combining these two, we find that $p$ is always at least $(4/3)k^2$.
Combining these two, we find that $p$ is always at least $(4/3)k^2$.
dgulotta
2023-05-23 23:14:03
Does that argument make sense?
Does that argument make sense?
JigglypuffDaBest
2023-05-23 23:16:35
this is exactly like one of those crazy solutions they have in AMC 12 #24 or something. . . lol and by saying this, i mean no for my current brain
this is exactly like one of those crazy solutions they have in AMC 12 #24 or something. . . lol and by saying this, i mean no for my current brain
yiningwang
2023-05-23 23:16:35
no but ok
no but ok
vrondoS
2023-05-23 23:16:35
yes
yes
dgulotta
2023-05-23 23:17:06
Hmm... I'm happy to take questions at the end, but I guess I'll finish the argument first.
Hmm... I'm happy to take questions at the end, but I guess I'll finish the argument first.
dgulotta
2023-05-23 23:17:24
So, we have found that when we place one board, the change in perimeter $p$ and change in area $k$ satisfy $p \ge (4/3)k^2$.
So, we have found that when we place one board, the change in perimeter $p$ and change in area $k$ satisfy $p \ge (4/3)k^2$.
dgulotta
2023-05-23 23:17:47
Now suppose we place $N$ boards, with total perimeter $P$ and total area $K$,
Now suppose we place $N$ boards, with total perimeter $P$ and total area $K$,
dgulotta
2023-05-23 23:18:00
By the power mean inequality (or the Cauchy-Schwarz inequality), we get $P/N \ge (4/3)(K/N)^2$. We can rewrite this as $N \ge (4/3) K^2/P$.
By the power mean inequality (or the Cauchy-Schwarz inequality), we get $P/N \ge (4/3)(K/N)^2$. We can rewrite this as $N \ge (4/3) K^2/P$.
dgulotta
2023-05-23 23:18:43
Then $N \ge 4/3 \cdot (2023^2)^2 / (2 \cdot 2023)$, which is over 5 billion.
Then $N \ge 4/3 \cdot (2023^2)^2 / (2 \cdot 2023)$, which is over 5 billion.
dgulotta
2023-05-23 23:18:51
That's it!
That's it!
dgulotta
2023-05-23 23:19:19
It's possible to tweak this argument to get 31 billion.
It's possible to tweak this argument to get 31 billion.
dgulotta
2023-05-23 23:19:44
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
2023-05-23 23:19:52
If you have any last questions, I can answer them now.
If you have any last questions, I can answer them now.
timchen
2023-05-23 23:20:02
Thank you!
Thank you!
Silvermoonleaf
2023-05-23 23:20:02
Thank you!
Thank you!
dgulotta
2023-05-23 23:20:24
We'll be posting tonight's transcript on 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 on 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
2023-05-23 23:20:42
I'll also post more solutions to problem 6 at https://artofproblemsolving.com/community/c135t71f135h3069224_math_jam_on_may_23_about_the_2023_qq_problems
I'll also post more solutions to problem 6 at https://artofproblemsolving.com/community/c135t71f135h3069224_math_jam_on_may_23_about_the_2023_qq_problems
dgulotta
2023-05-23 23:21:01
We hope you enjoyed this year's QQ, and stay tuned for the 2024 Quiz (and the summer 2024 application) to be posted in January.
We hope you enjoyed this year's QQ, and stay tuned for the 2024 Quiz (and the summer 2024 application) to be posted in January.
timblack
2023-05-23 23:21:19
Thanks everyone!
Thanks everyone!
devenware
2023-05-23 23:21:31
And a special thank you to our presenters!
And a special thank you to our presenters!
snow52
2023-05-23 23:21:42
Thank You!
Thank You!
yiningwang
2023-05-23 23:21:42
bye!!!!
bye!!!!
snow52
2023-05-23 23:21:42
Thank you!
Thank you!
JigglypuffDaBest
2023-05-23 23:22:41
Thank you so much!
Thank you so much!
Joker20
2023-05-23 23:22:41
Thank you!
Thank you!
yiningwang
2023-05-23 23:22:41
thank you!!!
thank you!!!
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
