Math Jams

jwelsh 2025-05-21 18:50:27
Welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam! The Math Jam will begin at 7:00 pm ET (4:00 pm PT). We will cover problems 5-6 today. You can find problems 1-4 in the Math Jam archive: https://artofproblemsolving.com/school/mathjams-transcripts?id=720

jwelsh 2025-05-21 19:00:12
Hello and welcome to the Canada/USA Mathcamp Qualifying Quiz Math Jam!

fengyiteng 2025-05-21 19:00:23
hi

IsaacShi 2025-05-21 19:00:23
hello

weepingwillows 2025-05-21 19:00:23
Hello!

jwelsh 2025-05-21 19:00:25
Before I introduce our guests, let me briefly explain how our online classroom works.

jwelsh 2025-05-21 19:00:34
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.

jwelsh 2025-05-21 19:00:45
Also, you'll find that you can adjust the classroom windows in a variety of ways by clicking on the user dropdown menu in the top-right corner of the classroom.

jwelsh 2025-05-21 19:00:56
Canada/USA Mathcamp is an intensive five-week-long summer program for high-school students interested in mathematics, designed to expose students to the beauty of advanced mathematical ideas and to new ways of thinking. You can learn more about Canada/USA Mathcamp here: www.mathcamp.org

jwelsh 2025-05-21 19:01:04
Many AoPS instructors, assistants, and students are alumni of this outstanding program!

jwelsh 2025-05-21 19:01:22
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 2025 Quiz problems at https://www.mathcamp.org/qualifying_quiz/ . In this Math Jam, members of this year's Mathcamp Quiz committee will discuss the problems are their solutions. Today, we're joined by:

jwelsh 2025-05-21 19:01:33
Dan Gulotta (dgulotta) has been a camper, mentor, and visiting speaker at Mathcamp, most recently in 2021. He is currently a postdoc at the University of Utah, studying number theory and p-adic geometry.

jwelsh 2025-05-21 19:01:44
Neeraja Kulkarni (user1618) has been a mentor at Mathcamp in 2020 and 2023. She is currently a postdoc at the University of Rochester, studying harmonic analysis.

jwelsh 2025-05-21 19:01:58
Also helping out today, we have Kevin Carde (KevinCarde). Kevin is the Assistant Director and Technical Lead of Mathcamp. He's been part of every Mathcamp summer since 2011!

jwelsh 2025-05-21 19:02:11
I'll turn things over to Neeraja (user1618)!

user1618 2025-05-21 19:02:16
Hi everyone! Thanks jwelsh for the introduction. I'm Neeraja, and I'll be presenting problem 5. Dan will be presenting problem 6.
Please feel free to ask questions in the chat at any time!

user1618 2025-05-21 19:02:33
Problem 5: The state of Infiana is an infinite plane of farmland, subdivided into an infinite square grid of 1 km × 1 km plots of land. A finite number of farmers (at least two) each own infinite territory in Infiana, with each 1×1 plot belonging to exactly one farmer. The plots that each farmer owns are connected by orthogonal adjacency; in other words, any two points belonging to the same farmer can be connected by a road that lies within that farmer’s territory and that does not pass through a vertex of a 1 × 1 plot along the way. A farmer may split their territory into two fields by building a fence along the gridlines, all within their own territory. The laws of Infiana dictate that the fence must be of finite length, but the resulting fields must still have infinite area. Each field can then be further subdivided into more fields.

user1618 2025-05-21 19:03:45
Part a:
For each positive integer n, give an example of a territory that can be split into n pieces but no more.

user1618 2025-05-21 19:04:25
Let’s start by getting a feel for the problem by taking a look at some small values of

$n$ . First, what might a territory that can be split into two pieces look like? Describe it.

user1618 2025-05-21 19:06:42
Okay, there are many correct answers! Most of them say "a rectangle with finite width and infinite length"

user1618 2025-05-21 19:07:04
A similar and also correct answer is a U-shape, as shown below.

user1618 2025-05-21 19:07:10

https://cdn.aops.com/images/4/7/6/4760c77f6376b5ef992c127b8be1e2a42718da8f.png

user1618 2025-05-21 19:07:28
This territory can be split into two infinite parts using a fence of length 1 along any of the interior grid lines, but any additional fences would create a finite region, which is not allowed.

user1618 2025-05-21 19:07:59
Now, we want to extend this construction to larger values of

$n$ . What happens if we add another infinite line of grid squares, making it an “m”-shape with infinitely long legs? How many fields can we split this shape into?

user1618 2025-05-21 19:08:08

https://cdn.aops.com/images/e/0/6/e06958b31ac3756ffdf3a6f8f2afdc1727bb1fc3.png

user1618 2025-05-21 19:09:04
It can be split into three fields, as shown here.

user1618 2025-05-21 19:09:13

https://cdn.aops.com/images/3/9/3/3934153615e3afa0fd020fa25b05001b9f7899d7.png

user1618 2025-05-21 19:09:37
Like in the first example, if more than two fences are placed, a finite region is created. One way to persuade yourself of this is that each field needs to contain an infinite portion of at least one of the legs, but this can only be true of one field per leg due to the orthogonal adjacency requirement.

user1618 2025-05-21 19:10:00
We can extend this construction to work for arbitrary

$n$ , creating a “comb” structure with

$n$ infinitely extending “teeth” as shown below.

user1618 2025-05-21 19:10:08

https://cdn.aops.com/images/2/1/c/21caf7311d45e55b23f01dda1c6c479c00c1cbcd.png

user1618 2025-05-21 19:10:33
This answers part (a).

user1618 2025-05-21 19:10:36
Part b:
Prove that no territory can be broken up into infinitely many pieces.

Guest 8480 2025-05-21 19:10:51
Three

yoonsunam 2025-05-21 19:10:51
3

uss2010 2025-05-21 19:10:51
3

DrivenCheetah13 2025-05-21 19:10:51
3

Slipper99 2025-05-21 19:10:51
3

user1618 2025-05-21 19:11:43
A key part of part (b) is the finiteness of the number of farmers. Can you use the solution to part (a) to explain why this is?

user1618 2025-05-21 19:13:00
Great answers from the chat!

user1618 2025-05-21 19:13:10
If the number of farmers could be infinite, we could extend the comb construction from the previous problem infinitely, since doing so would create infinitely many farmers between the “teeth” of the comb.

user1618 2025-05-21 19:13:40
We now want to make a rigorous argument to show that the allowed number of fields is limited in some way by the number of farmers in Infiana.

user1618 2025-05-21 19:14:01
Based on the comb example, it makes intuitive sense that the number of fields is related to the number of ways that the territory “goes out to infinity.” The problem is how to make this notion precise.

user1618 2025-05-21 19:14:28
Many applicants developed an intuitive notion of the “ways of going out to infinity” via the concept of “infinite arms” of a territory, as a generalization of the teeth of the “comb” in part (a).

user1618 2025-05-21 19:14:47
However, this concept is difficult to work with rigorously. How do we define an arm? How do we tell the difference between two arms and two parts of the same wide arm? How do we even know that it’s always possible to define an arm?

user1618 2025-05-21 19:15:05
The key lies in a different property of a territory. Imagine the comb shape. What other attribute of it can we say “goes out to infinity,” other than the interiors of its teeth?

Backbranch 2025-05-21 19:15:37
The territories separating the teeth?

uss2010 2025-05-21 19:15:56
the boundary between farmers' territory.

Pandatao 2025-05-21 19:16:07
The slots between them

user1618 2025-05-21 19:16:34
Nice ideas! Let's think about the boundary between the farmers' territory

user1618 2025-05-21 19:17:20
Think of the "lines" between each pair of plots in different farmers’ territories. We can consider each of the connected components of the graph formed by these line segments as a single “boundary component”.

user1618 2025-05-21 19:17:45
Each boundary component has infinite length, because of the following reasoning. If a boundary component had any endpoints or loops, then the orthogonal adjacency or infinite territory requirements would be violated.

user1618 2025-05-21 19:18:28
Each boundary component can have more than two ends (imagine a "T" or "H" shape), but the portion of a boundary component adjacent to any given territory is just a simple curve of infinite length.

user1618 2025-05-21 19:18:59
A territory is entirely defined by its boundary components. For instance, instead of thinking of the comb in the previous problem as being made up of some number of “teeth,” we can think of it as being bounded by one big U-shaped boundary component with many smaller U-shaped boundary components within its curve.

user1618 2025-05-21 19:19:35
Our goal is to find a relationship between the number of boundary components adjacent to a territory to the number of farmers’ territories adjacent to it.

user1618 2025-05-21 19:20:34
First, note that a single territory cannot be on two sides of a boundary component because then there would be some line of orthogonally adjacent squares within that farmer’s territory which goes from one side of the boundary component to another, which is impossible since boundary components have no endpoints.

user1618 2025-05-21 19:21:34
I now claim that every fence is a simple curve with both ends on a boundary component.

user1618 2025-05-21 19:21:44
Why is this true? Can you explain it?

Backbranch 2025-05-21 19:22:43
If it were not, it wouldn’t fully enclose a shape. You would be able to move around it without leaving a territory.

user1618 2025-05-21 19:23:35
Yeah, if a fence enclosed a shape without having endpoints on a boundary component, the fence would be a loop enclosing a finite area, which is not allowed

user1618 2025-05-21 19:24:27
Great! Next I claim that every fence must go from one boundary component to a different boundary component (i.e. it can't return to the same boundary component). Why is this?

maromex 2025-05-21 19:25:24
if it returned to the same boundary it would enclose a finite space which is not allowed

DittoDino 2025-05-21 19:25:26
It would make the place inside finite

Backbranch 2025-05-21 19:25:52
If it went to the same boundary, you would be able to follow along it in a finite path, so it must enclose a finite space.

user1618 2025-05-21 19:25:57
Perfect!

user1618 2025-05-21 19:26:14
Next, we want to show that no two fences can connect the same pair of boundary components.

user1618 2025-05-21 19:26:32
Imagine that there are two fences which both join the same pair of boundary components. Then you could start at the endpoint of one fence (which is on the first boundary component), travel along the fence to its other endpoint (on the second boundary component), travel along the second boundary component to the second fence, and travel back along the second fence to the first boundary component. Why would this break the laws of Infiana?

maromex 2025-05-21 19:27:12
in Infiana a shape with finite perimeter has finite area

uss2010 2025-05-21 19:27:29
finite area

DittoDino 2025-05-21 19:28:11
Finite perimeter Finite area

user1618 2025-05-21 19:28:28
Yes, again, a closed loop is formed, so that farmer’s field must have finite area.

user1618 2025-05-21 19:29:01
As a result, each pair of boundary components can be connected at most once by a fence, so if there are

$n$ boundary components adjacent to some farmer’s territory, there can be at most

$\binom{n}{2}$ distinct fences.

user1618 2025-05-21 19:29:56
Since there are finitely many farmers, each farmer has a finite number of neighbors, so the number of boundary components adjacent to any farmer's territory if finite.

user1618 2025-05-21 19:30:05
This completes part (b).

user1618 2025-05-21 19:30:21
Part c:

Prove that there are always at least two farmers who cannot split their territory at all.

user1618 2025-05-21 19:30:54
Again, boundary components are the key to solving this problem.

user1618 2025-05-21 19:31:17
We use induction on the number of territories in Infiana for this proof. As a base case, let there be just two territories.

user1618 2025-05-21 19:31:48
Is there ever such a configuration with just 2 territories that can be split, and if not, then why?

Backbranch 2025-05-21 19:32:40
There is only one boundary component, so no.

weepingwillows 2025-05-21 19:32:57
only one boundary comonent

weepingwillows 2025-05-21 19:33:34
which is the single infinite line separating their territories

user1618 2025-05-21 19:34:03
Perfect! If there are 2 farmers, there is exactly one boundary line separating their territories

user1618 2025-05-21 19:34:34
Since each fence must join two distinct boundary components, no fence is possible. This finishes the base case.

user1618 2025-05-21 19:34:54
Now, for the inductive step, suppose that for any number of farmers

$k$ in Infiana which is less than some number

$n$ , there are always at least two farmers who cannot split their territory at all.

user1618 2025-05-21 19:35:28
Let’s consider some configuration of Infiana with

$n$ farmers and assume for the sake of contradiction that it has less than two territories which are unsplittable.

user1618 2025-05-21 19:36:08
Since there are 2 or more farmers in total, at least one farmer can split their territory, so their territory must have at least two boundary components. Let’s call this farmer’s territory

$\mathcal{T}$ .

user1618 2025-05-21 19:37:54
Now we will divide all the farmers, excluding

$\mathcal{T}$ , into 2 groups: "farmers to the left of

$\mathcal{T}$ ", and "farmers to the "right of

$\mathcal{T}$ ", defined in the following way:

user1618 2025-05-21 19:39:12
We can pick the portion of one boundary component adjacent to

$\mathcal{T}$ (which is equivalent to an infinite line) and divide the territories into two “sides”: one including all of the territories on the same side of that infinite line as

$\mathcal{T}$ , other than

$\mathcal{T}$ itself, and the other including all of the territories on the opposite side of that infinite line from

$\mathcal{T}$ .

user1618 2025-05-21 19:39:58
Now, based on this definition, does each side have at least one territory, and why?

maromex 2025-05-21 19:42:29
Yes because there must be an infinite area on one side of an infinite line, and also an infinite area on the other side of the line

Backbranch 2025-05-21 19:42:29
Yes, because a boundary component is defined by two territories, so the boundary components on each side have at least one territory connected to them.

weepingwillows 2025-05-21 19:42:29
yes because \mathcal{T} 's boundary component is a infinite curve that splits it into 2, and every other farmer's territory lies entirely in one of the 2 regions, so each side must contain at least one of the remaining

$n-1$ territories. if one side was empty then all the other farlands would be on the same side of \mathcal{T} 's boundary

uss2010 2025-05-21 19:42:29
If not, T cannot be split.

user1618 2025-05-21 19:42:48
Each side must have at least one territory in it because

$\mathcal{T}$ has at least two boundary components and each boundary component must be adjacent to at least two territories.

user1618 2025-05-21 19:43:20
Recall that we assumed earlier, for the sake of contradiction, that there are less than two unsplittable territories overall.

user1618 2025-05-21 19:43:31
This means that at least one side of

$\mathcal{T}$ has no unsplittable territories. Let’s call that side the “left side” and the other side the “right side.”

user1618 2025-05-21 19:44:42
Imagine a configuration in which all the territories on the left side and

$\mathcal{T}$ are all combined into a single territory; and the territories on the right side are kept as they are.

user1618 2025-05-21 19:44:57
Then how many unsplittable territories does this new configuration have, and how many farmers does it have?

maromex 2025-05-21 19:47:09

$1$ unsplittable territory and less than

$n$ farmers

wams2024 2025-05-21 19:47:09
4 territories and 4 farmers

wams2024 2025-05-21 19:47:09
i mean 3 farmers

maromex 2025-05-21 19:47:09
Then we can use inductive hypothesis to finish

weepingwillows 2025-05-21 19:47:09
1 big farmland on the left side of

$\mathcal{T}$ and all the right side ones, and since left side contributed no unsplittable,

$\mathcal{T}$ must be splittable

user1618 2025-05-21 19:47:26
Okay, many different answers here

user1618 2025-05-21 19:48:33
The new configuration of Infiana has less than two unsplittable territories, since all the territories on the left side are unsplittable and there’s only one other territory which is not from the original left side.

user1618 2025-05-21 19:48:44
Additionally, it clearly has fewer than

$n$ farmers.

user1618 2025-05-21 19:49:17
This now contradicts the inductive hypothesis

weepingwillows 2025-05-21 19:49:41
ohhhhh so the only unsplittable farm must be on the right side farmers, so only one territory is unsplittable in the new configuration, contradiction with the left side no unsplittable assumption, so in the original n both sides must each have at least one unsplittable?

user1618 2025-05-21 19:49:46
yeah!

user1618 2025-05-21 19:50:02
Because of this contradiction, it is necessarily true that there are always at least two farmers who cannot split their territory at all.

user1618 2025-05-21 19:50:10
This completes Problem 5!

user1618 2025-05-21 19:50:23
Thanks everyone for your comments!

user1618 2025-05-21 19:50:28
Now I'll hand it over to Dan to talk about Problem 6.

dgulotta 2025-05-21 19:50:46
Thanks Neeraja!

dgulotta 2025-05-21 19:51:01
Problem 6: The Hilbert Curve is a famous example of a space-filling curve. (You can read all about it on Wikipedia, though you don't need any of that information to solve this problem.) Inspired by the Hilbert curve, Misha decides to build an infinite running track of the same shape. Instead of making the segments smaller and smaller so that the whole thing fits inside a 1×1 square, he makes all the segments 1 meter long and allows the track to extend over the entire first quadrant of the plane.

dgulotta 2025-05-21 19:51:14
The track is constructed in stages, as follows:

dgulotta 2025-05-21 19:51:18
The initial stage

$H_0$ starts at

$(0,0)$ and covers the bottom left

$1 \times 1$ square of the first quadrant. It consists of three segments in a U-shape:

dgulotta 2025-05-21 19:51:28

https://mathcamp.org/files/yearly/2025/quiz/h0.png

dgulotta 2025-05-21 19:51:35
For each positive integer

$n$ , the stage

$H_n$ starts at

$(0,0)$ and covers the bottom left

$(2^{n+1}-1) \times (2^{n+1}-1)$ square of the first quadrant. It begins with

$H_{n-1}$ , then continues with three rotated or reflected copies of

$H_{n-1}$ joined together with line segments of length 1, as shown below:

dgulotta 2025-05-21 19:51:47

https://mathcamp.org/files/yearly/2025/quiz/hn.png

dgulotta 2025-05-21 19:52:02
Note that the procedures for constructing

$H_n$ for even and odd

$n$ are essentially the same. We display them separately to emphasize that when

$n$ is odd, the construction results in

$H_n$ appearing sideways (reflected about the line

$y = x$ ).

dgulotta 2025-05-21 19:52:12
The first few stages of the construction are shown below:

dgulotta 2025-05-21 19:52:21

https://mathcamp.org/files/yearly/2025/quiz/hilbert-stages.png

dgulotta 2025-05-21 19:52:47
(a) Warm-up: how long is

$H_n$ ?

dgulotta 2025-05-21 19:52:55
One way to approach this question is to count the points in

$H_n$ with integer coordinates. How many such points are there?

dgulotta 2025-05-21 19:55:32
(Hint:

$H_0$ has four points with integer coordinates. How many

$H_n$ 's are in an

$H_{n+1}$ ?)

PersistentCrocodile 2025-05-21 19:56:28
4

Pandatao 2025-05-21 19:56:28
4 times

DragonMath0 2025-05-21 19:56:28
four times as many

dgulotta 2025-05-21 19:56:46
Right - so then how many integer points should be in

$H_n$ ?

maromex 2025-05-21 19:57:35

$(2^{n+1})^2 = 2^{2n+2}$

Random37 2025-05-21 19:57:35
4^(n+1)?

weepingwillows 2025-05-21 19:57:35

$4^{n+1}$

fishchips 2025-05-21 19:57:35

$4^{n+1}$

wams2024 2025-05-21 19:57:35

$4^{n+1}$

dgulotta 2025-05-21 19:57:42
Right. There are

$2^{n+1}$ possible

$x$ -coordinates and

$2^{n+1}$ possible

$y$ -coordinates (each ranging from

$0$ to

$2^{n+1}-1$ ). So there are

$4^{n+1}$ points with integer coordinates in

$H_n$ .

dgulotta 2025-05-21 19:57:54
Given that we know the number of points with integer coordinates, how can we find the length of

$H_n$ ?

weepingwillows 2025-05-21 19:59:02
so track length should be

$4^{n+1}-1$ since from the start you need to travel 1 to get to every point

DrivenCheetah13 2025-05-21 19:59:02
that minus 1

Random37 2025-05-21 19:59:02
subtract 1? so the length would be4^(n+1)-1

dgulotta 2025-05-21 19:59:10
Right, since there are

$4^{n+1}$ points with integer coordinates,

$4^{n+1}-1$ line segments of length

$1$ are needed to connect them. So the total length is

$4^{n+1}-1$ .

dgulotta 2025-05-21 19:59:16
So we have solved part (a).

dgulotta 2025-05-21 19:59:31
(b) How far along the track does a runner travel to get to the point

$(n,n)$ ? (Hint: try it first for

$n = 2^k$ .)

dgulotta 2025-05-21 19:59:38
Let's follow the hint and look at the point

$(2^k,2^k)$ first.

dgulotta 2025-05-21 19:59:46
In which stage of the construction does the curve reach

$(2^k,2^k)$ ?

dgulotta 2025-05-21 20:00:21
(Note that (1,1) is the upper right corner of H_0).

Guest 4723 2025-05-21 20:01:56
what is k ？

dgulotta 2025-05-21 20:02:10

$k$ can be any nonnegative integer.

Guest 8487 2025-05-21 20:03:33
H_k

DragonMath0 2025-05-21 20:03:33
H_k ?

dgulotta 2025-05-21 20:03:38
The point

$(2^k,2^k)$ is in

$H_{k}$ but not in

$H_{k-1}$ .

dgulotta 2025-05-21 20:03:42

https://dgulotta.github.io/qq25_jam_images/b1.png

dgulotta 2025-05-21 20:04:10
Does that make sense so far?

dgulotta 2025-05-21 20:05:05
How much of the curve does a runner have to go through to get to

$(2^k,2^k)$ ?

Pandatao 2025-05-21 20:07:21
1/2

wams2024 2025-05-21 20:07:21

$\frac{1}{2}$

maromex 2025-05-21 20:07:46
It's just past halfway on the curve, so

$2^{2k+1}$

Guest 8487 2025-05-21 20:07:46
2^(2k+1)

maromex 2025-05-21 20:07:46
Slightly past half of the curve.

$\dfrac{2^{2k+2}-1}{2} + \frac{1}{2} = 2^{2k+1}$

weepingwillows 2025-05-21 20:07:46
if

$(2^k,2^k)$ is where it is on the diagram then the bottom two

$H_{k-1}$ and the two lines

dgulotta 2025-05-21 20:07:56
They need to go through two full

$H_{k-1}$ 's to get to

$(2^k, 2^k)$ .

dgulotta 2025-05-21 20:08:08
Since an

$H_{k-1}$ has

$4^{k}$ points with integer coordinates, a runner has to pass through

$2 \cdot 4^{k}$ points with integer coordinates before getting to

$(2^k,2^k)$ . So they also have to pass through

$2 \cdot 4^{k}$ segments to get to

$(2^k,2^k)$ .

dgulotta 2025-05-21 20:08:32
Now we consider how many steps it takes to get to the point

$(n,n)$ . Denote this quantity by

$s(n)$ .

dgulotta 2025-05-21 20:08:55
Fix a value of

$k$ . For which integers

$n$ is

$(n,n)$ contained in the original

$H_{k}$ but not the original

$H_{k-1}$ ?

dgulotta 2025-05-21 20:12:40
(Hint: in part (a), we computed the maximum x and y coordinates of a point of

$H_k$ .)

maromex 2025-05-21 20:14:47
when

$2^k \le n \le 2^{k+1} - 1$

dgulotta 2025-05-21 20:14:55
Right,

$(n,n)$ is contained in

$H_{k}$ but not

$H_{k-1}$ if

$2^k \le n < 2^{k+1}$ . In other words,

$2^k$ must be the largest power of two that is less than or equal to

$n$ .

dgulotta 2025-05-21 20:15:12
How is the copy of

$H_{k-1}$ containing of

$(n,n)$ related to the original

$H_{k-1}$ ?

Guest 8487 2025-05-21 20:17:34
it's self similar to the opposite diagonal

dgulotta 2025-05-21 20:17:44
To get the copy, we have to flip the original along the diagonal line

$y=x$ and then translate by

$(2^k, 2^k)$ .

dgulotta 2025-05-21 20:17:50
Under this transformation, which point in the original

$H_{k-1}$ corresponds to the point

$(n,n)$ in the copy?

maromex 2025-05-21 20:19:23
Oops forgot the translation. It's

$(n- 2^k, n - 2^k)$

dgulotta 2025-05-21 20:19:27
Right,

$(n-2^k,n-2^k)$ .

maromex 2025-05-21 20:19:47
After we reach

$(2^k, 2^k)$ , we see that it takes

$s(n - 2^k)$ more steps to get to

$(n, n)$

dgulotta 2025-05-21 20:19:53
From the above analysis, we can write down a recursive formula for

$s(n)$ . What is it?

maromex 2025-05-21 20:21:43

$s(n) = s(2^k) + s(n - 2^k) = 2^{2k+1} + s(n - 2^k)$

dgulotta 2025-05-21 20:21:47
The formula is:

dgulotta 2025-05-21 20:21:48

$s(n) = \begin{cases} 0, & n=0 \\ s(n-2^k) + 2 \cdot 4^k, & 2^k \le n \le 2^{k+1} \end{cases} \,.$

dgulotta 2025-05-21 20:22:00
This formula leads to a nice interpretation of

$s(n)$ in terms of the binary representation of

$n$ .

dgulotta 2025-05-21 20:22:04
If the binary representation of

$n$ is

$n_k n_{k-1} \dotsb n_1 n_0$ , what is the binary representation of

$n-2^k$ ?

Guest 8487 2025-05-21 20:23:29
n_(k-1) n_(k-2) .... n_1 n_0

EaZ_Shadow 2025-05-21 20:23:29
(n_k - 1)n_(k-1)...n_1n_0

Random37 2025-05-21 20:23:29
same thing without leading digit

maromex 2025-05-21 20:23:29

$n_{k-1}n_{k-2}\cdots n_1n_0$

dgulotta 2025-05-21 20:23:35
Right, subtracting

$2^k$ just removes the leading digit (which is

$n_k=1$ ). So the binary representation of

$n-2^k$ is

$n_{k-1} \dotsb n_1 n_0$ .

dgulotta 2025-05-21 20:23:41
Using this information, how would you express

$s(n)$ in terms of the base 2 representation of

$n$ ?

dgulotta 2025-05-21 20:25:50
For example, if

$n=2^{k_2} + 2^{k_1}$ , what is

$s(n)$ ?

maromex 2025-05-21 20:27:02

$2^{2k_2 + 1} + 2^{2k_1 + 1}$

dgulotta 2025-05-21 20:28:04
Right. In general, if

$n$ is a sum of

$2^{k_i}$ 's, then

$s(n)$ is a sum of

$2^{2k_i+1}=2 \cdot 4^{k_i}$ .

dgulotta 2025-05-21 20:29:18
So if n is written as

$n_k n_{k-1} \dotsb n_1 n_0$ in base 2, how would you write

$s(n)$ in base 4 (or 2 if you prefer)?

maromex 2025-05-21 20:30:29

$n_k0n_{k-1}0\cdots n_10n_00$

Guest 8487 2025-05-21 20:30:29
a string of 2s and 0s

dgulotta 2025-05-21 20:31:04
If the base 2 representation of

$n$ is

$n_k n_{k-1} \dotsb n_1 n_0$ , then

$n = \sum_{i=0}^k 2^i n_i$ . We see from the recursive formula that

$s(n) = \sum_{i=0}^k 2 \cdot 4^i n_i$ . Equivalently, the base 4 representation of

$s(n)$ is

$(2n_k)(2n_{k-1}) \dotsb (2n_1)(2n_0)$ . The base 2 representation is

$n_k 0 n_{k-1} 0 \dotsb n_1 0 n_0 0$ .

dgulotta 2025-05-21 20:31:21
This concludes part (b).

dgulotta 2025-05-21 20:31:43
(c) One interesting feature of this running track is that you sometimes pass within a 1-meter distance of points that are very far ahead of you along the track — or very far behind! Suppose Anna, Benny, and Charlotte all start from (0,0) at the same time. Anna strolls at 1 m/s, Benny walks at 2 m/s, and Charlotte jogs at 3 m/s. Which pair(s) of them will pass within 1 meter of each other infinitely often? (Provide a proof both for the pairs that do and for the pairs that don't!)

dgulotta 2025-05-21 20:31:55
Let's look at Anna and Benny first.

dgulotta 2025-05-21 20:31:58
Assume that Benny has traveled between

$4^n$ and

$4^{n+1}$ meters, for some nonnegative integer

$n$ .

dgulotta 2025-05-21 20:32:04
Define

$\overline{H}_n$ to be the original

$H_n$ , plus the segment leading out of it. Then our assumption says that Benny is in

$\overline{H}_n$ , but not in

$\overline{H}_{n-1}$ .

dgulotta 2025-05-21 20:32:14
If Anna is in the first quarter of

$\overline{H}_n$ , where can Benny be?

Guest 8487 2025-05-21 20:33:41
the second quarter

Backbranch 2025-05-21 20:33:41
The second

Random37 2025-05-21 20:33:47
the second quarter?

dgulotta 2025-05-21 20:33:52
Since Benny moves twice as fast as Anna, he would have to be in the first half of

$\overline{H}_n$ . Since we assumed that he has traveled at least

$4^n$ meters, he cannot be in the first quarter, so he must be in the second quarter.

vicinity 2025-05-21 20:33:56
2nd

dgulotta 2025-05-21 20:34:13

https://dgulotta.github.io/qq25_jam_images/c1.png

dgulotta 2025-05-21 20:34:22
If Anna is in the second quarter of

$\overline{H}_n$ , where can Benny be?

Guest 8487 2025-05-21 20:35:10
third or fourth

maromex 2025-05-21 20:35:10
third or fourth quarter

Random37 2025-05-21 20:35:10
3rd or 4th quarter

Backbranch 2025-05-21 20:35:10
the second half of H_n

dgulotta 2025-05-21 20:35:16
Right, Benny has to be in the second half of

$\overline{H}_n$ .

dgulotta 2025-05-21 20:35:21

https://dgulotta.github.io/qq25_jam_images/c2.png

dgulotta 2025-05-21 20:35:26
Can Anna be in the second half of

$\overline{H}_{n}$ ?

catpalasu 2025-05-21 20:36:07
no

Craftybutterfly 2025-05-21 20:36:07
no

Guest 8487 2025-05-21 20:36:07
no

OGMATH 2025-05-21 20:36:07
no

Random37 2025-05-21 20:36:13
Benny would be finished by the time she gets there

dgulotta 2025-05-21 20:36:16
No, then Benny would have to be outside

$\overline{H}_n$ .

dgulotta 2025-05-21 20:36:39
Now let's divide the diagram into sixteenths instead of quarters. It looks like this:

dgulotta 2025-05-21 20:36:42

https://dgulotta.github.io/qq25_jam_images/c3.png

dgulotta 2025-05-21 20:36:47
Each dashed square represents an

$H_{n-2}$ .

dgulotta 2025-05-21 20:36:50
We can compare where Anna and Benny are at various times.

dgulotta 2025-05-21 20:36:58

https://dgulotta.github.io/qq25_jam_images/c4.png

dgulotta 2025-05-21 20:37:03
If Anna is in a light gray region, then Benny must be in the corresponding dark gray region.

maromex 2025-05-21 20:37:50
it looks like they are never exactly 1 meter apart

dgulotta 2025-05-21 20:37:54
In the last (bottom) four diagrams, the regions are more than 1 meter apart.

dgulotta 2025-05-21 20:37:59
In the first two diagrams, there is one corner of the light region that is 1 meter from a corner of the dark region. But we can check that Anna and Benny do not reach these corners at the same time.

dgulotta 2025-05-21 20:38:25
Assuming

$n \ge 2$ (so that it makes sense to divide

$\overline{H}_n$ into sixteenths), Anna and Benny cannot pass within 1 meter of each other. So in total, they can pass within 1 meter of each other only finitely many times.

dgulotta 2025-05-21 20:38:32
Now let's consider Benny and Charlotte.

dgulotta 2025-05-21 20:38:36
Our strategy will be similar. We assume that Charlotte is in

$\overline{H}_n$ , but not in

$\overline{H}_{n-1}$ . We get a similar diagram:

dgulotta 2025-05-21 20:38:38

https://dgulotta.github.io/qq25_jam_images/c5.png

dgulotta 2025-05-21 20:39:21
In this case, dividing

$\overline{H}_n$ into 16ths wasn't enough: we had to divide it into 64ths.

dgulotta 2025-05-21 20:39:25
The diagram shows that if

$n \ge 3$ (so that it makes sense to divide the diagram into 64ths), Benny and Charlotte cannot pass within 1 meter of each other.

Random37 2025-05-21 20:40:15
wait, but can't Anna and Benny pass within one meter of each other when they are both in the first quarter?

dgulotta 2025-05-21 20:41:03
If they were both in the first quarter of

$\overline{H}_n$ , then they are both in

$\overline{H}_{n-1}$ , so we can perform the same analysis with

$n$ replaced by

$n-1$ .

dgulotta 2025-05-21 20:41:52
As long as Benny isn't in the first quarter of

$\overline{H}_0$ , we can always find some

$n$ so that Benny is in

$\overline{H}_n$ , but not in the first quarter.

dgulotta 2025-05-21 20:42:03
And he's only in

$\overline{H}_0$ for a finite amount of time.

dgulotta 2025-05-21 20:43:00
Finally, let's consider Anna and Charlotte.

dgulotta 2025-05-21 20:43:03
Even when we split

$\overline{H}_n$ into 64ths, it looks like Anna and Charlotte can potentially pass within 1 meter of each other.

dgulotta 2025-05-21 20:43:04

https://dgulotta.github.io/qq25_jam_images/c6.png

dgulotta 2025-05-21 20:43:23
It looks like Anna passes the point

$(2^n-1,2^n-1)$ around the same time that Charlotte passes the point

$(2^n,2^n)$ .

dgulotta 2025-05-21 20:43:26
How long does it take Charlotte to reach

$(2^n,2^n)$ ?

dgulotta 2025-05-21 20:43:59
(Note that we computed the distance to

$(2^n, 2^n)$ in part (b).)

maromex 2025-05-21 20:45:07

$\frac{2^{2n+1}}{3}$ seconds i mean

dgulotta 2025-05-21 20:45:12
In part (b), we calculated that Charlotte has to run

$2\cdot 4^n$ meters to reach

$(2^n,2^n)$ . Since she travels at 3 m/s, it will take her

$2 \cdot 4^n/3$ seconds to reach

$(2^n,2^n)$ .

Random37 2025-05-21 20:45:30
I'm confused about the question. What exactly does it mean to pass by each other "infinitely often"?

dgulotta 2025-05-21 20:47:05
After the first few seconds, any pair of runners will be at least 1 meter apart. Occasionally, they might be exactly 1 meter apart. So the question is asking whether there are infinitely many occasions where this happens.

dgulotta 2025-05-21 20:47:50
Does that make sense?

dgulotta 2025-05-21 20:48:34
Going back to Anna and Charlotte... How long does it take Anna to reach

$(2^n-1,2^n-1)$ ?

dgulotta 2025-05-21 20:49:24
Again, it's possible to use the formula that we found in part (b).

maromex 2025-05-21 20:50:44

$2^{2n-1} + 2^{2n-3} + 2^{2n-5} + \cdots + 2^3 + 2^1 = \frac{2^{2n+1} - 2}{3}$

dgulotta 2025-05-21 20:50:46
Since

$2^n-1$ can be written as

$\underbrace{11\dotsb 1}_n$ in base 2, our solution to part (b) tells us that the number of meters that Anna needs to walk to reach

$(2^n-1,2^n-1)$ is

$\underbrace{22\dotsb2}_n$ in base 4. This is

$2 \cdot (4^{n-1}+4^{n-2}+\dotsb+1) = 2(4^n-1)/3$ meters. Anna travels at 1 m/s, so it will take her

$2(4^n-1)/3$ seconds.

dgulotta 2025-05-21 20:50:50
So Anna reaches

$(2^n-1,2^n-1)$ just slightly before Charlotte reaches

$(2^n,2^n)$ .

dgulotta 2025-05-21 20:50:58
Now look at the first few steps in the construction of the Hilbert curve again.

dgulotta 2025-05-21 20:51:02

dgulotta 2025-05-21 20:51:21
Which way does Anna walk just after she reaches

$(2^n-1,2^n-1)$ ? (The answer depends on

$n$ .)

maromex 2025-05-21 20:54:28
Left if

$n$ is even, down if

$n$ is odd

dgulotta 2025-05-21 20:54:39
If

$n$ is even, then Anna walks left. If

$n$ is odd, then she walks down.

dgulotta 2025-05-21 20:54:41

https://dgulotta.github.io/qq25_jam_images/c7.png

dgulotta 2025-05-21 20:54:54
Which way does Charlotte walk just before she reaches

$(2^n,2^n)$ ? (Again, the answer depends on

$n$ .)

weepingwillows 2025-05-21 20:57:09
up if n is odd, right if n is even

dgulotta 2025-05-21 20:57:12
If

$n$ is odd, then Charlotte walks upward. If

$n$ is even, then she walks to the right.

dgulotta 2025-05-21 20:57:14

https://dgulotta.github.io/qq25_jam_images/c8.png

dgulotta 2025-05-21 20:57:33
So do Anna and Charlotte pass within 1 meter of each other in between the time Anna reaches

$(2^n-1,2^n-1)$ and the time Charlotte reaches

$(2^n,2^n)$ ?

maromex 2025-05-21 20:58:38
When

$n$ is odd, yes

dgulotta 2025-05-21 20:58:45

https://dgulotta.github.io/qq25_jam_images/c9.png

dgulotta 2025-05-21 20:59:01
In this case, Anna and Charlotte are moving in opposite directions on parallel segments. At some time, they will have the same

$x$ -coordinate, and they will be exactly 1 meter apart.

dgulotta 2025-05-21 20:59:06
It's possible to calculate that they are 1 meter apart at time

$2\cdot 4^n/3 - 5/12$ .

dgulotta 2025-05-21 20:59:32
So we have shown that Anna and Charlotte pass each other infinitely often.

dgulotta 2025-05-21 21:01:19
We're running short on time, so I think we will have to skip part (d). But we will make sure to post a solution on the Mathcamp web site.

dgulotta 2025-05-21 21:04:16
There is a request for the problem statement for part d so I'll post that.

dgulotta 2025-05-21 21:04:28
(d) Della and Ellie each take a stroll along the running track at a speed of 1 m/s. Ellie starts

$k$ seconds after Della, where

$k$ is a positive odd integer. Show that there is some value of

$k$ such that Della and Ellie never pass within 1 meter of each other.

sharknavy75 2025-05-21 21:04:39
Can you put a link here?

dgulotta 2025-05-21 21:05:29
I assume the solutions will be available at https://mathcamp.org/qualifying_quiz/solutions/.

dgulotta 2025-05-21 21:05:54
That's the end of the quiz. Thank you so much for spending your evening with us!

dgulotta 2025-05-21 21:06:08
We'll be posting tonight's transcript at https://www.mathcamp.org/qualifying_quiz/solutions/ within the next few days, in case you want to revisit some of what we covered tonight.

dgulotta 2025-05-21 21:06:10
We hope you enjoyed this year's QQ, and stay tuned for the 2026 Quiz (and the summer 2026 application) to be posted in January.

jwelsh 2025-05-21 21:06:24
Thank you all for coming! Over 300 students joined us over the course of today's Marthcamp Math Jam!

jwelsh 2025-05-21 21:06:57
& a special thanks to Mathcamp for coming out tonight too!

Backbranch 2025-05-21 21:07:04
Thank you!

Guest 8487 2025-05-21 21:07:04
thank you! bye!

jwelsh 2025-05-21 21:07:16
If you have questions for Mathcamp, you ask tomorrow or can contact them at www.mathcamp.org/contact.php

jwelsh 2025-05-21 21:07:37
A transcript of this Math Jam will be posted soon here: www.aops.com/school/mathjams-transcripts

jwelsh 2025-05-21 21:07:45
We're closing the classroom now!

Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6

Facilitator: