Choate STEM Problem of the Week

Field: Linguistics
Problem ID: 1
Author: David Garsten '23 (adapted from Doris L Payne)
Effective Date: 10/27/2021
Difficulty: 3 jalapeños
Problem statement: 
Tone is very important in the East African language Maasai. Vowels written with an acúte accent have high tone, those with a gràve accent have low tone, and those without an accent have mid tone.

(Pronunciation guide: 
ɔ = "awe"
ɛ = "let"
ɪ = "bit"
ʊ = "hood"
ŋ = "song")

Here are some sentences in Maasai: 

1) éósh ɔlmʊraní ɔlásʊráɪ̀
2) áadɔ́l ɔlasʊráɪ́
3) áaósh ɔlmʊraní
4) ɪ́dɔ́l ɔlmʊránì
5) íóshokí ɔlmʊránì ɔlásʊráɪ̀
6) ádúŋokí ɔlmʊránì ɔlcɛtá
7) ádúŋ ɔlcɛtá
8) áaduŋokí ɔlmʊraní ɔlcɛtá
9) áadúŋ ɔlmʊraní
10) édúŋ ɔlmʊraní

Match them to their English translations: 

A) The warrior cuts me.
B) The warrior cuts the tree for me.
C) The warrior cuts it.
D) I cut the tree for the warrior.
E) The warrior hits me.
F) You see the warrior.
G) The warrior hits the snake.
H) The snake sees me.
I) You hit the snake for the warrior.
J) I cut the tree.

Field: CS
Problem ID: 2
Author: Jewon Im (credit: Quora)
Effective Date: 11/08/2021
Difficulty: 2 jalapeños
Problem statement: Using any language, write code that prints the numbers 1 to 20, each on separate lines, without using any numerical digit (0...9) in the actual code.

Output should look like:
1
2
3
…
19
20

Point distribution: 1 point for logic, 1 point for syntax.

Field: Math
Problem ID: 3
Author: ryang (written by Ireland)
Effective Date: 11/15/2021
Difficulty: 3 jalapenos?
Problem Statement: 
Each of $n$ members of a club is given a different item of information. The members are allowed to share the information, but, for security reasons, only in the following way: A pair may communicate by telephone. During a telephone call only one member may speak. The member who speaks may tell the other member all the information the speaker knows. Determine the minimal number of phone calls that are required to convey all the information to each of the members.

Point Distribution: 1 point for answer, 2 points for proof.
New Point Distribution (implemented 11/16): 1 point for answer, 1 point for showing that your method achieves the answer, and 1 point for showing that you need at least that many phone calls.

Field: CS
Problem ID: 4
Author: Jewon Im
Effective Date: 11/23/2021
Difficulty: 2 jalapeños
Problem statement: Give the 5000th fibonacci number, modulo 10^9+7. Do not submit your full code. (Note: fib(1) = 1, fib(2) = 1, fib(3) = 2...)

EDIT: you can use modulo 10^9+9, as long as you specify when submitting that you used this number instead.

Point distribution: 1 point for answer, 1 point for the name of the technique you used to optimize your algorithm.

Field: Physics
Problem ID: 5
Author: ryang
Effective Date: 11/29/2021
Difficulty: 2.5 jalapeños

Problem Statement: 
Two fences of height $h_1$ and $h_2$ (perpendicular segments to
the ground) have distance d between the topmost points of 
the fences. Show that the minimum speed required to throw 
a ball over both fences (with initial position/speed/angle 
varied) is $v=\sqrt{g(h_1+h_2+d)}.

EDIT: The question is equivalently asking you to show that if the initial velocity is less than sqrt(g(h1+h2+d)), it cannot make it over both fences regardless of where on the ground it is thrown from, and the angle it is throw at. 

Field: Logic
Problem ID: 6
Author: ryang, jewon im
Effective Date: 12/6/2021
Difficulty: 3 jalapenos

Problem Statement: 
You have 100 different kinds of pills, 99 are harmless and 1 of them is poisonous. You wish to determine which type is poisonous. You have at your disposal an infinite supply of rabbits. 

You may complete a single-day experiment. In the morning, you give each rabbit some set of pills and it eats all of them. Later that day, your research assistant will tell you which rabbits got poisoned.

What is the minimum number of participating rabbits needed to guarantee determining which type of pill is poisonous if you have:
(1) one of each kind of pill (1 point, ~1 jalapeno) 
(2) two of each kind of pill (1 points, ~2.5 jalapeno)
(3) infinitely many of each kind of pill (1 points, ~2 jalapeno)

Bonus points if you submit a general formula. (n pills, k of each kind of pill, and a somewhat reasonable way to find the min # of rabbits needed)

Field: CS
Problem ID: 8
Author: jewon im
Effective Date: 12/13/2021
Difficulty: 4 jalapeños
Problem statement: 
Given a list of N unique numbers, give an algorithm/method guaranteeing to find a local minimum (not absolute minimum) in time complexity < O(N). The time required to read in the list is ignored.

Point distribution: 1 point for algorithm, 1 point for time complexity of algorithm, 1 point for reasoning.

Clarifications:
1. A local min is some number that is smaller than both of its neighbors.
2. What  <O(n) means is that you need to find an algorithm such that if it executes in f(N) moves for a list with N numbers, then the limit as N goes to infinity of f(N)/N is 0.

Field: Math
Problem ID: 9
Author: Ryan Yang
Effective Date: 12/27/2021
Difficulty: 3 jalapeños
Problem Statement: 
Bob is thinking of a positive integer less than 100. Alice wants to figure out his number, and can ask him seven yes or no questions about it. However, once Bob has said no four times, he will feel too sad to answer any more questions. Show that Alice can always figure out Bob's number. 
(submit what her first question should be)

Field: Chess
Problem ID: 10
Proposer: Ryan Yang
Effective Date: 1/4/2021
Difficulty: 1 jalapeños. Worth 2 points.
Problem Statement:
[Black to play and mate.](https://cdn.discordapp.com/attachments/891482447580123137/928136966409683004/Screen_Shot_2022-01-04_at_11.02.22_PM.png?ex=666875a8&is=66672428&hm=bdd95f0075de44f4f9e19c511be84c2c2fa844612f68bf501ead3ec71416c646&)

Field: Logic
Problem ID: 11
Author: Ryan Yang (from free-sudoku.com)
Effective Date: 1/10/2022
Difficulty: 1 jalapeños
Problem statement: Solve the sudoku. You may submit to the bot using a Discord media link (send image to random channel -> copy media link)
https://cdn.discordapp.com/attachments/925247394218651659/930245731565076521/1231f334-a58f-4725-8d57-02ede1545619.png?ex=66683899&is=6666e719&hm=de4717639873a35afe7239dbb285fff0670562c84d18c14480db08a9d0ba3914&

If you can not get the media attachment to work, you 
 may submit the list of 9 numbers that go along the main NW to SE diagonal. (Should be of the form 7XXXXXXX4)

Field: CS
Problem ID: 12
Author: Jewon Im
Effective Date: 1/17/2022
Difficulty: 3 jalapeños

Problem statement:
You are given an array of integers. You are allowed to make calculations and store memory as you wish based on this array. Then, you will be given a random continuous subset of the array, and asked to find the standard deviation of the subset. A constraint is that you are not allowed to iterate over any arrays after being given the subset (making the time complexity O(1)). This means that no matter what subset you are given, you will be able to return the standard deviation in the same time complexity.
What is the minimal amount of memory needed for your pre-calculations in order to find the standard deviation with this limitation?

One way would be to calculate and store the standard deviation for every possible subset of the array using a large "answer key" array of size 2^n. Any answers more optimal than this solution will be accepted and awarded 0-3 points depending on its optimality.

Field: Linguistics
Problem ID: 13
Author: David Garsten
Effective Date: 1/25/2022
Difficulty: 3 jalapeños

Problem statement: 
Dorini is my conlang. Ryan made me do this. One of the major components of Dorini sentence structure is “topic,” which marks the emphasized argument of the sentence. Below are some sentences in Dorini with their English translations. Topics are bolded.

1) Ryan explains math in the study room.
ttumakuda Ryan rddarsuguda i duasiwo

2) My dog bites the teacher. 
lakiu dua ssi kobachin

3) The Assessment Team chases my friend. 
koba duakadu nri nkachin

4) Deven eats an eel because of my parrot. 
samo Deven rtunjoki wa ttumashi

5) Your teacher bites your friend's meal in the dining hall. 
lakiu duamo samosiwo nri shiushiuda nkamo

6) The Assessment Team explains math. 
ttumakuda rddarsuguda ssi duakadu

7) JFK chases fish in the library.
koba JFK shagushi i tikusiwo

8) The dining hall kills procrastination.
waiha samosiwo nri rsurlarda

1. How would you say the following sentences in Dorini?
a) The teacher chases JFK because of procrastination. 
b) My dog kills math in the library study room. 
c) My friend eats the eel.

Now look at the following question-answer dialogues. One answer has been translated for you. 

9) i ji kasamo Neill kan Latin?
kasamo Neill kan Latin i duasiwo
(answer translation:) Neill thinks about Latin Club in the study room.

10) nri ji chishanji?
chishanji nri jewokoba

11) kussu i kanda mi?
rda, kussu i kanda

2. Based on these examples, translate the following responses into English, underlining focused elements, and saying what Dorini questions could have prompted them.

a) mana, mandua Michael nri rddarsuguda
b) amu shibi wa paqakadu
c) kaku ji amu machika ssi Sam

Point distributions: 1 point per subproblem (6 points total), partial credit given.

The previous POTD (ID: 12) will remain active. 5 points are available if you submit code that terminates within 30 seconds with the [attached test case](jewonim.com/assets/txt/12values.txt). The test case is of the form:
N Q
a[0] a[1] a[2] a[3] .... a[N-1]
l[0] l[0]
l[1] r[1]
...
l[Q-1] r[Q-1]

where N is the size of the array, and Q is the number of queries. Your task is to print out the standard deviation of the numbers a[L], a[L+1], .... a[R-1], a[R] for each query "L R".

Here's a small test case to test your code with:
10 4
1 0 11 3 5 9 8 7 9 10
0 5
2 4 
3 9
4 7

which is asking you to print
1. stdev(1,0,11,3,5,9)
2. stdev(11,3,5)
3. stdev(3,5,9,8,7,9,10)
4. stdev(5,9,8,7)

Field: Math
Problem ID: 14
Author: Deven (Found on TikTok)
Effective Date: 2/1/2022
Difficulty: 1.5 jalapeños

Problem Statement: 
Given an equilateral triangle with side length 10, if you select a random point P in its interior, what is the range of possible values of the sum of the distances from the point to each side?

Field: Games + Theory! Strategy!
Problem ID: 15
Author: Ryan Yang (adapted from a round run by Brandon Wang)
Effective Date: 2/7/2022
Difficulty: NA. Your submission will be competing against others' submissions.

Problem Statement: 
This week's POTW will be a Blotto round due at 11:59pm EST, February 13th, 2022. You will submit a list of nine non-negative integers that sum to 100 to either the bot or https://forms.gle/4qFr8iJfTEsZuN5w9. For example, "100 0 0 0 0 0 0 0 0" is a valid submission. All submissions will be played against each other and ranked based on the rules explained in the dropbox document. POTW points will be assigned based on the rankings.

Details about how matchups will be scored:
https://www.dropbox.com/s/ou49kyfymf0td5k/Blotto_Round_1__BOTW_%20(2).pdf?dl=0

EDIT 2/13: 
Just a reminder that submissions are due tonight. In case the original explanation was unclear, here's another attempt at an explanation. You're fighting for control on a 3x3 grid,

1 2 3
4 5 6
7 8 9

and you send some number of troops to each of the sites. Then, based on who gets control, points are awarded. You get 1 point for controlling a square, and 2 more points for each row, column, diagonal that you achieve.

Example: In A = (11,11,11,11,12,11,11,11,11) vs. B = (20, 0, 0, 20, 20, 20, 0 ,0 ,20), the grid looks alike

B A A
B B B 
A A B

so A gets 4 + 2* 0 = 4 points, and B gets 5 + 2*2 = 9 points, and B wins the matchup. 

Field: Math
Problem ID: 16
Author: Jewon Im (credit: random Instagram post)
Effective Date: 2/14/2022
Difficulty: 2 jalapeños

Problem statement: 
Given that the side of the square has length x, give the circumference of the circle in terms of x. (2 points)
https://cdn.discordapp.com/attachments/899463961836142664/943006685801377862/unknown.png?ex=666880aa&is=66672f2a&hm=898e378e47ec4c1ab613216a2fd12602dbb346c1f9aa69a452e5d1b90ec78230&

Field: Math
Problem ID: 17
Author: Ryan Yang (From a Michael Ren handout)
Effective Date: 2/21/2022
Difficulty: 3 jalapeños

Problem Statement:
You’re given a triangular cake and a box in the shape of its mirror image.
Can you cut the cake into three pieces which fit in the box?
(The cake has icing and
thus may not be placed upside down.)
https://cdn.discordapp.com/attachments/891482447580123137/945540158898442240/IMG_ADBAA6E51E1E-1.jpeg?ex=66687da5&is=66672c25&hm=0e56c748479f31b477ea05e504608d16c9fd2990af92bef7e6b98ca71d46e650&

You must justify your answer in order to receive points. (3 points available)

Field: Math
Problem ID: 18
Author: Ryan Yang (Adapted from Folklore?)
Effective Date: 2/28/2022
Difficulty: 2 jalapeños
Problem Statement: Deven forgot to take a screenshot at both 2:22 pm and 22:22 on 2s Day (February 22nd, 2022). Frustrated by this, he vows to find love elsewhere, perhaps with the number 3? To this end, he hopes to find 2022 positive perfect cubes that sum to a positive perfect cube. Is this possible?

0.5 points for the correct yes/no answer, and 2 points for a full solution.

Field: CS + Stats
Problem ID: 19
Author: Ryan Yang (Original)
Effective Date: 3/15/2022
Difficulty: 2 jalapeños, 3.14 points.
Problem Statement: Happy (Belated) Pi Day!
One way to calculate pi is with a monte carlo simulation. This is done by sampling x from [-1,1] and y from [-1,1]. The probability that any such sample satisfies x^2+y^2<1 is pi/4.

If you repeatedly samplen times, then you can estimate pi as 4*(# inside the circle)/n. 
Let d be the number of digits guaranteed to you by the 99%  confidence interval. Find the functional dependence between n and d.

Stats Notes: The formula for the 99% confidence interval is mean +- 1.960 * (STDEV / sqrt(# of samples)).

The formula for the standard deviation is STDEV = sqrt(variance). Variance is equal to E[(x-avg)^2] = E[x^2] - E[x]^2. Also, note that Var(X+Y) = Var(X)+ Var(Y)  when X and Y are uncorrelated variables.

Field: Logic
Problem ID: 20
Author: Ryan Kim (Korean TV show?)
Effective Date: 3/28/2022
Difficulty: 2 jalapeños
Problem statement: Find the 5th number (2 points).
https://cdn.discordapp.com/attachments/896468283660845056/958170005202145320/image0.png?ex=66684b9b&is=6666fa1b&hm=9f908d9aa3a72360f0ea8a29d071e10d15e48a39adc85e6c1cddb93290826c25&

Hint (3/29): The fact that the numbers are written in a 7-segment display font is important

Field: Math (Geometry)
Problem ID: 21
Author: Ryan Yang (pseudo-folklore problem)
Effective Date: 4/4/2022
Difficulty: 3 jalapeños.
Problem Statement: 
A quadrilateral with side lengths 1,4,8,7 (in that order) can be inscribed in a circle. What is the diameter of that circle? (3 points)

Field: Logic
Problem ID: 23
Author: Ryan Kim (taken from Korean YT channel?)
Effective Date: 4/12/2022
Difficulty: 1 jalapeños
Problem statement: Move one number to make this equation true. You are not allowed to touch the + or = signs. (1 point)
https://cdn.discordapp.com/attachments/896468283660845056/963514120903221248/unknown.png?ex=66689ef3&is=66674d73&hm=3cf4998c94be7f6d4f4f010dcb0f6ccde224e2bbe9355ee308e735859d931eb8&

Field: Algorithms
Problem ID: 25
Author: Ryan Yang (from IOI)
Effective Date: 4/18/2022
Difficulty: 2 jalapeños
Problem Statement: 
You are given L<R, and some molecules with weights w0, w1, ... w[n-1]. It is guaranteed that R-L >= max(w) - min(w). Give an algorithm that determines whether there exists a set of molecules whose total weight is in the range [L, R], or state that no such set exists. 

(No coding necessary, although coded solutions are encouraged)

Field: Algorithms
Problem ID: 26
Author: Ryan Yang (old codeforces)
Effective Date: 4/26/2022
Difficulty: 3 jalapeños
Problem Statement: 
A field contains 𝑛^2 square cells grouped into 𝑛 rows and 𝑛 columns. The cells are labeled in some order with 1,2,3,...,𝑛^2. Additionally, for each cell A, one of the four adjacent (horizontally or vertically) cells has a larger number than A does.

You can check individual cells' numbers. Use this information to locate the cell with value 1. For full credit, do this with <4n queries.

Hint: Don't check POTW 8

Field: Math
Problem ID: 27
Author: Ryan Yang 
Effective Date: 5/9/2022
Difficulty: 2 jalapeños, worth 3 points
Problem Statement:  Prove that the sum of two consecutive odd primes (i.e. 3 and 5 or 23 and 29) is the product of at least three (possibly repeated) prime factors.
https://cdn.discordapp.com/attachments/891482447580123137/973352373663727746/unknown.png?ex=66682849&is=6666d6c9&hm=b0dd15d9b616c38b0d78b969e8b5cd5bc0a76d57337b4c4c148dd97259bd9440&

Field: Math
Problem ID: 28
Author: Ryan Yang (From Po-Shen Loh Handout)
Effective Date: 5/16/2022
Difficulty: 2 jalapeños, 3 points
Problem Statement:  The 3-dimensional vectors A, B, and C satisfy: (x is cross product)
A x B = B x C = C x A ≠ 0 
Prove that A+B+C = 0.

Just for fun: worth 0.5 pt for correct answer (allowed until next potw), and 100 points for accurate, generalizable, reasoning (no time limit). Find the next number in the sequence
1, 3, 7, 13, 27, 31, 37, 45, 57, 61, 67, 75, 81, 85, 91, 103, 115, 117, 133, 135, 147, 163, 171, 181, 193, 201, 205, 207, 211, 217, 237, 261, 265, 271, 273, 283, 291, 295, 313, 325, 337, 343, 351, 355, 363, 367, 373, 381, 387, 391, 405, 415, 421, 423, 427, 435, 441, 445, 453, 457, 475, 487, 493, 495, 507, ... 

Field: ??
Problem ID: 29
Author: Ryan Yang
Effective Date: 6/6/2022
Difficulty: 1.5 jalapeño, 2 points
Problem Statement Say that person A outranks person B if B calls A by a title while A calls B by their first name. Find some three people A,B,C such that A outranks B, B outranks C, and C outranks A. (under standard social norms) 

Field: Chess
Problem ID: 30
Author: Ryan Yang (original puzzle 😛 )
Difficulty: 3 jalapeno, 5 points
Effective Date: 7/27/2022
Problem Statement:
Luke is walking around a tournament and sees Max and Eric playing the attached position with white to move. Evaluate the position:
https://cdn.discordapp.com/attachments/788112485847662602/937089047497699338/Screen_Shot_2022-01-29_at_3.57.16_PM.png?ex=6668ba2f&is=666768af&hm=1f65c290344e0ebe702c435d2d285377cafb8642f4822cfd4f141a59bdbf6280&
FEN: rnB5/k2N4/N1P5/PpK5/8/8/8/8 w - b6 0 2 
(I trust y'all not to use an engine pls)

Hint (7/28): White has mate in <=2
Hint (7/31): This position is very hard to reach. considering what black's most recent move was is very helpful.

Field: Math
Problem ID: 31
Author: Peyton Li, Ryan Yang
Effective Date: 8/2/2022
Difficulty: 3 jalapeno, 5 points
Problem Statement: Let X = (1-1/2)(1-1/4)(1-1/8)(1-1/16)(1-1/32)(1-1/64)(1-1/128)..... = prod_{n=1}^{infty} (1- 0.5^n). You can easily get an upper bound by computing a few terms, but getting a lower bound is much harder. Find a lower bound on X and you will be scored based on the strength of the lower bound:
 - X>0: 2 points
 - X>=63/256: 3 points
 - X>=1/4: 4 points
 - X>=9/32: 5 points
You can use a calculator, but I'll just tell you that X is approximately 0.28878.

Remark (where this problem came from): In F_2, the probability that a NxN matrix with randomly selected entries is invertible is prod_{n=1}^{N} (1- 0.5^n) 

Field: Puzzles
Problem ID: 32
Author: Communicated by Jeffrey Chen
Effective Date: 8/15/2022
Difficulty: 1.5 jalapenos, 3 points

Problem Statement:
Move one matchstick to make the following equation (2+5=9) true:
https://cdn.discordapp.com/attachments/891482447580123137/1008744088369111100/IMG_DC4BCB46087A-1.jpeg?ex=66685f24&is=66670da4&hm=aab05ef75e5b2b1e34e113ed8add5f273b35c649fe781fe6ea52a5570c36c254&

Field: Math
Problem ID: 33
Author: Ryan Yang. (flavor text written w/ jewon)
Effective Date: 8/27/2022
Difficulty: 2 jalapenos, 3 points

Problem Statement:
Jewon is sitting in a van with 5 big bags of poisoned candy. She gives candy to passing children (each child gets at most one of each type). Each child either rejects the candy, or eats one candy (before immediately getting sick and not eating any more candy). For each of the 5 candies, the number of times it is given and the number of times it is eaten are listed below:
- Hazelnut: 2000 given, 1600 children sickened.
- Yellow Lemon: 2200 given, 1600 children sickened.
- Pistachio: 1900 given, 1300 children sickened.
- Strawberry: 2000 given, 1700 children sickened.
- Mint: 1400 given, 1100 children sickened.
Let M be the number of children who were offered exactly one candy, and ate that candy. Find the smallest possible value of M.

Using this value, among the sickened children, compute the proportion of them who were given exactly one candy.

Field: Math
Problem ID: 33
Author: Jewon Im
Effective Date: 9/5/2022
Difficulty: 2 jalapeños, 2 points

Problem statement: 
Approximate how many standard gumballs (1-in diameter) would fit in a half-gallon mason jar (dimensions: 4.33in bottom diameter, 8.66in height, 3.54in upper diameter; 64oz). 

Hint: Kepler conjecture and some common sense about mason jars

Field: Math
Problem ID: 34
Effective Date: 9/28/2022
Difficulty: 2.5 jalapeños

Problem Statement:
A computer selects a number P, chosen uniformly from the interval [0,1] and makes a biased coin that has a probability P of turning up heads.

Suppose that you flip the coin, and it comes up heads 35 times and tails 20 times. What is the probability that the next coin flip will result in a heads?
Note: the bot is down so you should DM the solution to me (Ryan Yang).

Field: Math
Problem ID: 35
Author: Ryan Yang
Effective Date: 12/4/2022
Difficulty: 3 jalapeños, 6 points

Problem Statement:
The organizers of the world cup are planning for 2026 and want to change the number of teams in each group, but still have at least three teams in each group. They also want to keep the same structure and the same total number of games. Currently, there are 8 groups of 4, from which the top 2 advance into a 16 team knockout stage. This has 8*6=48 group stage games + 16 knockout games = 64 total games.

For example, one such alternative is 16 groups of 3, where one team advances from each group. This will have 16*3=48 group stage games and 16 knockout games, for a total of 64 games. There are two other alternatives; three points will be given for each alternative that you submit.

Field: Architecture?
Problem ID: 36
Effective Date 2/6/2023
Difficulty: 2 jalapeños, 3 points

Problem Statement
Find the angle between the two science building walls shown in the attached image. The only three instruments you are allowed to use are
1. a pencil
2. a ruler
3. a calculator

Two points will be given for outlining a solution, and full credit will be given for actually going to the science building (IRL!) and calculating the angle.

https://cdn.discordapp.com/attachments/891482447580123137/1072247291341176962/Screen_Shot_2023-02-06_at_3.06.38_PM.png?ex=6668ae9b&is=66675d1b&hm=c07a2a901f51d05ad0fe8d5a46aa3ca93d3cf6433d52e02427940598e235e460&