potw solutions
spoilers! similar to how the other potw solution is a parallel of #potw annoucnements channel, this is a mirror of #solutions.
30 (Constrained Chess Position)
The only way to get to this position is for black to have just moved their pawn forward two squares. Thus, en-passant is legal. Executing en-passant gives you mate in one.
29 (Titles do not define a poset)
There are many possible triples. The simplest one is:
a phd student X < X’s PI professor < X’s PhD advisor’s mom < X
28 (Cross Products)
Note that Ax(A+B+C) = 0 + AxB + AxC = 0 + AxB – (CxA) = 0. Similarly, Bx(A+B+C)=Cx(A+B+C)=0. Thus, A+B+C,A, B, C are all orthogonal which is clearly impossible since we’re in 3d space. Thus, A+B+C=0.
27 (NT from a deck)
consider consecutive primes p,q. then, 2 divides p+q since both are odd. in addition, (p+q)/2 is between p,q and thus cannot be prime. thus, p+q has at least 3 prime factors
26 (CAMO 2022/4)
our main tool is testing a line of cells, finding the minimum M along the cells, testing the two values next to M, and which ever side is smaller contains the minima. binary sort creating smaller and smaller rectangles like this uses roughly (n+n/2)+(n/2+n/4)+….. = 3n moves.
codeforces:
https://codeforces.com/gym/102341/problem/C
CAMO 2022/4
https://artofproblemsolving.com/community/c3012737
25 (IOI 2016/1)
official IOI solution:
https://ioinformatics.org/files/ioi2016solutions.pdf
24 (President’s Day)
Blogpost explaining how I predicted Presidents’ Day:
https://ryanyang.us/?p=1155
23 (Matchstick-ish)
turn 35+4=5 into 5+4=9 by moving the 3
22
NA: skipped 22
21 (Quadrilateral Geo)
Source: Princeton 2014
Solution:
note that the order doesn’t actually matter. In fact, this quadrilateral fits in a circle with diameter sqrt(65)
20 (Korean Number Puzzle)
The pattern within 115, 15, 16, 19 is that you are overlaying a 1 on a 15 at different positions (slowly shifting the 1 to the right). For the next value, you place it to the right of the 15, giving 151
19 (Monte Carlo)
I’m actually not quite sure about this one, stats is weird.
Variance is ~1/n and standard deviation is ~1/sqrt(n). Thus, the standard error is ~1/n, and thus the range of the confidence interval is proportional to the inverse of the number of samples.
18 (2022 Cubes Make A Cube)
13^3=2197=2022+7*25. Thus, starting with 2022 1s and replacing 25 1s with 8s works.
17 (Cutting Cake)
Sol 1: consider the circumcentre O. Cut OA,OB, and OC.
Sol 2:, consider incenter I. Cut the altitudes from I to the three sides
16 (Geometry)
Let X be the intersection of the circle and AB. Then, by “Power of a Point”, AX* AB = AE^2. Since AE = 1/2x, AB=x, we have AX = 1/4 * x, and XB = 3/4 * x. By the Pythagorean theorem, XC = 5/4 * x. The circumference is pi times this, so the answer was 5/4 pi x
15 (Blotto)
My setup (which won the MOP blotto round):
18 18 4
4 36 4
4 4 18
14
Geometric Solution from Deven:
https://cdn.discordapp.com/attachments/891482157040693308/940731492907229205/IMG_1177.png
13 (David’s Linguistics Problem)
David’s Solutions:
10) What do I hope for? I hope for dreams.
11) Is it snowing here? Yes, it is snowing here.
2a. Is math taught by Michael? No, math isn’t taught by Michael.
2b. Who has passion? Humans have passion.
2c. Who thinks they’re a magician? Sam thinks he’s a magician.
easter eggs:
‘math’ rddarsugurda is from number-group.
‘dog’ koba also means ‘chase’, and ‘dream’ jewokoba means night-chase.
‘human’ paqaka is from meat-person
‘magician’ machika is from mist-person.
12 (Efficient Variance Queries)
The main idea was to keep a “prefix sum”. This allows one to query in O(1) the sum of the elements in a subsequence, or the sum of the squares of the element. Then, using the formula for standev = sqrt(variance), and
variance = 1/m * sum(squares) – (1/m * sum() )^2
you can calculate the standard deviation.
Code:
https://www.dropbox.com/s/qq5b2lqgempsmiw/12standev.py?dl=0
11 (Sudoku)
762583614
10 (Chess)
Qf2+ Kh1 Q×f1+ R×f1 R×f1#
9 (Espen’s Favorite Problem)
2021 mc3 p6: https://mathcircle.berkeley.edu/sites/default/files/handouts_mc/problems/2021/mc3.pdf
8
Binary search, O(log n), can find local min through a “ball rolling down a hill” analogy
7
skipped accidentally
6
(1) 99
(2) 14
(3) 7
5
sketch sol:
https://cdn.discordapp.com/attachments/891482157040693308/917615554402082816/Screen_Shot_2021-12-06_at_10.16.04_PM.png
4
Using 10^9+7: 976496506
Using 10^9+9: 938346009
Acceptable optimization method names: dynamic programming, recursive dynamic programming/memoization, iterative/bottom-up dynamic programming, Binet’s formula
Sample code using memoization, O(n) (lang c++, author Jewon):
#include
#define modulo 1000000009
using namespace std;
long long dp[5005];
long long fib(int n) {
if(!dp[n]) dp[n] = (fib(n – 1) + fib(n – 2)) % modulo;
return dp[n];
}
int main() {
dp[1] = dp[2] = 1;
cout << fib(5000) << endl;
}
Sample code using Binet’s formula, O(log n) (lang python, author ryang):
p = 10**9+9
sqrt = 0
for i in range(p):
if((i*i %p)== 5):
sqrt=i #45,56 are the values that work
break
n=5000
a = (1+sqrt) * pow(2,-1,p)
b = (1-sqrt) * pow(2,-1,p)
Fn = (pow(sqrt,-1,p)* (pow(a,n,p) – pow(b,n,p)) )% p
print(Fn)
3
We claim the answer is $2n-2$. The construction is: In the first $n-1$ moves everyone tells person $A$ their information, and in the next $n-1$ moves $A$ tells everyone everything.
Proof 1: We now prove that this is optimal. Call someone “wise” if they know all of the information.
Firstly, clearly at least $n-1$ moves are needed before someone is wise. After this has happened, we still need at least $n-1$ moves until everyone is wise because each move can only increase the number of wise people by 1.
Thus, at least
(n-1)+(n-1)=2n-2 moves are needed
and we’re done. []
Proof 2 (not mine):
$2n-2$ is constructible by having person $k$ call $k+1$ for $k = 1, 2, ldots n-1$, after which person $n$ knows all the information ($n-1$ calls). Then person $n$ calls each person up and tells them, for $n-1$ more calls.
To show at least $2n-2$ calls are needed: After $n-1$ calls, no matter how they are done, some person, WLOG person $n$, hasn’t called anyone. In each subsequent call only one more person can learn person $n$’s information, and there are $n-1$ people that need to know. So after the first $n-1$ calls, you need at least $n-1$ more calls for everyone to learn what person $n$ knows. That gives $2n-2$ as a lower bound
Source: https://artofproblemsolving.com/community/c6h479048p2682355
2
(lang c++)
#include
using namespace std;
int main() {
string one = “.”;
string twenty = “………………..”;
for(int i = one.length(); i <= twenty.length(); i++) {
cout << i << endl;
}
}
(lang brainfuck)
++++++++++[>+++++>+++++>+>+>+<<<<<-]>->–>>[<<.+>.>-]<<———->>>[<<<<.>.+>.>>-]<<<<+.–.
1
1G 2H 3E 4F 5I 6D 7J 8B 9A 10C