Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
May 1, 2025
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
May 1, 2025
0 replies
Romanian National Olympiad 1997 - Grade 9 - Problem 2
Filipjack   1
N 6 minutes ago by Mathzeus1024
Source: Romanian National Olympiad 1997 - Grade 9 - Problem 2
Find the range of the function $f: \mathbb{R} \to \mathbb{R},$ $$f(x)=\frac{3+2\sin x}{\sqrt{1+\cos x}+\sqrt{1-\cos x}}.$$
1 reply
Filipjack
Apr 6, 2025
Mathzeus1024
6 minutes ago
Computing functions
BBNoDollar   4
N 12 minutes ago by ICE_CNME_4
Let $f : [0, \infty) \to [0, \infty)$, $f(x) = \dfrac{ax + b}{cx + d}$, with $a, d \in (0, \infty)$, $b, c \in [0, \infty)$. Prove that there exists $n \in \mathbb{N}^*$ such that for every $x \geq 0$
\[
f_n(x) = \frac{x}{1 + nx}, \quad \text{if and only if } f(x) = \frac{x}{1 + x}, \quad \forall x \geq 0.
\](For $n \in \mathbb{N}^*$ and $x \geq 0$, the notation $f_n(x)$ represents $\underbrace{(f \circ f \circ \dots \circ f)}_{n \text{ times}}(x)$. )
4 replies
BBNoDollar
Yesterday at 5:25 PM
ICE_CNME_4
12 minutes ago
Nice concurrency
navi_09220114   1
N 14 minutes ago by bin_sherlo
Source: TASIMO 2025 Day 1 Problem 2
Four points $A$, $B$, $C$, $D$ lie on a semicircle $\omega$ in this order with diameter $AD$, and $AD$ is not parallel to $BC$. Points $X$ and $Y$ lie on segments $AC$ and $BD$ respectively such that $BX\parallel AD$ and $CY\perp AD$. A circle $\Gamma$ passes through $D$ and $Y$ is tangent to $AD$, and intersects $\omega$ again at $Z\neq D$. Prove that the lines $AZ$, $BC$ and $XY$ are concurrent.
1 reply
navi_09220114
32 minutes ago
bin_sherlo
14 minutes ago
k-triangular sets
navi_09220114   0
21 minutes ago
Source: TASIMO 2025 Day 2 Problem 6
For an integer $k\geq 1$, we call a set $\mathcal{S}$ of $n\geq k$ points in a plane $k$-triangular if no three of them lie on the same line and whenever at most $k$ (possibly zero) points are removed from $\mathcal{S}$, the convex hull of the resulting set is a non-degenerate triangle. For given positive integer $k$, find all integers $n\geq k$ such that there exists a $k$-triangular set consisting of $n$ points.

Note. A set of points in a Euclidean plane is defined to be convex if it contains the line segments connecting each pair of its points. The convex hull of a shape is the smallest convex set that contains it.
0 replies
navi_09220114
21 minutes ago
0 replies
System of Equations
P162008   0
2 hours ago
If $a,b$ and $c$ are complex numbers such that

$\frac{ab}{b + c} + \frac{bc}{c + a} + \frac{ca}{a + b} = -9$

$\frac{ab}{c + a} + \frac{bc}{a + b} + \frac{ca}{b + c} = 10$

Compute $\frac{a}{c + a} + \frac{b}{a + b} + \frac{c}{b + c}.$
0 replies
P162008
2 hours ago
0 replies
System of Equations
P162008   0
2 hours ago
If $a,b$ and $c$ are complex numbers such that

$\sum_{cyc} ab = 23$

$\frac{a}{c + a} + \frac{b}{a + b} + \frac{c}{b + c} = -1$

$\frac{a^2b}{b + c} + \frac{b^2c}{c + a} + \frac{c^2a}{a + b} = 202$

Compute $\sum_{cyc} a^2.$
0 replies
P162008
2 hours ago
0 replies
2022 MARBLE - Mock ARML I -8 \frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}=32
parmenides51   3
N 2 hours ago by P162008
Let $a,b,c$ complex numbers with $ab+ +bc+ca = 61$ such that
$$\frac{1}{b+c}+\frac{1}{c+a}+\frac{1}{a+b}= 5$$$$\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}=32.$$Find the value of $abc$.
3 replies
parmenides51
Jan 14, 2024
P162008
2 hours ago
ISI 2025
Zeroin   1
N 2 hours ago by alexheinis
Let $\mathbb{N}$ denote the set of natural numbers and let $(a_i,b_i),1 \leq i \leq 9$ denote $9$ ordered pairs in $\mathbb{N} \times \mathbb{N}$. Prove that there exist $3$ distinct elements in the set $2^{a_i}3^{b_i}$ for $1 \leq i \leq 9$ whose product is a perfect cube.
1 reply
Zeroin
Yesterday at 2:29 PM
alexheinis
2 hours ago
Pell's Equation
Entrepreneur   1
N 3 hours ago by MihaiT
A Pells Equation is defined as follows $$x^2-1=ky^2.$$Where $x,y$ are positive integers and $k$ is a non-square positive integer. If $(x_n,y_n)$ denotes the n-th set of solution to the equation with $(x_0,y_0)=(1,0).$ Then, prove that $$x_{n+1}x_n-ky_{n+1}y_n=x_1,$$$$x_n\pm y_n\sqrt k=(x_1\pm y_1\sqrt k)^n.$$
1 reply
Entrepreneur
4 hours ago
MihaiT
3 hours ago
Inequalities
sqing   15
N 4 hours ago by sqing
Let $a,b,c >2 $ and $ ab+bc+ca \leq 75.$ Show that
$$\frac{1}{a-2}+\frac{1}{b-2}+\frac{1}{c-2}\geq 1$$Let $a,b,c >2 $ and $ \frac{1}{a}+\frac{1}{b}+\frac{1}{c}\geq \frac{6}{7}.$ Show that
$$\frac{1}{a-2}+\frac{1}{b-2}+\frac{1}{c-2}\geq 2$$
15 replies
sqing
May 13, 2025
sqing
4 hours ago
Pertenacious Polynomial Problem
BadAtCompetitionMath21420   6
N Today at 3:51 AM by lbh_qys
Let the polynomial $P(x) = x^3-x^2+px-q$ have real roots and real coefficients with $q>0$. What is the maximum value of $p+q$?

This is a problem I made for my math competition, and I wanted to see if someone would double-check my work (No Mike allowed):

solution
Is this solution good?
6 replies
BadAtCompetitionMath21420
May 17, 2025
lbh_qys
Today at 3:51 AM
Vieta's Formula.
BlackOctopus23   4
N Today at 3:11 AM by compoly2010
Can someone help me understand Vieta's Formula? I am currently learning it for my class. I learned that for a polynomial of degree $n$, all the roots added will give $-\frac{a_{n-1}}{a_n}$. I also learned that if every single root, multiplies every single root, it will give $\frac{a_{n-2}}{a_n}$. I also learned that if all the roots are multiplied, it will give $-\frac{a_0}{a_n}$. Is this right? And is there any purpose for these equations?
4 replies
BlackOctopus23
Yesterday at 11:10 PM
compoly2010
Today at 3:11 AM
The sum of 335 distinct positive integers
Streit31415   1
N Today at 12:36 AM by Bocabulary142857
The sum of 335 distinct positive integers is equal to 100000
a) what is the minimum number of odd numbers among them ?
b) what is the maximum number of odd numbers among them ?
1 reply
Streit31415
Yesterday at 11:38 PM
Bocabulary142857
Today at 12:36 AM
Diophantine Equation (cousin of Mordell)
urfinalopp   4
N Yesterday at 10:54 PM by FoeverResentful
Find pairs of integers $(x;y)$ such that:

$x^2=y^5+32$
4 replies
urfinalopp
Yesterday at 6:38 PM
FoeverResentful
Yesterday at 10:54 PM
Guess the leader's binary string!
cjquines0   80
N Apr 25, 2025 by Ilikeminecraft
Source: 2016 IMO Shortlist C1
The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) The contestant is allowed to look at the strings written by the deputy leader and guess the leader’s string. What is the minimum number of guesses (in terms of $n$ and $k$) needed to guarantee the correct answer?
80 replies
cjquines0
Jul 19, 2017
Ilikeminecraft
Apr 25, 2025
Guess the leader's binary string!
G H J
G H BBookmark kLocked kLocked NReply
Source: 2016 IMO Shortlist C1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Sagnik123Biswas
421 posts
#70
Y by
If $n=2k$, then it takes $2$ moves. Otherwise $1$ move. We can recover each bit by making use of the fact that $\binom{n-1}{k} \neq \binom{n-1}{k-1}$ when $2k \neq n$. However when $n=2k$, the the produced list anyways has $2$ possible generators. So we do casework, and are able to get it in $2$ moves.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathLuis
1545 posts
#71
Y by
Note that we are given $\binom{n}{k}$ strings, consider one fixed position in each of them, by an easy counting we know that $\binom{n-1}{k}$ strings will have this digit in the right position and $\binom{n-1}{k-1}$ of them will have this digit changed, now if $n \ne 2k$ then since those two quantities are different we can easly differenciate them and thus re-construct the original string in only 1 guess. But if $n=2k$ then note that if we swap all the digits in the leader's binary string then after repeating the process we get that the deputy leader shares to the student the same list of binary strings as the string un-swapped, therefore, there is exactly 2 possible outcomes both correct from what the deputy leader gives to the student, and as a result the student is forced to make at least 2 guesses, now to achieve exactly 2 guesses just do the following, take all $k+1$ strings where the last $k-1$ digits remain fixed, and now we have two outcomes, one is assuming that those $k-1$ have all changed and that among the $k+1$ strings exactly one digit changes each time thus the student can guess one only string, on the other hand the student can assume that those $k-1$ digits never suffered a change and each time among those $k+1$ strings, $k$ strings change, giving a inverted string compared to your first choice, it is clear that by what we have seen, one of these two strings is correct so it takes at most 2 guesses.
Therefore the minimun for $n \ne 2k$ is 1 and for $n=2k$ is 2 thus we are done :cool:.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blueprimes
356 posts
#72
Y by
We claim the answer is $1$ for $n \ne 2k$ and $2$ when $n = 2k$.

$\textbf{Case 1: } n \ne 2k$
Note that among the $\binom{n}{k}$ strings, for each digit, it stays the same in $\binom{n - 1}{k}$ strings and toggles in $\binom{n - 1}{k - 1}$. Since $\binom{n - 1}{k} \ne \binom{n - 1}{k - 1}$, we can uniquely identify the digit in the original string by simply counting the number of instances of $0$s and $1$s. This yields $1$ as the minimum number of guesses.

$\textbf{Case 2: } n = 2k$
First we show that we cannot get the correct answer in $1$ guess. Let $s$ be the chosen $n$-digit binary string, and let $s'$ be the string $s$ when all of its digits are toggled. We claim that both $s$ and $s'$ yield the same list, say $\ell$, of altered strings. This is easy to see: Given any alteration of $k$ digits on $s$, a unique equivalent alteration exists for $s'$ by simply toggling the other $k$ digits.

We will now also show that $s$ and $s'$ are the only two strings that can generate this list $\ell$. By considering a constant binary vector shift, we can WLOG $s$ is the all-$0$ string and $s'$ is the all-$1$ string. But all strings in $\ell$ have precisely $k$ $0$s which is impossible to achieve with any other strings.

Now to show that we can get the correct answer in at most $2$ attempts, just generate the list over all strings and see what works. By our above claim, we get it in at most $2$ tries.

We are done!
This post has been edited 1 time. Last edited by blueprimes, Feb 18, 2025, 6:43 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ezpotd
1279 posts
#73
Y by
We claim the answer is $1$ if $n \neq 2k$ and $2$ otherwise.

Case if $n = 2k$: For every string, the string formed by inverting each bit is present in the set, so by symmetry we require at least $2$ attempts. To prove that $2$ attempts is sufficient, consider the first half of the string. For each subset of $i$ bits of the first half, there are $\binom ki \binom{k}{k - i}$ strings with these $i$ bits inverted. There are thus only two distinct strings that have a unique first half, one of which that has all of the first half inverted and one with none. Thus it suffices to take the first half of all the strings and only note the two strings that have no matches in the list. Out of these, one is the correct string with the first half inverted and the second is the correct string with the second half inverted. We do not know which one. Invert the first half of both of these, then one of them is the correct answer.

Case if $n \neq 2k$: For each bit, we can determine the inverted form appears $\binom{n - 1}{k - 1}$ times in the list and the correct form appears $\binom{n - 1}{k}$ times, and since these values are guaranteed to be distinct by $n \neq 2k$, we can uniquely determine each bit correctly on the first try.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lpieleanu
3001 posts
#74
Y by
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
eg4334
637 posts
#75
Y by
The answer is $\boxed{1, n \neq 2k}$ and $\boxed{2, n = 2k}$
If $n \neq 2k$, then for each index of the string the correct one appears $\binom{n-1}{k}$ and the incorrect one appears $\binom{n-1}{k-1}$. Therefore the correct one can always be deduced.
This argument fails however when $\binom{n-1}{k} = \binom{n-1}{k-1} \implies n = 2k$. In this case, clearly the string and its complement both work so we require two guesses. To achieve this, simply fix the first digit and use the same argument above on the rest of the string. For example consider $n=6, k=3$ with the string $101110$. If the first digit truly is $1$, then we know the first two digits are correct in $\binom{4}{3}$ ways but the first digit is correct and second digit incorrect in $\binom{4}{2}$ ways. Thus we can deduce the second digit and in a similar fashion the rest of the sting. The case where the first digit is incorrect gives the other case, so we are done.
This post has been edited 1 time. Last edited by eg4334, Dec 10, 2024, 1:33 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cursed_tangent1434
636 posts
#76
Y by
First notice that the $n^{th}$ digit will be flipped in $$\binom{n-1}{k-1}$$of the given binary strings. So unless $$\binom{n-1}{k-1} = \frac{\binom{n}{k}}{2}\implies n=2k$$Po-Shen can directly find what each digit must be and in find the correct string in 1 guess. Now, suppose $n=2k$. Notice half the binary strings given will end in 0 and the other half in 1. Now, consider the remaining $n-1$ digits of each binary string. Assume that the last digit was flipped and became $x \in {0,1}$. Then, of first $n-1$ digits in the $\frac{\binom{n}{k}}{2}$ strings ending with $x$, we will have $k-1$ digits being flipped, which is identical to the case when Titu selects $n-1$ and $k-1$ and since clearly $n-1 \neq \frac{k-1}{2}$ the first $n-1$ digits can be determined in 1 guess. Thus, Po-Shen has to guess the last digit (with two options) requiring 2 guesses in total to hit the right answer.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Eka01
204 posts
#77
Y by
Solved with a slight hint/being told that I was wrong.
Obviously the number of strings written by deputy leader are $\binom{n}{k}$. For a particular place, the number of strings where it has the correct digit is $\binom{n-1}{k}$ so if the number of places it is written incorrectly is not equal to the number of places it is written correctly, then the contestant can uniquely determine all the places without leaving anything to chance. A quick calculation shows that this happens iff $n \neq 2k$. If $n=2k$, then fix any digit, say the foremost one, then if we fixed the correct digit, then we can instead view the case as being given a string of length $n-1$ and all the strings varying from this in $\frac{n}{2}$ places. Otherwise, we can view it as being given a string of length $n-1$ varying in $\frac{n-2}{2}$ places. In each of these cases, the contestant needs just one attempt, hence $2$ guesses are sufficient for the $n=2k$ case.
This post has been edited 1 time. Last edited by Eka01, Dec 28, 2024, 7:44 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
smileapple
1010 posts
#78
Y by
If $n\neq 2k$, then $1$ guess suffices. Specifically, Po-Shen can look at the $i$th bit across all $\binom{n}k$ strings written down. The original bit will appear $\binom{n-1}k$ times and the flipped bit will appear $\binom{n-1}{k-1}\neq\binom{n-1}k$ times as $n\neq 2k$. Hence Po-Shen can extract the $i$th bit of the original string for all $i$ and obtain the correct answer.

If $n=2k$, then $2$ guesses is the minimum. Note that $2$ guesses are necessary as both Titu's original string and its complement, with all bits flipped, fit Zuming's description. On the other hand, if the first bit is determined, then Po-Shen can reduce the situation to one with $n'=2k-1$ by considering only the $\binom{n-1}k$ matching strings and throwing away the rest, extracting the other $n-1$ bits. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
NTguy
23 posts
#79 • 1 Y
Y by alexanderhamilton124
Very cool problem, there are $\binom{n}{k}$ total strings, and in $\binom{n-1}{k-1}$ of them, a particular digit will have been changed. So, for each digit we need to count the number of strings where it is $0$ and $1$. Whichever of $0$ and $1$ comes $\binom{n}{k} - \binom{n-1}{k-1}$ times is the correct digit. The only problem arises when $\binom{n}{k} = 2\cdot \binom{n-1}{k-1}$ which is true iff $n=2k$. For this case, first assume the first digit in the leader's string is $1$. Then, in the $\binom{n-1}{k-1}$ strings which have $0$ as the first digit, we know that the first digit has changed, leaving an $n-1$ digit number with $k-1$ digits changed. This is the same as the case of $n \neq 2k$. So, from this we can deduce the entire string and guess it. If it is wrong, we know that the first digit is $0$, and repeat this process. So, for $n=2k$ we require $2$ guesses and for $n \neq 2k$ we require only $1$ guess.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
alexanderhamilton124
400 posts
#80
Y by
For $n$ odd, and for $n$ even and $k \neq \frac{n}{2}$, the answer is $1$. Consider any digit place. The right digit occurs $\binom{n - 1}{k}$ times in this place, and the wrong one appears $\binom{n - 1}{k - 1}$. These two are clearly not equal for this case, so the contestant simply picks the one that apears $\binom{n - 1}{k}$ times for each digit, which gives us one guess.

For $n = 2k$, we can't do it in one guess. This is because if the leader gives the string which is different from this string in all places, we get the same set of strings. We now prove we can do it in two guesses. Randomly pick the first digit. Consider a digit place. The right digit will appear $\binom{n - 2}{k}$ times and the wrong one will appear $\binom{n - 2}{k - 1}$ times (even if the first digit is wrong, the digits in this place will have the same number of occurrences in the reverse order). These two aren't equal since $n - 2$ is even, so pick the one that appears $\binom{n - 2}{k}$ times for each digit place. Give this as the answer. If it's wrong, that means we picked the first digit wrong and then simply do this with the second digit.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maximilian113
575 posts
#81
Y by
Note that swapping $k$ with $n-k$ and vice versa yield equivalent cases, so WLOG assume that $k \leq \frac{n}{2}.$

If $n \neq 2k,$ we have $2k < n.$ Therefore there are multiple pairs of strings that differ at $2k$ places, those places must be where a bit flipped. Therefore in the other positions the bits must not have changed, therefore we can determine them. And, since we have all $\binom{n}{k}$ strings it follows that we can use this method to uniquely determine the original string, so $\boxed{1}$ guess.

If $n = 2k,$ we can look at pairs of strings that differ by $n-2$ places. Then, for the other $2$ places, one of them must have been changed twice, while the other one has to have been original. Therefore if we fix the first digit, taking all pairs of such strings and analyzing the pairs of unchanged bits allows us to determine the string. Hence we have at most $\boxed{2}$ possibilites as there were $2$ possibilites for the first digit.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
de-Kirschbaum
201 posts
#82
Y by
We claim that the contestant can guess it in $1$ if $k \neq \frac{n}{2}$ and $2$ if $k=\frac{n}{2}$.

If $k \neq \frac{n}{2}$ then we know that each digit will be flipped $\binom{n-1}{k-1}$ times and be correct $\binom{n}{k}-\binom{n-1}{k-1}=\binom{n-1}{n-k-1} \neq \binom{n-1}{k-1}$ times. Thus at each digit the contestant can look at all of the binary strings written and pick the digit that appears $\binom{n-1}{n-k-1}$ times and that gives them the correct bit.

If $k=\frac{n}{2}$ then we know that $\binom{n-1}{n-k-1}=\binom{n-1}{k-1}$ so the contestant can no longer pick the correct digit just by looking at the number of times they appear. However, the contestant can guess the first bit to be $1$ or $0$ (unflipped) and then assume the rest of the $n-1$ bits are flipped in $\frac{n}{2}$ places, then following the strategy in the previous case the contestant can guess a number according to that. If the first bit was guessed correctly, then the contestant will recover the original string following this method because then obviously all the flips must happen in the $n-1$ bits. If the first bit was guessed incorrectly, the contestant will recover the complement of the original string, but either way since the first bit is either $1$ or $0$ it takes two guesses to guarantee the original string.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
gladIasked
648 posts
#83
Y by
flavortext :P
If $n=2k$, then Po-Shen needs two guesses. Otherwise, he only needs one guess.

Note that if Po-Shen focuses on a single digit, there are exactly $n-1\choose k$ strings with that digit being ``correct" and exactly $n-1\choose k-1$ strings with that digit being ``incorrect." As long as ${n-1\choose k} \ne {n-1\choose k-1}\iff n\ne2k$, Po-Shen is able to determine the correct digits and the original string.

If $n=2k$, then Po-Shen can randomly guess the ``correct" first digit and determine the ``correct" values of the remaining digits (assuming that his guess was correct). If his guess was incorrect, the Po-Shen can simply choose the other possible value for the first digit and determine the original string. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ilikeminecraft
658 posts
#84
Y by
For the $i^{\text{th}}$ position, we have $\binom{n - 1}{k}$ strings for it to be correct, and $\binom{n - 1}{k - 1}$ for it to be wrong. Hence, if $\binom{n - 1}{k - 1} = \binom{n - 1}{k},$ then they require 2 steps, and 1 otherwise. However, we have ethat this condition holds if and only if $n = 2k.$ Thus, our answer is $1$ if $n \neq 2k,$ and $2$ otherwise.
Z K Y
N Quick Reply
G
H
=
a