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
Point inside parallelogram
BigSams   21
N 3 minutes ago by Want-to-study-in-NTU-MATH
Source: Canadian Mathematical Olympiad - 1997 - Problem 4.
The point $O$ is situated inside the parallelogram $ABCD$ such that $\angle AOB+\angle COD=180^{\circ}$. Prove that $\angle OBC=\angle ODC$.
21 replies
BigSams
May 7, 2011
Want-to-study-in-NTU-MATH
3 minutes ago
Geometry
MathsII-enjoy   1
N 5 minutes ago by MathsII-enjoy
Given triangle $ABC$ inscribed in $(O)$ with $M$ being the midpoint of $BC$. The tangents at $B, C$ of $(O)$ intersect at $D$. Let $N$ be the projection of $O$ onto $AD$. On the perpendicular bisector of $BC$, take a point $K$ that is not on $(O)$ and different from M. Circle $(KBC)$ intersects $AK$ at $F$. Lines $NF$ and $AM$ intersect at $E$. Prove that $AEF$ is an isosceles triangle.
1 reply
MathsII-enjoy
May 15, 2025
MathsII-enjoy
5 minutes ago
Probably a good lemma
Zavyk09   5
N 13 minutes ago by Orzify
Source: found when solving exercises
Let $ABC$ be a triangle with circumcircle $\omega$. Arbitrary points $E, F$ on $AC, AB$ respectively. Circumcircle $\Omega$ of triangle $AEF$ intersects $\omega$ at $P \ne A$. $BE$ intersects $CF$ at $I$. $PI$ cuts $\Omega$ and $\omega$ at $K, L$ respectively. Construct parallelogram $KFRE$. Prove that $A, R, L$ are collinear.
5 replies
Zavyk09
Yesterday at 12:50 PM
Orzify
13 minutes ago
System of Equations
P162008   0
37 minutes 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
37 minutes ago
0 replies
D1033 : A problem of probability for dominoes 3*1
Dattier   1
N 38 minutes ago by Dattier
Source: les dattes à Dattier
Let $G$ a grid of 9*9, we choose a little square in $G$ of this grid three times, we can choose three times the same.

What the probability of cover with 3*1 dominoes this grid removed by theses little squares (one, two or three) ?
1 reply
Dattier
May 15, 2025
Dattier
38 minutes ago
2022 MARBLE - Mock ARML I -8 \frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}=32
parmenides51   3
N an hour 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
an hour ago
ISI 2025
Zeroin   1
N an hour 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
an hour ago
Pell's Equation
Entrepreneur   1
N 2 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
3 hours ago
MihaiT
2 hours ago
Inequalities
sqing   15
N 2 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
2 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
p+2^p-3=n^2
tom-nowy   1
N Yesterday at 6:51 PM by urfinalopp
Let $n$ be a natural number and $p$ be a prime number. How many different pairs $(n, p)$ satisfy the equation:
$$p + 2^p - 3 = n^2 .$$
Inspired by https://artofproblemsolving.com/community/c4h3560823
1 reply
tom-nowy
Yesterday at 11:16 AM
urfinalopp
Yesterday at 6:51 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