\documentclass[a4paper]{article}
\usepackage[margin=0.5in]{geometry}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}

\setlength{\parindent}{0em}

\title{\textbf{COMP90056 Assignment A}}
\author{Tingsheng (Tinson) Lai (731319)}
\date{\today}

\begin{document}
    \maketitle
    \section{Part 1}
    Let $S$ denotes the union, i.e. $$S = S_1 \cup S_2$$
    From the inequality, we can claim that the inequality inherently holds for $\forall x \in S \backslash S_2$ and $\forall x \in S \backslash S_1$. So the only task is to prove that the inequality holds for the third circumstance where $$\forall x \in S_1 \cap S_2$$
    Use $\hat{S}$ as the intersection $$\hat{S} = S_1 \cap S_2$$
    First prove the $RHS$ where $\forall x \in \hat{Z}$ $\hat{c} \left( x \right) \leq f_{x}$. As $x \in S_1 \wedge x \in S_2$, we know that $\hat{c}_1 \left( x \right) \leq f_{1,x}$ and $\hat{c}_2 \left( x \right) \leq f_{2,x}$. So $$\hat{c} \left( x \right) = \hat{c}_1 \left( x \right) + \hat{c}_2 \left( x \right) \leq f_{1,x} + f_{2,x} = f_{x}$$
    Even if the subtraction to shrink the size happens, the $RHS$ still holds as $\forall i \in \mathbb{U}$, $f_{i}$ will not be changed throughout the whole process. For the $LHS$, using the same trick we can get $$f_{1,x} - \frac{m_1 - \tau_1}{k_1} + f_{2,x} - \frac{m_2 - \tau_2}{k_2} = f_x - \frac{m - \tau}{x}$$ So $$\hat{c} \left( x \right) \geq f_x - \frac{m - r}{k} = LHS$$ Subtracting $a$ from each $x \in S$ will decrease the value of $\tau$ by at least $k \cdot a$. Denoting $\Delta \hat{c}_x$ = -a as the change in the counter and $\Delta \tau$ as the change in $\tau \leq -a \cdot k$. It is clear that $f_x$ and $m$ and $k$ are fixed, so $\Delta LHS \leq -a$. So the decrease in the $LHS$ are even greater than $\hat{c} \left( x \right)$, so the inequality still holds.
\end{document}
