This is a mirror/log of the #potw announcements channel.
Welcome to the Choate STEM POTW
Welcome! The Choate STEM Problem of the Week is a server posting student-made problems weekly, broadcasting to all the STEM club Discords at Choate—including CPU, GirlTech, Math, Linguistics, Physics, Chess, and QuizBowl. If you are interested in participating through solving problems in various fields and competing in a leaderboard, please join the server here: https://discord.gg/bFX8ey442d
31: 8/2
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)
30: 7/27
Field: Chess
Problem ID: 30
Author: Ryan Yang (original puzzle!)
Difficulty: 3 jalapenos, 5 points
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
FEN: rnB5/k2N4/N1P5/PpK5/8/8/8/8 w – b6 0 2
(I trust y’all not to use an engine pls)
29: 6/6
Field: ??
Problem ID: 29
Author: Ryan Yang
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)
28: 5/16
Field: Math
Problem ID: 28
Author: Ryan Yang (From Po-Shen Loh Handout)
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.
image:
https://cdn.discordapp.com/attachments/891482447580123137/975950375280599080/unknown.png
27: 5/9
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.
To submit your solution dm the CSP POTW Bot with the message “!submit [answer]”
image:
https://cdn.discordapp.com/attachments/891482447580123137/973352373663727746/unknown.png
26: 4/26
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.
Don’t check POTW 8
25: 4/18
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)
23: 4/12
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
19: 3/15
Field: CS + Stat
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
Note: 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.
18: 2/28
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.
17: 2/21
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.) You must justify your answer in order to receive points. (3 points available)
15: 2/7
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%282%29.pdf?dl=0
14: 2/1
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?
13: January 25th
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.
12: January 17th
Field: CS
Problem ID: 12
Author: Jewon Im
Effective Date: 1/17/2022
Difficulty: 3 jalapeños
Problem statement (Original):
Given an array of integers, explain how you could calculate the standard deviation of any subset in O(1) after doing an O(n) initial calculation.
Layman’s Version:
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.
11: January 11th
Field: Logic
Problem
ID: 11
Proposer: Ryan Yang (from free-sudoku.com)
Effective Date: 1/10/2022
Difficulty: 1 jalapeños
Problem statement: Solve the sudoku. Submit the list of 9 numbers that go along the main NW to SE diagonal. (Should be of the form 7XXXXXXX4)
https://cdn.discordapp.com/attachments/925247394218651659/930245731565076521/1231f334-a58f-4725-8d57-02ede1545619.png
9: December 27th
Field: Math
Problem ID: 9
Proposer: 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)
8: December 13th
Field: CS
Problem ID: 8
Proposer: 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.
6: December 6th
Field: Logic
Problem ID: 6
Proposer: 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)
4: November 23rd
Field: CS
Problem ID: 4
Proposer: 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.
3: November 15th
Field: Math
Problem ID: 3
Proposer: ryang (written by Ireland)
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, 1 point for showing that your method achieves the answer, and 1 point for showing that you need at least that many phone calls.
2: November 8th
Field: CS
Problem ID: 2
Proposer: Jewon Im (credit: Quora)
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.
1: October 27th
Field: Linguistics
Problem
ID: 1
Proposer: David Garsten ’23 (adapted from Doris L Payne)
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.