The time is now - Spring classes are filling up!

G
Topic
First Poster
Last Poster
k a AMC 10/12 A&B Coming up Soon!
jlacosta   0
Nov 1, 2024
There is still time to train for the November 6th and November 12th AMC 10A/12A and AMC 10B/12B, respectively! Enroll in our weekend seminars to be held on November 2nd and 3rd (listed below) and you will learn problem strategies, test taking techniques, and be able to take a full practice test! Note that the “B” seminars will have different material from the “A” seminars which were held in October.

[list][*]Special AMC 10 Problem Seminar B
[*]Special AMC 12 Problem Seminar B[/list]
For those who want to take a free practice test before the AMC 10/12 competitions, you can simulate a real competition experience by following this link. As you assess your performance on these exams, be sure to gather data!

[list][*]Which problems did you get right?
[list][*]Was the topic a strength (e.g. number theory, geometry, counting/probability, algebra)?
[*]How did you prepare?
[*]What was your confidence level?[/list]
[*]Which problems did you get wrong?
[list][list][*]Did you make an arithmetic error?
[*]Did you misread the problem?
[*]Did you have the foundational knowledge for the problem?
[*]Which topics require more fluency through practice (e.g. number theory, geometry, counting/probability, algebra)?
[*]Did you run out of time?[/list][/list]
Once you have analyzed the results with the above questions, you will have a plan of attack for future contests! BEST OF LUCK to all competitors at this year’s AMC 10 and AMC 12!

Did you know that the day after both the AMC 10A/12A and AMC 10B/12B you can join a free math jam where our AoPS team will go over the most interesting problems? Find the schedule below under “Mark your calendars”.

Mark your calendars for these upcoming free math jams!
[list][*]November 20th: Amherst College Info Session, 7:30 pm ET: Matt McGann, Dean of Admission and Financial Aid at Amherst College, and Nathan Pflueger, math professor at Amherst College, will host an info session exploring both Amherst College specifically and liberal arts colleges generally. Topics include opportunities in math, the admission process, and financial aid for both US and international students.
[*]November 7th: 2024 AMC 10/12 A Discussion, Thursday, 7:30 pm ET:
[*]AoPS instructors will discuss problems from the AMC 10/12 A, administered November 6. We will discuss some of the most interesting problems from each test!
[*]November 13th: 2024 AMC 10/12 B Discussion, Wednesday, 7:30 pm ET:
[*]AoPS instructors will discuss problems from the AMC 10/12 B, administered November 12. We will discuss some of the most interesting problems from each test![/list]
AoPS Spring classes are open for enrollment. Get a jump on the New Year 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!

Whether you've taken our classes at AoPS Online or AoPS Academies or reached the top echelons of our competition training with our Worldwide Online Olympiad Training (WOOT) program, you can now add your AoPS experience to the education section 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
Sunday, Nov 3 - Mar 9
Tuesday, Nov 5 - Mar 11
Friday, Dec 6 - Apr 4
Sunday, Jan 5 - Apr 20
Wednesday, Jan 15 - Apr 30
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
Thursday, Nov 7 - Mar 13
Monday, Dec 2 - Mar 31
Wednesday, Jan 8 - Apr 23
Sunday, Jan 19 - May 4 (1:00 - 2:15 pm ET/10:00 - 11:15 am PT)
Monday, Jan 27 - May 12
Tuesday, Jan 28 - May 13 (4:30 - 5:45 pm ET/1:30 - 2:45 pm PT)
Sunday, Feb 16 - Jun 8
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10

Prealgebra 2 Self-Paced

Introduction to Algebra A
Friday, Nov 8 - Mar 14
Wednesday, Dec 11 - Apr 9
Tuesday, Jan 7 - Apr 22
Wednesday, Jan 29 - May 14
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
Thursday, Dec 5 - Mar 6
Wednesday, Jan 8 - Mar 26
Thursday, Jan 30 - Apr 17
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
Monday, Dec 2 - Mar 3
Tuesday, Jan 28 - Apr 15
Sunday, Feb 16 - May 4
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3

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

Introduction to Geometry
Monday, Nov 11 - May 12
Wednesday, Nov 13 - May 14 (9:30 - 11:00 pm ET/6:30 - 8:00 pm PT)
Tuesday, Dec 10 - Jun 3
Wednesday, Jan 8 - Jun 18
Thursday, Jan 30 - Jul 10
Friday, Feb 14 - Aug 1
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1

Paradoxes and Infinity
Sat & Sun, Nov 16 - Nov 17 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Nov 10 - May 11
Tuesday, Dec 3 - May 27
Friday, Jan 17 - Jun 27
Wednesday, Feb 12 - Jul 23
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13

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

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

Precalculus
Sunday, Nov 10 - Apr 27
Tuesday, Dec 10 - May 20
Wednesday, Jan 8 - Jun 4
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
Tuesday, Dec 10 - Jun 10
Friday, Feb 28 - Aug 22
Sunday, Mar 30 - Oct 5

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Mon, Wed & Fri, Dec 2 - Jan 10 (meets three times each week!)
Tuesday, Feb 4 - Apr 22
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2

MATHCOUNTS/AMC 8 Advanced
Tuesday, Nov 5 - Feb 11
Mon, Wed & Fri, Dec 2 - Jan 10 (meets three times each week!)
Tue, Thurs & Sun, Dec 10 - Jan 19 (meets three times each week!)
Sunday, Feb 16 - May 4
Friday, Apr 11 - Jun 27

Special AMC 8 Problem Seminar A
Sat & Sun, Jan 11 - Jan 12 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

Special AMC 8 Problem Seminar B
Sat & Sun, Jan 18 - Jan 19 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

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)

Special AMC 10 Problem Seminar B
Sat & Sun, Nov 2 - Nov 3 (4:00 - 7:00 pm ET/1:00 - 4: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 AMC 12 Problem Seminar B
Sat & Sun, Nov 2 - Nov 3 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

AIME Problem Series A
Tue, Thurs & Sun, Jan 7 - Feb (meets three times each week!)

AIME Problem Series B
Mon, Wed & Fri, Jan 6 - Jan 31 (meets three times each week!)

Special AIME Problem Seminar A
Sat & Sun, Jan 25 - Jan 26 (4:00 - 7:00 pm ET/1:00 - 4: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
Monday, Dec 2 - Mar 3
Friday, Jan 17 - Apr 4
Sunday, Feb 16 - May 4
Monday, Mar 24 - Jun 16

Intermediate Programming with Python
Tuesday, Feb 25 - May 13

Science

Introduction to Physics
Tuesday, Dec 10 - Mar 11
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, Dec 14 - Dec 15 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
0 replies
jlacosta
Nov 1, 2024
0 replies
easy substitutions for a functional in reals
Circumcircle   3
N 14 minutes ago by megarnie
Source: Kosovo Math Olympiad 2025, Grade 11, Problem 2
Find all functions $f:\mathbb{R}\rightarrow\mathbb{R}$ with the property that for every real numbers $x$ and $y$ it holds that
$$f(x+yf(x+y))=f(x)+f(xy)+y^2.$$
3 replies
Circumcircle
2 hours ago
megarnie
14 minutes ago
Simple system of equations
topologicalsort   2
N 21 minutes ago by rchokler
Source: Bulgarian Autumn Tournament 2024, 10.1
Find all real solutions to the system of equations: $$\begin{cases} (x^2+xy+y^2)\sqrt{x^2+y^2} = 88 \\ (x^2-xy+y^2)\sqrt{x^2+y^2} = 40  \end{cases}$$
2 replies
topologicalsort
3 hours ago
rchokler
21 minutes ago
Perfect powers of functions on a finite set
Tintarn   2
N an hour ago by eddiekopp
Source: Baltic Way 2024, Problem 9
Let $S$ be a finite set. For a positive integer $n$, we say that a function $f\colon S\to S$ is an $n$-th power if there exists some function $g\colon S\to S$ such that
\[
    f(x) = \underbrace{g(g(\ldots g(x)\ldots))}_{\mbox{\scriptsize $g$ applied $n$ times}}
\]for each $x\in S$.

Suppose that a function $f\colon S\to S$ is an $n$-th power for each positive integer $n$. Is it necessarily true that $f(f(x)) = f(x)$ for each $x\in S$?
2 replies
Tintarn
6 hours ago
eddiekopp
an hour ago
A 5 y old result
mihaig   0
an hour ago
Source: Possibly Own
Let $a,b,c,d\geq0$ be reals satisfying $a^2+b^2+c^2+d^2=4.$
Prove
$$\sqrt3\left(a^3+b^3+c^3+d^3\right)+4\left(2-\sqrt3\right)\sqrt[4]{a^3b^3c^3d^3}\geq8.$$Study the equality cases.
0 replies
mihaig
an hour ago
0 replies
No more topics!
Size of Subsets of Stable Staircases
willwin4sure   17
N Yesterday at 12:26 PM by kes0716
Source: USA TSTST 2020 Problem 5, by Ashwin Sah and Mehtaab Sawhney
Let $\mathbb{N}^2$ denote the set of ordered pairs of positive integers. A finite subset $S$ of $\mathbb{N}^2$ is stable if whenever $(x,y)$ is in $S$, then so are all points $(x',y')$ of $\mathbb{N}^2$ with both $x'\leq x$ and $y'\leq y$.

Prove that if $S$ is a stable set, then among all stable subsets of $S$ (including the empty set and $S$ itself), at least half of them have an even number of elements.

Ashwin Sah and Mehtaab Sawhney
17 replies
willwin4sure
Dec 14, 2020
kes0716
Yesterday at 12:26 PM
Size of Subsets of Stable Staircases
G H J
G H BBookmark kLocked kLocked NReply
Source: USA TSTST 2020 Problem 5, by Ashwin Sah and Mehtaab Sawhney
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
willwin4sure
257 posts
#1 • 2 Y
Y by son7, Mango247
Let $\mathbb{N}^2$ denote the set of ordered pairs of positive integers. A finite subset $S$ of $\mathbb{N}^2$ is stable if whenever $(x,y)$ is in $S$, then so are all points $(x',y')$ of $\mathbb{N}^2$ with both $x'\leq x$ and $y'\leq y$.

Prove that if $S$ is a stable set, then among all stable subsets of $S$ (including the empty set and $S$ itself), at least half of them have an even number of elements.

Ashwin Sah and Mehtaab Sawhney
This post has been edited 1 time. Last edited by willwin4sure, Dec 15, 2020, 6:09 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
The_Turtle
253 posts
#2 • 29 Y
Y by SnowPanda, spartacle, ProblemSolver2048, mira74, spike2015, 606234, aa1024, yayups, jeff10, Idio-logy, QuaternionUniverse, MarkBcc168, Atpar, Rg230403, p_square, Pluto04, yunseo, iks92, enzoP14, L567, megarnie, OlympusHero, pog, guptaamitu1, IAmTheHazard, Mango247, Mango247, Mango247, Sedro
Define the profile of a stable set to be the set of points in it with even $x$-coordinate. It suffices to show that among all subsets of $S$ with the same profile, at least half have even cardinality.
[asy]
size(100);
int[] s = {11, 8, 8, 6, 4, 4, 3, 2, 2, 1};
int[] p = {0, 7, 0, 5, 0, 2, 0, 2, 0, 0};
for (int i = 1; i <= s.length; ++i) {
	for (int j = 1; j <= s[i-1]; ++j) {
    	if (j <= p[i-1]) {
        	dot((i, j), red);
        } else {
        	dot((i, j));
            if (i % 2 == 1 && j <= (i > 1 ? p[i-2] : s[0]) && j > (i < s.length ? p[i] : 0)) {
            	draw(shift((i, j)) * ((-0.5, -0.5) -- (-0.5, 0.5) -- (0.5, 0.5) -- (0.5, -0.5) -- cycle));
            }
        }
        if (j == (i > 1 ? min(s[i-1], p[i-2]) : s[0])) {
        	label(scale(0.5) * ("$c_" + string(i) + "$ = " + string((i > 1 ? p[i-2] : s[0]) - (i < s.length ? p[i] : 0))), (i+1, s[i-1]+1.25));
        }
        if (i % 2 == 0 && p[i-1] != 0) {
        	draw((i - 1.5, p[i-1]+0.5) -- (i + 0.5, p[i-1]+0.5) -- (i + 0.5, (i < s.length ? p[i+1] : 0)+0.5));
        }
    }
}
label("$P$", (1.5, -0.5), red);
label("$S$", (-1, s[0]+0.5));
[/asy]
Fix a profile $P$, and for each odd-indexed column $i$, let $c_i$ be the number of points in the column with a point in $P$ (or no point) to its immediate left but not to its right. Then each stable subset with profile $P$ can be represented as an element of
\[\{0, 1, \ldots, c_1\} \times \{0, 1, \ldots, c_3\} \times \{0, 1, \ldots, c_5\} \times \ldots,\]and the subset has even size if and only if its corresponding tuple has even sum. If a $c_i$ is odd, then exactly half of the tuples have even sum. If every $c_i$ is even, then there is exactly one more tuple with even sum than with odd sum, by induction. $\blacksquare$
This post has been edited 1 time. Last edited by The_Turtle, Dec 14, 2020, 7:40 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rd123
473 posts
#5 • 6 Y
Y by 606234, mira74, The_Turtle, ProblemSolver2048, Pluto04, Stuffybear
Definitely not as elegant as the above solution.

Call the border of a stable set $S$ the set $$\{(x,y) \in S \ | \ (x+1,y+1) \not\in S \}.$$
We induct on the number of points. If there is either $0$ or $1$ points, then the conclusion is clear, so the base case has been established. Also assume if $S$ is stable and $|S| < n$ then the conclusion follows.

For the inductive step assume $|S|=n$. Choose a point $P=(x_0,y_0)$ in the border of $S$ with at least one even coordinate, which clearly exists if $n > 1$. (We can just take a point with $x$-coordinate or $y$-coordinate equal to $2$.) We will do cases on whether $P$ is in the stable subset or not.

Case 1: $P$ is in the subset.

Then all points $(x,y)$ with $x<x_0,y<y_0$ are in the subset. There are $x_0y_0$ of these, which is even. The remaining points in $S$ can be split into two (possibly empty) sets, $S_1$ and $S_2$.
[asy]
fill((0,0)--(0,7)--(4,7)--(4,0)--cycle, green + opacity(0.02));
fill((4,5)--(6,5)--(6,2)--(8,2)--(8,0)--(4,0)--cycle,cyan + opacity(0.02));
fill((0,7)--(0,10)--(3,10)--(3,8)--(4,8)--(4,7)--cycle,cyan+opacity(0.02));
draw((0,10)--(3,10)--(3,8)--(4,8)--(4,5)--(6,5)--(6,2)--(8,2)--(8,0),red);
draw((8,0)--(0,0)--(0,10));
dot("$P$",(3.5,6.5),SW);
label("$S_1$",(5,1));
label("$S_2$",(1,8));
[/asy]
Note that both $S_1$ and $S_2$ are stable if they were to be translated accordingly. Let $S_i$ have $E_i$ "stable" subsets of even size, and $O_i$ of odd size. Since we have already included an even number of points in our subset, we get $E_1E_2+O_1O_2$ stable subsets of even size, and $E_1O_2+E_2O_1$ stable subsets of odd size. As $$(E_1E_2+O_1O_2)-(E_1O_2+E_2O_1)=(E_1-O_1)(E_2-O_2) \geq 0$$by the inductive hypothesis, this case gives at least half of stable subsets are of even size. (The last step is also just the rearrangement inequality in $2$ variables.)

Case 2: $P$ is not in the subset.

The points directly above $P$ as well as those directly to the right of $P$ are then also not in the subset. We may delete these points, and we are left with another stable set $S'$, and at least half of stable subsets of $S'$ are of even size by inductive hypothesis.

Thus, both cases give at least half of stable subsets having even size, so overall at least half of stable subsets are of even size.
This post has been edited 2 times. Last edited by rd123, Dec 14, 2020, 6:42 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathematicsislovely
245 posts
#6 • 4 Y
Y by amar_04, Mango247, Mango247, Mango247
Please someone check if my solution is correct or not... :help:
Ignore,because it is wrong

@below,Yes you re right.Thanks for pointing out the mistake
This post has been edited 6 times. Last edited by Mathematicsislovely, Dec 14, 2020, 11:41 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mira74
1008 posts
#7 • 1 Y
Y by Mathematicsislovely
@above unfortunately, your mapping from odds to evens is not injective, I believe the diagram below shows that a 3x3 pillar followed by a 2x2 pillar and a 3x5 pillar would both map to a 2x5 pillar.
Attachments:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Eyed
1065 posts
#9 • 1 Y
Y by kevinmathz
Poorly written, needs a diagram :(

Consider every stable set, and for each $(x, y)$ in the set colour in the square $(x, y)$ on an infinite array, where the bottom left square is $(0, 0)$. Then, by the condition, the stable set is all the points underneath some path from the y axis to the x axis, such that every step moves one step to the right or one step down. Assume the first move is rightward and the last move is downward. Denote this as the "path of S". We will now prove the result via induction on the number of elements in $S$.

Our base case is if $S$ had $0$ elements, so it is empty. Then, since the empty set has an even number of elements, at least half of all the stable subsets of $S$ has an even number of elements, so our base case is proven. Now, assume for all stable sets $|T| < |S|$, at least half the stable subsets of $T$ has an even number of elements. Clearly any stable subset of $S$ must have it's path be below and to the left of the path of $S$. Consider a point $P = (x, y)$ on the path such that $xy$ is even. We will further impose the condition that $P$ is at most $2$ steps away from the end of the path, so either we move right then down to get to the end, down and down, or just down. One of these points must have at least one even coordinate (and be on the path).

Then, for any stable subset $T$ of $S$ whose path does not contain $P$, we can create a new path by removing every square whose coordinates $(x', y')$ are $x'\geq x, y'\geq y$, then adjusting the new path to go around these removed squares borders, which will also have $T$ as a stable subset. By our inductive hypothesis, at least half of these paths have even elements. Then, if a path contained $P$, then it must also contain the rectangle with corners at $(0, 0), (x, 0), (x, y), (0, y)$, which has an even number of elements. Furthermore, the beginning of the path will go from the y axis to $P$, so if cut the path off by the line parallel to the $x$ axis and through $P$, by our inductive hypothesis at least half of these sub-paths will contain an even number of elements. Finally, the last bit of the path, from $P$ to the end, either all of them contain even elements or exactly half of them do (again, via our condition of $P$). Thus, for the paths that pass through $P$, at least half of them contain even elements. Since in both cases at least half the paths have even elements, we conclude that over all stable subsets, at least half of them have even elements. Our induction is complete.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YaWNeeT
64 posts
#10 • 3 Y
Y by Rg230403, USJL, p_square
Apptempted to give a bijective proof, but it's wrong
Attachments:
This post has been edited 1 time. Last edited by YaWNeeT, Dec 19, 2020, 8:22 AM
Reason: wrong
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
zschess
92 posts
#11
Y by
Suppose $S$ has maximum $x$-coordinate equal to $n$. Note that any stable subset of $S$ can be seen as a sequence of integers $0 \le a_1 \le a_2 \le \cdots \le a_n$ where $a_i \le b_i$ (where the set is represented by a nondecreasing sequence $b_1,b_2,\cdots,b_n$ by looking at the $y$-coordinates from right to left). The number of elements in the subset is just $\sum a_i$.

We use dynamic programming. Let $E(i,j)$ denote the number of nondecreasing sequences $c$ of length $i$ that ends with $j$ such that $c_k \le b_k$ for all $k \le i$ and $\sum c_k$ is even. Define $O(i,j)$ similarly (but for when $\sum c_k$ is odd). Let $dp(i,j)=E(i,j)-O(i,j)$.

We have $dp(0,0)=1$ and $dp(0,x)=0$ for all other $x$. By considering all possible values of the last number in the sequence, we can obtain the recurrence
\[dp(i,j) = (-1)^{j}\sum_{k=0}^{j}dp(i-1,k)\]for all $j \le b_i$. Define $dp(i,j)=0$ elsewhere.

The key claim is that for all $i,j$, we have $dp(i,2j) \ge 0$, $dp(i,2j+1) \le 0$ and $|dp(i,2j+1)| \le |dp(i,2j)|$. We will prove this by induction.

Observe that this is true for $i=0$. Suppose it is true for all smaller $i$. If $2j > b_i$, we are done. Otherwise, letting $S=\displaystyle\sum_{k=0}^{2j-1}dp(i-1,k)$, $a = dp(i-1,2j) \ge 0$ and $b = -dp(i-1,2j+1) \ge 0$ (with $a \ge b$), we obtain
$dp(i,2j) = S+a$, $dp(i,2j+1)=-(S+a-b)$ (or $0$ if $2j+1>b_i$). In any case, $dp(i,2j) \ge 0$, $dp(i,2j+1) \le 0$ and $|dp(i,2j+1)| \le |dp(i,2j)|$, as desired.

It remains to note that the difference between the number of stable subsets of $S$ with even elements and those with odd elements is just $\displaystyle\sum_{k=0}^{b_n}dp(n,k)$, which is clearly nonnegative by our claim.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6836 posts
#12 • 13 Y
Y by SK_pi3145, mobro, Math_olympics, Rg230403, Pluto04, Mathematicsislovely, Atpar, v4913, a_friendwr_a, Muaaz.SY, hwdaniel, enzoP14, HamstPan38825
Current draft of official solution, given by Nikolai Beluhov:

We proceed by induction on $|S|$, with $|S| \le 1$ clear.
Suppose $|S| \ge 2$. For any $p \in S$, let $R(p)$ denote the stable rectangle with upper-right corner $p$. We say such $p$ is pivotal if $p + (1, 1) \notin S$ and $|R(p)|$ is even.
[asy] 	path R = box( (0,0), (6,3) ); 	fill(R, palered); 	fill(shift(5,2)*unitsquare, lightcyan); 	label("$p$", (5.5,2.5)); 	for (int i=0; i<=0; ++i) { 		draw(shift(i,5)*unitsquare); 	} 	for (int i=0; i<=1; ++i) { 		draw(shift(i,4)*unitsquare); 	} 	for (int i=0; i<=3; ++i) { 		draw(shift(i,3)*unitsquare); 	} 	for (int i=0; i<=7; ++i) { 		draw(shift(i,2)*unitsquare); 	} 	for (int i=0; i<=10; ++i) { 		draw(shift(i,1)*unitsquare); 	} 	for (int i=0; i<=10; ++i) { 		draw(shift(i,0)*unitsquare); 	} 	draw(R, heavyred+1.5); [/asy]

Claim: If $|S| \ge 2$, then a pivotal $p$ always exists.
Proof. Consider the top row of $S$.
  • If it has length at least $2$, one of the two rightmost points in it is pivotal.
  • Otherwise, the top row has length $1$. Now either the top point or the point below it (which exists as $|S| \ge 2$) is pivotal. \qedhere
$\blacksquare$
We describe how to complete the induction, given some pivotal $p \in S$. There is a partition \[ S = R(p) \sqcup S_1 \sqcup S_2 \]where $S_1$ and $S_2$ are the sets of points in $S$ above and to the right of $p$ (possibly empty).

Claim: The desired inequality holds for stable subsets containing $p$.
Proof. Let $E_1$ denote the number of even stable subsets of $S_1$; denote $E_2$, $O_1$, $O_2$ analogously. The stable subsets containing $p$ are exactly $R(p) \sqcup T_1 \sqcup T_2$, where $T_1 \subseteq S_1$ and $T_2 \subseteq S_2$ are stable.
Since $|R(p)|$ is even, exactly $E_1E_2 + O_1O_2$ stable subsets containing $p$ are even, and exactly $E_1O_2 + E_2O_1$ are odd. As $E_1 \ge O_1$ and $E_2 \ge O_2$ by inductive hypothesis, we obtain $E_1E_2 + O_1O_2 \ge E_1O_2 + E_2O_1$ as desired. $\blacksquare$
By the inductive hypothesis, the desired inequality also holds for stable subsets not containing $p$, so 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.
TheUltimate123
1738 posts
#13 • 1 Y
Y by Combigeontal231
We proceed by strong induction on \(|S|\), with base case \(S=\varnothing\).

The problem is trivial if all points of \(S\) have \(x\)-coordinate 1. Let \(P\in S\) be the point with \(x\)-coordinate 2 and maximum possible \(y\)-coordinate, and let \(A\) be the rectangle with bottom-left corner \((1,1)\) and upper-right corner \(P\). Let \(B\) be the subset of \(S\) above \(A\) and \(C\) the subset of \(S\) to the right of \(C\). Hence \(S=A\sqcup B\sqcup C\).

[asy]         size(4cm); defaultpen(fontsize(10pt));         draw( (1,0)--(1,3),gray); draw( (2,0)--(2,2),gray); draw( (3,0)--(3,1),gray);         draw( (0,1)--(3,1),gray); draw( (0,2)--(2,2),gray);         for (int i=3; i<7; i+=1) draw( (0,i)--(1,i),gray);

fill( (0,3)--(0,7)--(1,7)--(1,3)--cycle,invisible);         draw( (0,3)--(0,7)--(1,7)--(1,3),heavygreen+linewidth(1));         filldraw( (0,0)--(0,3)--(2,3)--(2,0)--cycle,invisible,blue+linewidth(1));         fill( (2,2)--(3,2)--(3,1)--(4,1)--(4,0)--(2,0)--cycle,invisible);         draw( (2,2)--(3,2)--(3,1)--(4,1)--(4,0)--(2,0),red+linewidth(1));         real t=.1; filldraw( (1+t,2+t)--(2-t,2+t)--(2-t,3-t)--(1+t,3-t)--cycle,invisible,purple+linewidth(1));

label("\(A\)",(0,1.5),W,blue);         label("\(B\)",(0,5),W,heavygreen);         label("\(C\)",(3,0),S,red);         label("\(P\)",(2,3),NE,purple);     [/asy]
  • Among subsets not containing \(P\), at least half contain an even number of elements by the inductive hypothesis.
  • Focus on subsets containing \(P\) (and thus all of \(A\)). Let \(p_B\ge\frac12\) be the probability a subset of \(B\) contains an even number of elements and \(p_C\ge\frac12\) be the probability a subset of \(C\) contains an even number of elements. Then the probability a subset of \(S\) containing \(P\) contains an even number of elements is \[p_Bp_C+(1-p_B)(1-p_C)=\frac{1+(2p_B-1)(2p_C-1)}2\ge\frac12,\]as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
guptaamitu1
655 posts
#14
Y by
Suppose that $n$ is the largest number such that the $n\text{-th}$ row contains at least one point. For $1\le i \le n$, let $a_i$ be the number of points in the $i \text{-th}$ row. Clearly, $a_1 \ge a_2 \ge \cdots \ge a_n$. In this configuration, define $f(a_1,a_2,\dots,a_n)$ to be the number of stable subsets having an even number of elements minus the number of stable subsets having an odd number of elements (note that inside $f$, there might some $0$'s occasionally, and in that case, you just have to ignore them (of course, $0$'s cannot be between positive integers). Here we are defining $n$ just for convenience and we also (again for convenience) let $f(0,0,\dots)=1$). We want to prove that the values of $f$ are always non-negative. First we claim that for all $n \ge 2$,
$$f(a_1,a_2,\dots,a_n) = \sum_{i=0}^{a_n} (-1)^{in} f(a_1-i,a_2-i,\dots,a_{n-1}-i) $$Indeed, if we assume that $i$ elements of the top row are chosen in that stable subset, then we will then have to choose some points from a set of points where in the $i \text{-th}$ row ($1 \le i \le n-1$), there are $a_i - i$ points, and we have already chosen $in$ points, so from here, our claim follows.
LEMMA: $f(a_1,a_2,\dots,a_n) \ge 0$ for odd $n$ ; $f(a_1,a_2,\dots,a_n) \ge f(a_1-1,a_2-1,\dots,a_n-1) \ge 0$ for even $n$
PROOF: This is an easy induction on $n$ by using the recurrence.

Can someone please check my solution and tell whether it is fine or not
This post has been edited 1 time. Last edited by guptaamitu1, Apr 29, 2021, 5:35 PM
Reason: .
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
508669
1040 posts
#15
Y by
willwin4sure wrote:
Let $\mathbb{N}^2$ denote the set of ordered pairs of positive integers. A finite subset $S$ of $\mathbb{N}^2$ is stable if whenever $(x,y)$ is in $S$, then so are all points $(x',y')$ of $\mathbb{N}^2$ with both $x'\leq x$ and $y'\leq y$.

Prove that if $S$ is a stable set, then among all stable subsets of $S$ (including the empty set and $S$ itself), at least half of them have an even number of elements.

Ashwin Sah and Mehtaab Sawhney

Same as few of the above solutions but wadev posting for storage.

We induct on $n$, the number of elements in $S$. We give this problem a representation in the cartesian plane for our convenience. We see that the base case $n = 1$ is trivial. Let us say that for all positive integers $k \leq n$, if $S$ has exactly $k$ elements, then the given result holds true. Consider a set $S$ with $n+1$ elements.

We impose the cartesian plane representation on the elements of $S$. Here is a sample diagram for $S$ for convenience in explanation.

[asy]
 /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */
import graph; size(10cm); 
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ 
pen dotstyle = black; /* point style */ 
real xmin = -5.298405797293469, xmax = 16.332783342012227, ymin = -3.2076286890721635, ymax = 10.151510615775093;  /* image dimensions */

 /* draw figures */
fill(shift((3,3)) * rotate(90) * scale(0.1411111111111111) * ((1,0)--expi(2*pi/3)--expi(4*pi/3)--cycle)); /* special point */
fill(shift((6,1)) * rotate(90) * scale(0.1411111111111111) * ((1,0)--expi(2*pi/3)--expi(4*pi/3)--cycle)); /* special point */
fill(shift((5,2)) * rotate(90) * scale(0.1411111111111111) * ((1,0)--expi(2*pi/3)--expi(4*pi/3)--cycle)); /* special point */
fill(shift((1,6)) * rotate(90) * scale(0.1411111111111111) * ((1,0)--expi(2*pi/3)--expi(4*pi/3)--cycle)); /* special point */
 /* dots and labels */
dot((0,6),linewidth(4pt) + dotstyle); 
dot((0,5),linewidth(4pt) + dotstyle); 
dot((0,4),linewidth(4pt) + dotstyle); 
dot((0,3),linewidth(4pt) + dotstyle); 
dot((0,2),linewidth(4pt) + dotstyle); 
dot((0,1),linewidth(4pt) + dotstyle); 
dot((0,0),linewidth(4pt) + dotstyle); 
dot((1,4),linewidth(4pt) + dotstyle); 
dot((1,3),linewidth(4pt) + dotstyle); 
dot((1,2),linewidth(4pt) + dotstyle); 
dot((1,1),linewidth(4pt) + dotstyle); 
dot((1,0),linewidth(4pt) + dotstyle); 
dot((2,3),linewidth(4pt) + dotstyle); 
dot((2,2),linewidth(4pt) + dotstyle); 
dot((2,1),linewidth(4pt) + dotstyle); 
dot((2,0),linewidth(4pt) + dotstyle); 
dot((3,2),linewidth(4pt) + dotstyle); 
dot((3,1),linewidth(4pt) + dotstyle); 
dot((3,0),linewidth(4pt) + dotstyle); 
dot((4,2),linewidth(4pt) + dotstyle); 
dot((4,1),linewidth(4pt) + dotstyle); 
dot((4,0),linewidth(4pt) + dotstyle); 
dot((5,1),linewidth(4pt) + dotstyle); 
dot((5,0),linewidth(4pt) + dotstyle); 
dot((6,0),linewidth(4pt) + dotstyle); 
dot((7,0),linewidth(4pt) + dotstyle); 
dot((8,0),linewidth(4pt) + dotstyle); 
dot((2,4),linewidth(4pt) + dotstyle); 
dot((0,7),linewidth(4pt) + dotstyle); 
dot((1,5),linewidth(4pt) + dotstyle); 
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); 
 /* end of picture */
[/asy]

Let $\mathbb{S}$ be the set of lattice points whose ordinate and abcissa when written in this order forms an element of the set $S$. We call a lattice point $X \equiv (a, b) \in \mathbb{S}$ as 'even-oriented', if either the abcissa or the ordinate of $X$ is even (that is $2 \mid ab$) and the diagonally adjacent lattice point of $X$ in the north-east direction does not belong to $\mathbb{S}$. The triangle shaped lattice points in the above diagram are few of the even-oriented lattice points in the above diagram.

We see that if $\mathbb{S}$ does not contain any even-oriented lattice point, then consider $\mathbb{S}$ with minimal number of lattices points in it (it can be confirmed that $\mathbb{S} \geq 5$ in this case) it must follow that the lattice point with largest abcissa if removed forms a set $\mathbb{S}_1$ with no even-oriented lattice point and lesser number of lattice points than $\mathbb{S}$, contradicting minimality of $\mathbb{S}$, which means that the every such set of lattices points $\mathbb{S}$ must contain an even-oriented point. Consider any even-oriented lattice point $V \in \mathbb{S}$, for our above diagram, we consider $V \equiv (4, 4)$ which is marked by a triangle. We observe that if a stable subset of $\mathbb{S}$ contains $V$, consider sets of lattice points $\mathbb{S}_1$ and $\mathbb{S}_2$ of points such that if $V_1 \in \mathbb{S}_1$ and $V_2 \in \mathbb{S}_2$, then $\text{abcissa}(V_1) > \text{abcissa}(V)$ and $\text{ordinate}(V_2) > \text{ordinate}(V)$. Due to our definition of even-oriented point, it can be confirmed that $S_1 \cap S_2 = \varphi$. We denote $f(S')$ to be the number of stable subsets of a set $S'$ containing even number of elements and let $g(S')$ be the number of stable subsets of $S'$ containing odd number of elements. We see that number of stable subsets of $\mathbb{S}$ containing $V$ and having even number of elements are $f(\mathbb{S}_1)f(\mathbb{S}_2) + g(\mathbb{S}_1)g(\mathbb{S}_2)$ and number of stable subsets of $\mathbb{S}$ containing $V$ and having odd number of elements are $f(\mathbb{S}_1)g(\mathbb{S}_2) + g(\mathbb{S}_1)f(\mathbb{S}_2)$, due to Re-arrangement Inequality, we see that since $f(\mathbb{S}_1) \geq g(\mathbb{S}_1)$ and $f(\mathbb{S}_2) \geq g(\mathbb{S}_2)$ due to our induction hypothesis, we see that $f(\mathbb{S}_1)f(\mathbb{S}_2) + g(\mathbb{S}_1)g(\mathbb{S}_2) \geq f(\mathbb{S}_1)g(\mathbb{S}_2)+f(\mathbb{S}_2)g(\mathbb{S}_1)$. If a stable subset of $\mathbb{S}$ does not contain $V$, then induct and finish the problem. Overall, we get that more than half the number of stable subsets of $\mathbb{S}$ have even number of elements, as desired.

A healthy note : We are interested in even-oriented vertices, in my case personally I am interested to look into even-oriented vertices because then number of even-element subsets of $\mathbb{S}$ is $f(\mathbb{S}_1)f(\mathbb{S}_2) + g(\mathbb{S}_1)g(\mathbb{S}_2)$ which strikes thought for Re-arrangement Inequality, here is my motivation to consider such points. I agree the solution is kinda same as official solution but the approach for proof for the existence of even-oriented points are different, that is only reason I posted this solution. Though writing the proof for this lemma properly on a sheet of paper might be troublesome but wadev this is APoS. Also I have solved this problem way back when the TSTST problems were released but I forgot my solution so here we go, new day different approach.
This post has been edited 4 times. Last edited by 508669, Jul 17, 2021, 12:23 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
4983 posts
#16
Y by
We use strong downwards induction. Define the skin of a stable set $S$ to be the set of all points $(x,y)$ in $S$ such that $(x+1,y+1)$ isn't in $S$. it is easy to see that if the skin of $S$ contains at least two points, one of them must have either $x$ or $y$ coordinate even, and the only stable set with a skin containing a single point is $\{(1,1)\}$.
For the base case, we can easily verify that the statement holds if $|S|=0,1$.
For the inductive step, suppose $|S| \geq 2$, so the skin of $S$ contains at least two points. Pick some point $P=(x,y)$ in the skin of $S$ with one of its coordinates even. We count the number of stable sets $S' \subseteq S$ based on whether or not they contain $P$:
  • If $P \in S'$, let $R$ denote the rectangle with corners $(1,1)$ and $P=(x,y)$, which contains $xy$ points—an even number. Clearly $R \in S'$, and $S \setminus R$ can be partitioned into two non-adjacent stable subsets $S_1,S_2$. If $S_1$ has $e_1\geq o_1$ stable subsets of even and odd size respectively and $e_2\geq o_2$ are defined similarly (where the inequalities come from inductive hypothesis), then by rearrangement (!) we have $e_1o_1+e_2o_2 \geq e_1o_2+e_2o_1$, so there are at least as many subsets $S'$ with an even number of elements than an odd number of elements.
  • If $P \not \in S'$, then any points above or to the right of $P$ are not in $S'$. Delete these points (including $P$) to get a smaller stable set that $S'$ must be the subset of. By inductive hypothesis there at least as many choices for $S'$ such that $|S'|$ is even than such that $|S'|$ is odd.
Combining these two cases, it follows that overall at least half of the choices for $S'$ have an even number of elements, as desired. $\blacksquare$
This post has been edited 1 time. Last edited by IAmTheHazard, Apr 4, 2022, 2:26 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
NoctNight
108 posts
#17
Y by
Same as most solutions above.

Use strong induction on $\lvert S\rvert$. The base cases $\lvert S\rvert =0,1$ are trivial. We will prove that if $S_e$ and $S_o$ are the number of even and odd-element stable subsets of $S$, then $f(S)=S_e-S_o\geq 0$.

Say that a point $(x,y)\in S$ is dominant if no other $(x',y')\in S$ satisfies $x'> x, y'> y$.

Consider dominant $(X,Y)$ from a stable set $S$ to form a new stable $S'$ - choose one of $X,Y$ to be even (which is possible since for any dominant $(x,y)$, we have that one of $(x-1,y), (x,y-1),(x+1,y),(x,y+1)$ must be dominant, and we know $\lvert S\rvert \geq2$.

Consider the subset $T\subseteq S$ of lattice points $(x', y')$ satisfying $x'\leq X, y'\leq Y$. Then $S\backslash T$ consists of two (potentially empty) disjoint stable subsets $A, B$. Then, by counting the stable subsets of $S'$ and the stable subsets $M$ of $S$ such that $M\not\subseteq S'$ (which must contain $(X,Y)$):
$$f(S)=S_e-S_o=f(S') + A_eB_e + A_oB_o-A_eB_o-A_oB_e=f(S')+(A_e-A_o)(B_e-B_o)=f(S')+f(A)f(B)\geq 0$$by the inductive assumption, completing the inductive step.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dolphinday
1254 posts
#18
Y by
Call a subset even if it has an even number of elements and odd, similarly.
The case where $|S| = 1$ thus $S = (1, 1)$ is true so we will ignore it.
We will work in the coordinate lattice plan with $(x, y)$ matching with its corresponding lattice point. We will do strong induction on $|S|$.
Let the barrier of $S$ be the set of points so that $(x + 1, y + 1)$ is not in $S$.
Then choose a point $P$ so that one of its coordinates $(x, y)$ are even. Note this clearly exists as there are at least two points on the barrier of $S$ which are adjacent.
Then let $R$ be the rectangle with $P$ and $(1, 1)$ as opposite corners, and let $A$ be the region above $P$ and $B$ the region to the right of $P$ so that $A \sqcup B \sqcup R = S$. Let $e_A$ and $e_B$ be the number of even subsets of $A$ and $B$ and $o_A, o_B$ for odd subsets similarly. Then the number of even subsets containing $P$ is $e_Ae_B + o_Ao_B$ and similarly the odd subsets are $e_Ao_B + e_Bo_A$ and by rearrangement inequality we have the number of even subsets being larger than the odd subsets due to $e_A \geq o_A, e_B \geq o_B$(induct. hypothesis).
Thus all subsets containing $P$ fit the criteria. If the subset does not contain $P$ then we are done by induction.

i wanted to add that this problem gave me an actual headache, I don't like it
This post has been edited 1 time. Last edited by dolphinday, Mar 20, 2024, 9:11 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shendrew7
722 posts
#19
Y by
Consider a point $P(u,v)$ on the "edge" of our stable set (such that $(u+1,v+1)$ is not in the set) with at least one even coordinate, which can be seen to exist. We use casework on $P$:
  • $P$ is not in the subset: We simply have a smaller stable set.
  • $P$ is in the subset: We must have the $uv$ points in the rectangle with opposite vertices $(0,0)$ and $P$, which is even. The remainder of our set is two smaller stable sets along the $x$- and $y$-axes, which we label $S_1$ and $S_2$. Then we require the inequality
    \[e_1e_2 + o_1o_2 \ge e_1o_2 + e_2o_1,\]where $e_i$/$o_i$ represent the number of even/odd element subsets of $S_i$. It suffices to have $e_1 \ge o_1$ and $e_2 \ge o_2$ by Rearrangement.
Thus we can finish by continuing downwards. $\blacksquare$
This post has been edited 1 time. Last edited by shendrew7, Apr 1, 2024, 4:40 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
vsamc
3769 posts
#20
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.
kes0716
4 posts
#21
Y by
If $S$ is the empty set, there is nothing to prove. Otherwise, denoting $X:= \max_{(x,y)\in S}x$ and $Y_i := \max_{(i,y)\in S}y(1 \leq i \leq X)$, it is clear that $S=\{(x, y)  | 1\leq x\leq X, 1\leq y\leq Y_x\}$. For every $1\leq x\leq X, 0\leq y\leq X_x$, denote by $a_{x,y}$ the number of stable subsets of $ \{(x',y')|1\leq x' \leq X, (x',y')\in S\}$ containing $(x, y)$(this constraint is omitted for $y=0$) with even cardinality minus the number of such subsets with odd cardinality. For convenience, define $a_{0,y}=1(0\leq y\leq Y)$ and $a_{x,y}=0$ for $(x,y)$ which $a_{x,y}$ is not defined yet. When computing $a_{x,y}$, if $(x,y+1)$ is in the desired subset, then the corresponding value is $a_{x,y+1}$. Otherwise, the subset already contains $y$ elements with x-grid $x$, and the rest is a stable subset consisting of x-grid less than $x$ that contains $(x-1,y)$ . In symbols, we get the recurrence relation $a_{x,y}=a_{x,y+1}+(-1)^ya_{x-1,y}(1\leq x\leq X, 0\leq y\leq X_x)$ .
We claim that for any $0\leq x \leq X$,
- if $x$ is even, $a_{x, 0}\geq a_{x, 1}\geq \cdots \geq a_{x, Y_x} \geq 0$.
- if $x$ is odd, then $a_{x,y}\geq0$ for $y$ even and $a_{x,y}\leq0$ for $y$ odd.
The proof goes by induction. The base case $x=0$ is trivial. Supposing the claim holds for $x<X$,
- if $x$ is even, $a_{x+1,y}=\sum_{i=y}^{\infty}(-1)^ya_{x,y}$ is an alternating series whose terms' absolute values are non-increasing and eventually becomes zero, so $a_{x+1,y}$ is non-negative if the first term is non-negative($y$ even) and non-positive if the first term is non-positive ($y$ odd) as desired.
- if $x$ is odd, all terms in the series $a_{x+1,y}=\sum_{i=y}^{\infty}(-1)^ya_{x,y}$ are positive, so it is immediate that $a_{x+1,y}$ are all positive and do not decrease as $y$ decreases.
In particular, $a_{X,0}\geq0$, finishing the proof.
This post has been edited 3 times. Last edited by kes0716, Yesterday at 12:35 PM
Z K Y
N Quick Reply
G
H
=
a