It's February and we'd love to help you find the right course plan!

G
Topic
First Poster
Last Poster
k a February Highlights and 2025 AoPS Online Class Information
jlacosta   0
Feb 2, 2025
We love to share what you can look forward to this month! The AIME I and AIME II competitions are happening on February 6th and 12th, respectively. Join our Math Jams the day after each competition where we will go over all the problems and the useful strategies to solve them!

2025 AIME I Math Jam: Difficulty Level: 8* (Advanced math)
February 7th (Friday), 4:30pm PT/7:30 pm ET

2025 AIME II Math Jam: Difficulty Level: 8* (Advanced math)
February 13th (Thursday), 4:30pm PT/7:30 pm ET

The F=ma exam will be held on February 12th. Check out our F=ma Problem Series course that begins February 19th if you are interested in participating next year! The course will prepare you to take the F=ma exam, the first test in a series of contests that determines the members of the US team for the International Physics Olympiad. You'll learn the classical mechanics needed for the F=ma exam as well as how to solve problems taken from past exams, strategies to succeed, and you’ll take a practice F=ma test of brand-new problems.

Mark your calendars for all our upcoming events:
[list][*]Feb 7, 4:30 pm PT/7:30pm ET, 2025 AIME I Math Jam
[*]Feb 12, 4pm PT/7pm ET, Mastering Language Arts Through Problem-Solving: The AoPS Method
[*]Feb 13, 4:30 pm PT/7:30pm ET, 2025 AIME II Math Jam
[*]Feb 20, 4pm PT/7pm ET, The Virtual Campus Spring Experience[/list]
AoPS Spring classes are open for enrollment. Get a jump on 2025 and enroll in our math, contest prep, coding, and science classes today! Need help finding the right plan for your goals? Check out our recommendations page!

Don’t forget: Highlight your AoPS Education on LinkedIn!
Many of you are beginning to build your education and achievements history on LinkedIn. Now, you can showcase your courses from Art of Problem Solving (AoPS) directly on your LinkedIn profile! Don't miss this opportunity to stand out and connect with fellow problem-solvers in the professional world and be sure to follow us at: https://www.linkedin.com/school/art-of-problem-solving/mycompany/ Check out our job postings, too, if you are interested in either full-time, part-time, or internship opportunities!

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
Monday, Feb 3 - May 19
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10

Prealgebra 1 Self-Paced

Prealgebra 2
Sunday, Feb 16 - Jun 8
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10

Prealgebra 2 Self-Paced

Introduction to Algebra A
Sunday, Feb 16 - Jun 8 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28

Introduction to Algebra A Self-Paced

Introduction to Counting & Probability
Sunday, Feb 9 - Apr 27 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2

Introduction to Counting & Probability Self-Paced

Introduction to Number Theory
Sunday, Feb 16 - May 4
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3

Introduction to Algebra B
Thursday, Feb 13 - May 29
Sunday, Mar 2 - Jun 22
Monday, Mar 17 - Jul 7
Wednesday, Apr 16 - Jul 30

Introduction to Algebra B Self-Paced

Introduction to Geometry
Friday, Feb 14 - Aug 1
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1

Intermediate: Grades 8-12

Intermediate Algebra
Wednesday, Feb 12 - Jul 23
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13

Intermediate Counting & Probability
Monday, Feb 10 - Jun 16
Sunday, Mar 23 - Aug 3

Intermediate Number Theory
Thursday, Feb 20 - May 8
Friday, Apr 11 - Jun 27

Precalculus
Tuesday, Feb 25 - Jul 22
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21

Calculus
Friday, Feb 28 - Aug 22
Sunday, Mar 30 - Oct 5

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Tuesday, Feb 4 - Apr 22
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2

MATHCOUNTS/AMC 8 Advanced
Sunday, Feb 16 - May 4
Friday, Apr 11 - Jun 27

AMC 10 Problem Series
Sunday, Feb 9 - Apr 27
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23

AMC 10 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

AMC 12 Problem Series
Sunday, Feb 23 - May 11

AMC 12 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

Special AIME Problem Seminar B
Sat & Sun, Feb 1 - Feb 2 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

F=ma Problem Series
Wednesday, Feb 19 - May 7

Programming

Introduction to Programming with Python
Sunday, Feb 16 - May 4
Monday, Mar 24 - Jun 16

Intermediate Programming with Python
Tuesday, Feb 25 - May 13

USACO Bronze Problem Series
Thursday, Feb 6 - Apr 24

Physics

Introduction to Physics
Friday, Feb 7 - Apr 25
Sunday, Mar 30 - Jun 22

Physics 1: Mechanics
Sunday, Feb 9 - Aug 3
Tuesday, Mar 25 - Sep 2

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
0 replies
jlacosta
Feb 2, 2025
0 replies
2014-2015 Fall OMO #26
v_Enhance   14
N Feb 9, 2025 by abeot
Let $ABC$ be a triangle with $AB=26$, $AC=28$, $BC=30$. Let $X$, $Y$, $Z$ be the midpoints of arcs $BC$, $CA$, $AB$ (not containing the opposite vertices) respectively on the circumcircle of $ABC$. Let $P$ be the midpoint of arc $BC$ containing point $A$. Suppose lines $BP$ and $XZ$ meet at $M$ , while lines $CP$ and $XY$ meet at $N$. Find the square of the distance from $X$ to $MN$.

Proposed by Michael Kural
14 replies
v_Enhance
Oct 28, 2014
abeot
Feb 9, 2025
2018-2019 Fall OMO Problem 30
trumpeter   17
N Jan 10, 2025 by qwerty123456asdfgzxcvb
Let $ABC$ be an acute triangle with $\cos B =\frac{1}{3}, \cos C =\frac{1}{4}$, and circumradius $72$. Let $ABC$ have circumcenter $O$, symmedian point $K$, and nine-point center $N$. Consider all non-degenerate hyperbolas $\mathcal H$ with perpendicular asymptotes passing through $A,B,C$. Of these $\mathcal H$, exactly one has the property that there exists a point $P\in \mathcal H$ such that $NP$ is tangent to $\mathcal H$ and $P\in OK$. Let $N'$ be the reflection of $N$ over $BC$. If $AK$ meets $PN'$ at $Q$, then the length of $PQ$ can be expressed in the form $a+b\sqrt{c}$, where $a,b,c$ are positive integers such that $c$ is not divisible by the square of any prime. Compute $100a+b+c$.

Proposed by Vincent Huang
17 replies
trumpeter
Nov 7, 2018
qwerty123456asdfgzxcvb
Jan 10, 2025
2013-2014 Fall OMO #26
v_Enhance   8
N Jan 8, 2025 by OronSH
Let $ABC$ be a triangle with $AB=13$, $AC=25$, and $\tan  A = \frac{3}{4}$. Denote the reflections of $B,C$ across $\overline{AC},\overline{AB}$ by $D,E$, respectively, and let $O$ be the circumcenter of triangle $ABC$. Let $P$ be a point such that $\triangle DPO\sim\triangle PEO$, and let $X$ and $Y$ be the midpoints of the major and minor arcs $\widehat{BC}$ of the circumcircle of triangle $ABC$. Find $PX \cdot PY$.

Proposed by Michael Kural
8 replies
v_Enhance
Oct 30, 2013
OronSH
Jan 8, 2025
2012-2013 Winter OMO #22
v_Enhance   2
N Dec 28, 2024 by NicoN9
In triangle $ABC$, $AB = 28$, $AC = 36$, and $BC = 32$. Let $D$ be the point on segment $BC$ satisfying $\angle BAD = \angle DAC$, and let $E$ be the unique point such that $DE \parallel AB$ and line $AE$ is tangent to the circumcircle of $ABC$. Find the length of segment $AE$.

Ray Li
2 replies
v_Enhance
Jan 16, 2013
NicoN9
Dec 28, 2024
2012-2013 Winter OMO #11
v_Enhance   2
N Dec 26, 2024 by NicoN9
Let $A$, $B$, and $C$ be distinct points on a line with $AB=AC=1$. Square $ABDE$ and equilateral triangle $ACF$ are drawn on the same side of line $BC$. What is the degree measure of the acute angle formed by lines $EC$ and $BF$?

Ray Li
2 replies
v_Enhance
Jan 16, 2013
NicoN9
Dec 26, 2024
2011-2012 Winter OMO #22
Zhero   4
N Dec 24, 2024 by NicoN9
Find the largest prime number $p$ such that when $2012!$ is written in base $p$, it has at least $p$ trailing zeroes.

Author: Alex Zhu
4 replies
Zhero
Jan 24, 2012
NicoN9
Dec 24, 2024
2013-2014 Fall OMO #29
v_Enhance   22
N Dec 11, 2024 by eg4334
Kevin has $255$ cookies, each labeled with a unique nonempty subset of $\{1,2,3,4,5,6,7,8\}$. Each day, he chooses one cookie uniformly at random out of the cookies not yet eaten. Then, he eats that cookie, and all remaining cookies that are labeled with a subset of that cookie (for example, if he chooses the cookie labeled with $\{1,2\}$, he eats that cookie as well as the cookies with $\{1\}$ and $\{2\}$). The expected value of the number of days that Kevin eats a cookie before all cookies are gone can be expressed in the form $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

Proposed by Ray Li
22 replies
v_Enhance
Oct 30, 2013
eg4334
Dec 11, 2024
2012-2013 Winter OMO #38
v_Enhance   11
N Oct 29, 2024 by PEKKA
Triangle $ABC$ has sides $AB = 25$, $BC = 30$, and $CA=20$. Let $P,Q$ be the points on segments $AB,AC$, respectively, such that $AP=5$ and $AQ=4$. Suppose lines $BQ$ and $CP$ intersect at $R$ and the circumcircles of $\triangle{BPR}$ and $\triangle{CQR}$ intersect at a second point $S\ne R$. If the length of segment $SA$ can be expressed in the form $\frac{m}{\sqrt{n}}$ for positive integers $m,n$, where $n$ is not divisible by the square of any prime, find $m+n$.

Victor Wang
11 replies
v_Enhance
Jan 16, 2013
PEKKA
Oct 29, 2024
2015-2016 Fall OMO #12
pi37   14
N Aug 7, 2024 by eg4334
Let $a$, $b$, $c$ be the distinct roots of the polynomial $P(x) = x^3 - 10x^2 + x - 2015$.
The cubic polynomial $Q(x)$ is monic and has distinct roots $bc-a^2$, $ca-b^2$, $ab-c^2$.
What is the sum of the coefficients of $Q$?

Proposed by Evan Chen
14 replies
pi37
Nov 18, 2015
eg4334
Aug 7, 2024
2017-2018 Fall OMO Problem 18
trumpeter   6
N Aug 5, 2024 by ryanbear
Let $a,b,c$ be real nonzero numbers such that $a+b+c=12$ and \[\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{abc}=1.\]Compute the largest possible value of $abc-\left(a+2b-3c\right)$.

Proposed by Tristan Shin
6 replies
trumpeter
Nov 7, 2017
ryanbear
Aug 5, 2024
2013-2014 Fall OMO #29
v_Enhance   22
N Dec 11, 2024 by eg4334
Kevin has $255$ cookies, each labeled with a unique nonempty subset of $\{1,2,3,4,5,6,7,8\}$. Each day, he chooses one cookie uniformly at random out of the cookies not yet eaten. Then, he eats that cookie, and all remaining cookies that are labeled with a subset of that cookie (for example, if he chooses the cookie labeled with $\{1,2\}$, he eats that cookie as well as the cookies with $\{1\}$ and $\{2\}$). The expected value of the number of days that Kevin eats a cookie before all cookies are gone can be expressed in the form $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

Proposed by Ray Li
22 replies
v_Enhance
Oct 30, 2013
eg4334
Dec 11, 2024
2013-2014 Fall OMO #29
G H J
G H BBookmark kLocked kLocked NReply
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6853 posts
#1 • 3 Y
Y by abacadaea, HamstPan38825, Adventure10
Kevin has $255$ cookies, each labeled with a unique nonempty subset of $\{1,2,3,4,5,6,7,8\}$. Each day, he chooses one cookie uniformly at random out of the cookies not yet eaten. Then, he eats that cookie, and all remaining cookies that are labeled with a subset of that cookie (for example, if he chooses the cookie labeled with $\{1,2\}$, he eats that cookie as well as the cookies with $\{1\}$ and $\{2\}$). The expected value of the number of days that Kevin eats a cookie before all cookies are gone can be expressed in the form $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

Proposed by Ray Li
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ahaanomegas
6294 posts
#2 • 2 Y
Y by Teevee, Adventure10
The Numerators: Our 'Solution'
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
james4l
2172 posts
#3 • 3 Y
Y by Adventure10, Mango247, and 1 other user
Actual Solution, more or less
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6853 posts
#4 • 3 Y
Y by HamstPan38825, Adventure10, Mango247
This was my favorite problem on the test; there is a very elegant solution using hint
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math_explorer
583 posts
#5 • 1 Y
Y by Adventure10
(not-so-)Obviously, the probability of everything is the same if Kevin picks a random permutation of all the cookies at the start and goes down the list, eating each cookie that still exists by the time he gets to it plus its subsets.

So compute the probability that each cookie takes up one of Kevin's days, i.e. that the cookie comes before its supersets in the permutation, and sum by linearity of expectation.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ksun48
1514 posts
#6 • 5 Y
Y by danepale, Adventure10, Mango247, and 2 other users
http://codeforces.com/problemset/problem/280/C
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6853 posts
#7 • 9 Y
Y by codyj, abacadaea, aopsqwerty, modest_branding, sotpidot, HamstPan38825, myh2910, Adventure10, Mango247
Okay, here is Ray's intended solution. Consider any cookie $S$. The expected number of times Kevin will choose it is $\frac{1}{2^{8-\lvert S \rvert}}$, because if the cookie is un-eaten then its parents are un-eaten. So the answer is just \[ \sum_{S} \frac{1}{2^{8-\lvert S \rvert}} \] which can be evaluated using standard techniques.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
codyj
723 posts
#8 • 2 Y
Y by Adventure10, Mango247
Awesome!!!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
quantumman
245 posts
#9 • 2 Y
Y by Adventure10, Mango247
That is amazing. I knew it had something to do with linearity didnt know how to finish it off though.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
abacadaea
2176 posts
#10 • 1 Y
Y by Adventure10
james4l wrote:
This works on any arbitrary graph, obviously without directed cycles because circular dependencies are kinda silly.

I'm pretty sure this works even if there are circular dependencies? The only thing that affects P(cookie X is eaten) is the number of cookies that X must be eaten with (i.e. the indegree of X in the graph), so its okay if the out-neighborhood of X overlaps with the in-neighborhood.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math154
4302 posts
#11 • 2 Y
Y by Adventure10, Mango247
abacadaea wrote:
james4l wrote:
This works on any arbitrary graph, obviously without directed cycles because circular dependencies are kinda silly.

I'm pretty sure this works even if there are circular dependencies?
I think we want the graph to be transitive. For $A\to B\to C$ (no edge between $A,C$) the expected value is certainly not $\frac{1}{1}+\frac{1}{2}+\frac{1}{2}$, since you need at least 2 days but you take 3 when you choose $C,B,A$ in that order. (The original argument fails because $C$ has a higher chance than $B$ of killing $C$---$A$ can kill $B$ before $C$ dies.)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
james4l
2172 posts
#12 • 2 Y
Y by Adventure10, Mango247
@abacadaea: Oh. That is true. Earlier I thought you could simply merge cycles into one big cookie but then again it's a bigger cookie that has a higher chance of being selected. Oops I guess it does make a difference.

@math154: I guess I should have clarified that by "cookies that trigger its demise" I also include indirectly, so C dies to A as well (or the reverse, I don't know what the arrow notation means), so it produces 1/1+1/2+1/3 which is correct.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math154
4302 posts
#13 • 1 Y
Y by Adventure10
Arrow means kill. So that's what I meant by transitivity.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathlogician
1051 posts
#14
Y by
Instead of the number of days, we consider the number of cookies that have been eaten. Note that since any given subset $X$ is guaranteed to be eaten eventually, we can find the probability that a cookie was the cookie that Kevin choose at random. If this subset has $A$ elements, then the aforementioned probability is $\frac{1}{2^{n-A}}$. Now, by linearity of expectation we can sum this result over all $2^n -1$ subsets, and consequently find the expected number of cookies Kevin chooses. To make this computation cleaner, we also add the empty set; note that this addition will increase the expected value by $\frac{1}{2^n}$. Let $S$ be the set $\{1,2, \dots, n\}.$ Now note that we have$$\sum _ \text{subsets of S} \frac{1}{2^{n-A}} = \sum ^n _{i=0} \frac{1}{2^{n-i}} \binom{n}{i} = \sum ^n _{i=0} \frac{1}{2^{i}} \binom{n}{i} = \left(1+\frac{1}{2}\right)^n,$$so our desired answer is$$\boxed{\left(\frac{3}{2}\right)^n - \frac{1}{2^n}}$$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathscienceclass
1246 posts
#15
Y by
Note that the expected value is the expected number of cookies that were chosen, so we use the indicator variables $c_S$ that take on $1$ if the cookie with label $S$ was chosen manually, and $0$ otherwise; we seek $\mathbb{E}[\sum_{S} c_S] = \sum_{S} \mathbb{E}[c_S]$. $\mathbb{E}[c_S]$, by definition, is just the probability that the cookie with label $S$ was chosen manually. If this cookie is uneaten, then the cookies with supersets of $S$ are uneaten as well. Furthermore, this cookie will only be eaten if Kevin manually chooses a cookie with label that is a superset of $S$. Thus the probability is simply the probability of $S$ itself being the chosen superset, which is $\frac{1}{2^{n-|S|}}$. Now we sum; I'll leave the computation to the reader. The answer is $\boxed{\left(\frac{3}{2}\right)^n-\frac{1}{2^n}}$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fidgetboss_4000
3469 posts
#16 • 5 Y
Y by Onafets, Lilathebee, RedFlame2112, Mango247, Mango247
how is this a #29
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8793 posts
#17
Y by
The main claim is the following:

Claim. The probability that a $k$-element subset is removed on its own and not by a superset is exactly $\frac 1{2^{n-k}}$.

Proof. This is obvious by infinite states. $\blacksquare$

Thus, the answer is simply $$\sum_{k=1}^n \frac{{n \choose k}}{2^{n-k}} = \left(1+\frac 12\right)^n - \left(\frac 12\right)^n = \frac{3^n-1}{2^n}.$$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
peppapig_
278 posts
#18
Y by
For a particular cookie with subset $S$ and $|S|$ elements, we have that Kevin has $\frac{2^n}{2^{|S|}}$ cookies that Kevin could choose in order to also eat $S$'s cookie. Therefore for any arbitrary cookie iced with $k$ elements, Kevin is expected to eat it $\frac{1}{2^{n-k}}$ times. By linearity of expectation, summing this over all $2^n-1$ cookies gives us a total expected value of
\[1\binom{n}{n}+\frac{1}{2}\binom{n}{n-1}+\dots+\frac{1}{2^{n-1}}\binom{n}{1}=-\frac{1}{2^n}+\sum_{i=0}^{n}\frac{1}{2^i}\binom{n}{i}=\left(1+\frac{1}{2}\right)^n-\left(\frac{1}{2}\right)^n,\]by binomial theorem, or $\left(\frac{3}{2}\right)^n-\left(\frac{1}{2}\right)^n$ expected days, finishing the problem.
This post has been edited 1 time. Last edited by peppapig_, Dec 10, 2023, 10:55 PM
Reason: Somehow forgot to paste over a whole line
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blueprimes
274 posts
#19
Y by
For every cookie with set $S$, that there are ${2^{n - |S|}}$ that have $S$ as a subset. The probability that cookie $S$ will be chosen to eliminate itself is hence $\frac{1}{2^{n - |S|}}$. By linearity, the expected number of cookies Kevin eats is also the sum os $\frac{1}{2^{n - |S|}}$ over all $S \subseteq \{1, 2, \dots, n \}$, so we wish to evaluate
$$\sum_{k = 1}^n \frac{\binom{n}{k}}{2^{n - k}} = \sum_{k = 1}^n \binom{n}{n - k} \left(\frac{1}{2} \right) 1^k = \left(1 + \frac{1}{2} \right)^n - \left( \frac{1}{2} \right)^n = \boxed{\frac{3^n - 1}{2^n}}.$$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dolphinday
1301 posts
#20
Y by
Add the empty set as a cookie and subtract $\frac{1}{2^n}$ from the final result as the empty set will be eaten given any choice on the first day.
The probability that a given cookie labeled with set $c$ is chosen is $\frac{1}{2^{n-|c|}}$. Then by linearity of expectation, we can sum this value over all $c \in \{1, 2, \dots, n\}$ to get the desired result. Notice that this sum is just $\frac{(1 + 2)^n}{2^n} = \frac{3^n}{2^n}$ and subtracting $\frac{1}{2^n}$ gives us $\frac{3^n - 1}{2^n}$ as our answer.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathwiz_1207
86 posts
#21
Y by
Notice that the expected number of days that Kevin eats the cookies is equal to the number of subsets of cookies he eats. Now, define
\[X_i =  \begin{cases} 
      1 & \text{cookie $i$ is directly eaten} \\
     0 & \text{a superset of cookie $i$ is eaten} \\
   \end{cases}\]Then, by linearity of expectation,
\[E[X_1 + X_2 + \cdots + X_{2^n - 1}] = E[X_1] + E[X_2] + \cdots + E[X_{2^n - 1}]\]Now, if subset $i$ is of size $k$, then there are $2^{n-k}$ sets which are a superset of it, thus the chance it is eaten is $\frac{1}{2^{n-k}}$. So, we get that
\[E[X_1] + E[X_2] + \cdots + E[X_{2^n - 1}] = \sum_{k=1}^n \frac{1}{2^{n-k}}{n \choose k} = \boxed{\frac{3^n - 1}{2^n}}\]and we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lpieleanu
2783 posts
#22
Y by
Solution
This post has been edited 2 times. Last edited by lpieleanu, Dec 5, 2024, 2:02 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
eg4334
570 posts
#23
Y by
General solution:

The main idea of the problem is that we want to consider the expected number of sets chosen by Kevin, or the sum of the probabilities that Kevin chooses that set over all sets (for some reason this took a long time). It's not hard to see that for a set of cardinality $k$, there are $2^{n-k}$ subsets with that as a subset, so the probability we want is $\frac{1}{2^{n-k}}$. Sum this over all subsets: $$\sum_{k = 1}^8 \binom{n}{k} \frac{1}{2^{n-k}}$$$$\frac{1}{2^n} \sum_{k=1}^8 \binom{n}{k} 2^k = \frac{1}{2^n} (3^n-1)$$
Z K Y
N Quick Reply
G
H
=
a