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
Yesterday at 11:16 PM
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
Yesterday at 11:16 PM
0 replies
Function equation
LeDuonggg   3
N 2 minutes ago by luutrongphuc
Find all functions $f: \mathbb{R^+} \rightarrow \mathbb{R^+}$ , such that for all $x,y>0$:
\[ f(x+f(y))=\dfrac{f(x)}{1+f(xy)}\]
3 replies
+1 w
LeDuonggg
Yesterday at 2:59 PM
luutrongphuc
2 minutes ago
A sequence containing every natural number exactly once
Pomegranat   4
N 11 minutes ago by Pomegranat
Source: Own
Does there exist a sequence \( \{a_n\}_{n=1}^{\infty} \), which is a permutation of the natural numbers (that is, each natural number appears exactly once), such that for every \( n \in \mathbb{N} \), the sum of the first \( n \) terms is divisible by \( n \)?
4 replies
Pomegranat
3 hours ago
Pomegranat
11 minutes ago
hard square root problem
kjhgyuio   0
21 minutes ago
........
0 replies
kjhgyuio
21 minutes ago
0 replies
Queue geo
vincentwant   5
N 38 minutes ago by Ilikeminecraft
Let $ABC$ be an acute scalene triangle with circumcenter $O$. Let $Y, Z$ be the feet of the altitudes from $B, C$ to $AC, AB$ respectively. Let $D$ be the midpoint of $BC$. Let $\omega_1$ be the circle with diameter $AD$. Let $Q\neq A$ be the intersection of $(ABC)$ and $\omega$. Let $H$ be the orthocenter of $ABC$. Let $K$ be the intersection of $AQ$ and $BC$. Let $l_1,l_2$ be the lines through $Q$ tangent to $\omega,(AYZ)$ respectively. Let $I$ be the intersection of $l_1$ and $KH$. Let $P$ be the intersection of $l_2$ and $YZ$. Let $l$ be the line through $I$ parallel to $HD$ and let $O'$ be the reflection of $O$ across $l$. Prove that $O'P$ is tangent to $(KPQ)$.
5 replies
vincentwant
Wednesday at 3:54 PM
Ilikeminecraft
38 minutes ago
System of two matrices of the same rank
Assassino9931   1
N 2 hours ago by RobertRogo
Source: Vojtech Jarnik IMC 2025, Category II, P2
Let $A,B$ be two $n\times n$ complex matrices of the same rank, and let $k$ be a positive integer. Prove that $A^{k+1}B^k = A$ if and only if $B^{k+1}A^k = B$.
1 reply
Assassino9931
5 hours ago
RobertRogo
2 hours ago
Putnam 1952 B1
centslordm   4
N 5 hours ago by Gauler
A mathematical moron is given two sides and the included angle of a triangle and attempts to use the Law of Cosines: $a^2 = b^2 + c^2 - 2bc \cos A,$ to find the third side $a.$ He uses logarithms as follows. He finds $\log b$ and doubles it; adds to that the double of $\log c;$ subtracts the sum of the logarithms of $2, b, c,$ and $\cos A;$ divides the result by $2;$ and takes the anti-logarithm. Although his method may be open to suspicion his computation is accurate. What are the necessary and sufficient conditions on the triangle that this method should yield the correct result?
4 replies
centslordm
May 30, 2022
Gauler
5 hours ago
Miklós Schweitzer 1956- Problem 8
Coulbert   2
N 5 hours ago by izzystar
8. Let $(a_n)_{n=1}^{\infty}$ be a sequence of positive numbers and suppose that $\sum_{n=1}^{\infty} a_n^2$ is divergent. Let further $0<\epsilon<\frac{1}{2}$. Show that there exists a sequence $(b_n)_{n=1}^{\infty}$ of positive numbers such that $\sum_{n=1}^{\infty}b_n^2$ is convergent and

$\sum_{n=1}^{N}a_n b_n >(\sum_{n=1}^{N}a_n^2)^{\frac{1}{2}-\epsilon}$

for every positive integer $N$. (S. 8)
2 replies
Coulbert
Oct 11, 2015
izzystar
5 hours ago
Very straightforward linear recurrence
Assassino9931   1
N 5 hours ago by Etkan
Source: Vojtech Jarnik IMC 2025, Category II, P1
Let $x_0=a, x_1= b, x_2 = c$ be given real numbers and let $x_{n+2} = \frac{x_n + x_{n-1}}{2}$ for all $n\geq 1$. Show that the sequence $(x_n)_{n\geq 0}$ converges and find its limit.
1 reply
Assassino9931
5 hours ago
Etkan
5 hours ago
Integration Bee in Czechia
Assassino9931   0
5 hours ago
Source: Vojtech Jarnik IMC 2025, Category II, P3
Evaluate the integral $\int_0^{\infty} \frac{\log(x+2)}{x^2+3x+2}\mathrm{d}x$.
0 replies
Assassino9931
5 hours ago
0 replies
Trace with minimal polynomial x^n + x - 1
Assassino9931   0
5 hours ago
Source: Vojtech Jarnik IMC 2025, Category I, P4
Let $A$ be an $n\times n$ real matrix with minimal polynomial $x^n + x - 1$. Prove that the trace of $(nA^{n-1} + I)^{-1}A^{n-2}$ is zero.
0 replies
Assassino9931
5 hours ago
0 replies
Fast-growing sequences
Assassino9931   0
5 hours ago
Source: Vojtech Jarnik IMC 2025, Category I, P3
Let us call a sequence $(b_1, b_2, \ldots)$ of positive integers fast-growing if $b_{n+1} \geq b_n + 2$ for all $n \geq 1$. Also, for a sequence $a = (a(1), a(2), \ldots)$ of real numbers and a sequence $b = (b_1, b_2, \ldots)$ of positive integers, let us denote
\[
S(a, b) = \sum_{n=1}^{\infty} \left| a(b_n) + a(b_n + 1) + \cdots + a(b_{n+1} - 1) \right|.
\]
a) Do there exist two fast-growing sequences $b = (b_1, b_2, \ldots)$, $c = (c_1, c_2, \ldots)$ such that for every sequence $a = (a(1), a(2), \ldots)$, if all the series
\[
    \sum_{n=1}^{\infty} a(n), \quad S(a, b) \quad \text{and} \quad S(a, c)
    \]are convergent, then the series $\sum_{n=1}^{\infty} |a(n)|$ is also convergent?

b) Do there exist three fast-growing sequences $b = (b_1, b_2, \ldots)$, $c = (c_1, c_2, \ldots)$, $d = (d_1, d_2, \ldots)$ such that for every sequence $a = (a(1), a(2), \ldots)$, if all the series
\[
    S(a, b), \quad S(a, c) \quad \text{and} \quad S(a, d)
    \]are convergent, then the series $\sum_{n=1}^{\infty} |a(n)|$ is also convergent?
0 replies
Assassino9931
5 hours ago
0 replies
Strange ring property
sapience   2
N Yesterday at 11:48 PM by RobertRogo
Let \( (A, +, \cdot) \) be a ring with \( Z(A) \) its centre (\( Z = \{ x \in A \mid xy = yx \text{ for any } x, y \in A \} \)), \( U(A) \) the set of invertible elements and \( A^* = A \setminus \{0\} \).
We will say \(A\) has the property \( \mathcal{P} \) if there exists a subgroup \(H \) of group \( (U(A), \cdot) \) such that \( H \subset Z(A) \), \( H \neq A^* \) and \( x^3 = y^3 \) for any \( x, y \in A^* \setminus H \).
Prove the following:
a) any ring with property \( \mathcal{P} \) is commutative;
b) if \(A \) has the property \( \mathcal{P} \), then \( x^3 = 0 \), for any \( x \in A \setminus U(A) \).

Note: \(0 \) and \(1 \) are the identity elements for \(+ \) and \(\cdot \)
2 replies
sapience
Mar 5, 2025
RobertRogo
Yesterday at 11:48 PM
real analysis
ILOVEMYFAMILY   1
N Yesterday at 5:04 PM by Alphaamss
Source: real analysis
For which value of $p\in\mathbb{R}$ does the series $$\sum_{n=1}^{\infty}\ln \left(1+\frac{(-1)^n}{n^p}\right)$$converge (and absolutely converge)?
1 reply
ILOVEMYFAMILY
Dec 2, 2023
Alphaamss
Yesterday at 5:04 PM
Putnam 1962 B5
sqrtX   4
N Yesterday at 4:56 PM by centslordm
Source: Putnam 1962
Prove that for every integer $n$ greater than $1:$
$$\frac{3n+1}{2n+2} < \left( \frac{1}{n} \right)^{n} + \left( \frac{2}{n} \right)^{n}+ \ldots+\left( \frac{n}{n} \right)^{n} <2.$$
4 replies
sqrtX
May 21, 2022
centslordm
Yesterday at 4:56 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
420 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
1521 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
344 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
1261 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
2982 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
611 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
389 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
574 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
198 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
611 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