Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3

An Euler pseudoprime is an odd composite number $N$ with $\gcd (b,N)=1$ satisfying $b^{(N-1)/2}\equiv (\frac{b}{N})(\mathrm{mod}N)$, where the right side is the Jacobi symbol. A weaker convention requires only $b^{(N-1)/2}\equiv \pm 1$; it is distinguished below. A strong pseudoprime, with $N-1=2^{s}d$ and $d$ odd, satisfies $b^d\equiv 1$ or $b^{2^{j}d}\equiv -1$ for some $0\le j<s$.

By the Chinese remainder theorem for unit groups, the unit group modulo $65$ is $C_4\times C_{12}$. Modulo $5$, $b^{32}=1$. Thus the only possible sign in $b^{32}\equiv \pm 1(\mathrm{mod}65)$ is positive. Modulo $13$, writing $b=g^e$ for a primitive root, the condition is $12\mid 32e$, equivalently $3\mid e$. Consequently $b$ has multiplicative order dividing $4$ in each factor. Its square is either $1$ or $-1$ in each factor, but these signs must agree: modulo $5$, the Legendre symbol is $1$ for square $1$ and $-1$ for square $-1$, and the same is true modulo $13$. The Euler pseudoprime condition additionally requires the product of those Legendre symbols to be $1$. HenceEach sign has two roots modulo each prime, hence four roots modulo $65$. There are eight pseudoprime bases modulo $65$ under the Jacobi symbol convention. Under the weaker sign-only convention there are instead sixteen pseudoprime bases, since the two signs of the squares need not agree; the stated equivalence therefore specifically uses the Jacobi symbol convention.

For the strong pseudoprime condition, $s=6,d=1$. Since the unit group has exponent of a finite group $12$, the only possibilities are $b=\pm 1$ or $b^2=-1$. The six pseudoprime bases are $1,8,18,47,57,64$. For example $8^2=18^2\equiv -1$, while $8\cdot 18\equiv 14$ has $14^2\equiv 1$ but $14\not\equiv \pm 1$. Thus the strong-pseudoprime pseudoprime bases are not a subgroup.

Let $D$ be the closed unit disc and setThe displacement bound gives $\Vert f(x)\Vert \le 1$, so $f:D\to D$ is continuous. The Brouwer fixed-point theorem applies because $D$ is nonempty, compact and convex. At a fixed point $x_{\ast }$, $x_{\ast }=x_{\ast }-g(K{x}_{\ast })/K$. Therefore $\boxed{t=K{x}_{\ast },g(t)=0}$.

For arbitrary $y\in {\mathbb{R}}^2$, the continuous map $g_y(x)=g(x)-y$ satisfies $\Vert g_y(x)-x\Vert \le K+\Vert y\Vert$. Applying the preceding Brouwer fixed-point theorem argument with this positive bound gives $g_y(t)=0$. Hence $g(t)=y$, and $g$ is surjective.

Let $e=(1,0)$ and defineThen $\Vert g(x)-x\Vert \le 1$ everywhere, but $0$ is not in the image of a function. The map is discontinuous at $0$, giving a bounded-displacement map which is not surjective.

Identify a binary word with its coefficient polynomial in $R={\mathbb{F}}_2[X]/(X^7-1)$. A cyclic code is exactly an ideal of $R$: closure under multiplication by $X$ is closure under cyclic shift. Its inverse image in the principal ideal domain ${\mathbb{F}}_2[X]$ has a unique monic generator polynomial of a cyclic code $g$ dividing $X^7-1$. PutThe cubics have no root in ${\mathbb{F}}_2$, hence are irreducible polynomials. The eight monic divisors yield all binary cyclic codes of length seven. A code generated by $g$ has basis $g,Xg,\dots ,X^{6-\mathrm{deg}g}g$ and dimension $7-\mathrm{deg}g$, with the zero code treated separately.

For the dual of a cyclic code, let $h=(X^7-1)/g$. Orthogonality of coefficient vectors to all cyclic shifts gives the generator $h^{\ast }(X)=X^{\mathrm{deg}h}h(X^{-1})$. Here $a^{\ast }=a,b^{\ast }=c,c^{\ast }=b$. Thus the complete pairing, with the respective dimensions, isThese are respectively the whole-space/zero, even-weight/repetition, and two Hamming code/binary simplex code pairs. The reciprocal formula follows because the product of a word polynomial and the reversed polynomial of an orthogonal word has zero coefficients in all cyclic positions; the resulting inclusion has the correct complementary dimension, hence is equality.

In strict Chomsky normal form, every production of a context-free grammar is $A\to BC$ or $A\to a$, with $A,B,C$ nonterminal symbols and $a$ a terminal symbol. Such a derivation cannot produce the empty word: it starts with one nonterminal symbol, and every step either increases the symbol count or replaces one symbol by one symbol. The context-free language $\{\epsilon \}$, generated by $S\to \epsilon$, is therefore not generated by any strict CNF grammar.

The convention matters: extended Chomsky normal form permits $S\to \epsilon$ with $S$ excluded from right-hand sides. Under that convention every context-free language has such a grammar, so the requested example would not exist.

The context-free languages $L_1=\{a^n{b}^n{c}^m:n,m\ge 0\}$ and $L_2=\{a^m{b}^n{c}^n:n,m\ge 0\}$ have context-free grammars $S\to TC$, $T\to aTb\mid \epsilon$, $C\to cC\mid \epsilon$, and $S\to AT$, $A\to aA\mid \epsilon$, $T\to bTc\mid \epsilon$, respectively.

Their intersection is $L=\{a^n{b}^n{c}^n:n\ge 0\}$. Suppose $L$ satisfied the pumping lemma for context-free languages with length $p$. In a decomposition $a^p{b}^p{c}^p=uvwxy$ with $|vwx|\le p$ and $|vx|>0$, the window $vwx$ cannot meet both the $a$ and $c$ blocks. Pumping down changes at least one count and leaves at least one count unchanged. Thus the three counts are unequal, or the word order is invalid, contrary to the pumping lemma for context-free languages. Hence CFLs are not closed under intersection.

Context-free languages are closed under union: use a new start symbol with alternatives for two renamed context-free grammars. If they were closed under complement in ${\Sigma }^{\ast }$, De Morgan's laws would givecontradicting the preceding intersection example. Therefore some CFL has a non-context-free complement. This is an existence argument; it does not assert that both complements of the particular $L_1,L_2$ are non-context-free.

A concrete choice is $L=\{a,b,c{\}}^{\ast }\setminus \{a^n{b}^n{c}^n:n\ge 0\}$. Words outside $a^{\ast }{b}^{\ast }{c}^{\ast }$ form a regular language. Among words inside it, membership in $L$ means the first two counts or the last two counts differ. Each unequal-count comparison has a context-free grammar: for $a^i{b}^j$ with $i>j$, use $T\to aTb\mid A$, $A\to aA\mid a$; for $i<j$, replace $A$ by $B\to bB\mid b$. Append any number of $c$'s, or prefix any number of $a$'s for the analogous $b,c$ comparison. Taking these unions gives a context-free language whose complement is the non-context-free equal-three-count language. These productions are definitions of the example, not a restriction to strict Chomsky normal form.

Write $\ell (\beta )$ for the log-likelihood and $U=\nabla \ell$ for the score function. Newton method uses the Observed Fisher information $M=-{\nabla }^2\ell$; Fisher scoring uses the Fisher information $M={\mathbb{E}}_{\beta }[-{\nabla }^2\ell ]$.

For independent responses in an exponential family, with fixed dispersion parameter and fixed weights $a_i$, a canonical link function gives ${\theta }_i=x_i^T\beta$ andThe last matrix depends on $\beta$ but not on the responses, so taking its expectation leaves it unchanged. Hence the two updates are identical, wherever this Fisher information matrix is invertible. Equivalently both solve the same iteratively reweighted least squares problem. This statement concerns the regression coefficients at a fixed dispersion parameter; a joint update of an unknown dispersion parameter need not have identical observed and expected full Fisher information matrices.

In the birth-death master equation, The upward jump has rate $\lambda$ and the downward jump rate $\beta x$, so the first two jump moments per unit time are $A(x)=\lambda -\beta x$ and $B(x)=\lambda +\beta x$. The second-order Kramers-Moyal expansion gives the diffusion approximation of a birth-death processFor the associated Fokker-Planck equation, integrating by parts with vanishing moment boundary terms gives $d⟨f⟩/dt=⟨A{f}^{\prime }+\frac{1}{2}B{f}^{\prime \prime }⟩$. Taking $f=x,x^2$ yieldsFor example, if $m_0=⟨x(0)⟩$, then $m(t)=\lambda /\beta +(m_0-\lambda /\beta )e^{-\beta t}$, while the variance satisfies $v^{\prime }=-2\beta v+\lambda +\beta m$. The two boxed moment equations also follow exactly from the discrete Markov jump-process generator, since quadratic functions have no higher jump terms. A reflecting diffusion confined to $x\ge 0$ can have extra boundary contributions; the formal approximation near extinction is not an exact replacement for the discrete process.

After division by $z$, the coefficients are $P=2/z-1$ and $Q=-1/z$. At $0$, $zP$ and $z^{2}Q$ are analytic functions, so $0$ is a regular singular point. Its indicial equation is $r(r-1)+2r=r(r+1)=0$. There are no other finite singular points of a differential equation. At infinity the regular singular point criterion for a second-order equation would require $P=O(z^{-1})$, but $P\to -1$; hence infinity is an irregular singular point.

Substituting $y=f/z$ reduces the equation to $f^{\prime \prime }-f^{\prime }=0$, soA linearly independent pair is $1/z$ and $(e^z-1)/z$. Their Wronskian is $e^z/z^2\ne 0$. The second has a removable singularity at $0$ and value $1$, whereas the first has a simple pole, agreeing with the two characteristic exponents at a regular singular point, $0,-1$. The integer difference does not require a logarithm. At infinity $e^z/z$ has an essential singularity, consistent with the irregular singular point; the existence of the simpler solution $1/z$ does not make infinity regular.

Liouville integrability on a $2n$-dimensional symplectic manifold means that there are $n$ functionally independent first integrals, including $H$, whose pairwise Poisson brackets vanish. Near a compact connected regular common level set, the Arnold-Liouville theorem gives action-angle variables $(J_i,{\theta }_i)$ with $J_i=(2\pi {)}^{-1}\oint pdq$, ${\theta }_i$ periodic modulo $2\pi$, $H=H(J)$, ${\dot{J}}_i=0$ and ${\dot{\theta }}_i=\partial H/\partial J_i$.

For a frozen mass, the turning point is $q_{\ast }=(2E{)}^{1/(2k)}$. The action variable isAdiabatic invariance of the action holds to leading order when the mass varies slowly compared with an orbital period, away from degenerating orbits. Keeping $J$ fixed givesFor $k=1$ this agrees with $E=\omega J$ and $\omega \propto m^{-1/2}$.

Chemical equilibrium imposes ${\mu }_e+{\mu }_p={\mu }_H+{\mu }_{\gamma }$. For blackbody photons, ${\mu }_{\gamma }=0$. Define the positive Hydrogen binding energy by $I=(m_e+m_p-m_H)c^2$, approximately $13.6\mathrm{eV}$. Multiplying the two Maxwell-Boltzmann distribution number densities and dividing by the neutral-hydrogen density givesUse $g_e{g}_p/g_H=1$ and $m_p/m_H\simeq 1$ to obtain the Saha ionization equationThe assumptions are nonrelativistic, dilute, nondegenerate species at a common temperature, ground-state hydrogen with the stated degeneracy factors, negligible mass correction in the prefactor, and sufficiently rapid reactions to maintain chemical equilibrium.

The baryon-to-photon ratio is extremely small, of order $10^{-9}$. Thus even when the typical photon energy is below $I$, the high-energy tail of the blackbody radiation contains enough photons above the ionization energy to reionize almost every newly formed hydrogen atom. Cosmological recombination becomes effective only when this exponentially small tail is also small compared with the baryon-to-photon ratio. Consequently recombination occurs at a temperature much lower than $I/k$, consistent with $kT\simeq 0.03I$. The exact freeze-out history also depends on reaction rates and expansion; the equilibrium estimate explains the large suppression of the temperature.

Set $p_{-2}=0,p_{-1}=1,q_{-2}=1,q_{-1}=0$ and define the continued fraction convergents byThe recurrence reverses the sign of $p_n{q}_{n-1}-p_{n-1}{q}_n$, whose initial value at $n=0$ is $-1$. Hence $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n-1}$. Every common divisor of $p_n,q_n$ divides this number, proving $\boxed{\gcd (p_n,q_n)=1}$.

Let $D_n=p_{n-1}{q}_{n-2}-p_{n-2}{q}_{n-1}=(-1{)}^{n-2}$. Solving the given Möbius transformation for the complete quotient and rationalizing givesThereforeThe denominator $D_n$ is $\pm 1$, so both are integers. The algebraic norm denominator is nonzero because $\sqrt{d}$ is an irrational number.

Use the periodic continued fraction $\sqrt{d}=[a_0;\overline{a_1,\dots ,a_m}]$. A direct matrix argument avoids any assumption about the parity of the period. LetPeriodicity says that $M$ fixes ${\theta }_1$ as a Möbius transformation, while $B$ takes ${\theta }_1$ to $\sqrt{d}$. Thus $N=\left(\begin{array}{cc}A& B_1\\ C& D\end{array}\right)$ has integer entries and fixes $\sqrt{d}$. Equating rational and irrational parts in $A\sqrt{d}+B_1=\sqrt{d}(C\sqrt{d}+D)$ gives $A=D,B_1=dC$. ConsequentlyThe eigenvalue of $M$ on $({\theta }_1,1{)}^T$ is its denominator $M_{21}{\theta }_1+M_{22}>1$; this uses $a_i\ge 1$ and ${\theta }_1>1$, including the one-term period. The corresponding eigenvalue of $N$ is $A+C\sqrt{d}>1$. If the algebraic norm is $-1$, square this unit; otherwise keep it. In either case there is a unit $u=X+Y\sqrt{d}>1$ of algebraic norm $1$ with integer $X,Y$. Its powers have integer coefficients and algebraic norm $1$, and are distinct since $u^j$ strictly increases. Hence Pell's equation has infinitely many integer solutions.

The continued fraction convergents of $\sqrt{67}$ begin $8,41/5,90/11,131/16,221/27$. The last one yieldsChanging either sign gives another valid integer solution.

A many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ with $x\in A⟺f(x)\in B$. If $B$ is recursively enumerable, compute $f(x)$ and run a semidecision procedure for $B$ on that value. It halts exactly when $x\in A$, so $A$ is recursively enumerable. Totality of $f$ is essential to this argument.

The S-m-n theorem says that parameters can be compiled effectively into program indices: for a standard effective numbering, there is a total computable function $s_m^n$ with ${\phi }_{s_m^n(e,\mathbf{a})}(\mathbf{x})={\phi }_e(\mathbf{a},\mathbf{x})$ for partial computable functions of $m+n$ arguments.

Write $K=\{e:{\phi }_e(e)\text{ halts}\}$, a recursively enumerable halting problem. If $X$ is recursively enumerable, make a program with parameter $x$ which ignores its input and runs a semidecision procedure for $x\in X$, halting when that procedure halts. By the S-m-n theorem its index $f(x)$ is total computable and $f(x)\in K⟺x\in X$. Conversely, $X{\le }_{m}K$ implies that $X$ is recursively enumerable by the previous construction. Thus $\boxed{X\text{ is r.e.}⟺X{\le }_{m}K}$.

Use uniform finite-stage enumerations $W_{n,s}$ and $K_s$. Define a uniformly recursively enumerable setThe S-m-n theorem supplies a total computable index function $f$ with $W_{f(n)}=V_n$. If $W_n$ is finite of size $h$, then $V_n\subseteq \{0,\dots ,h-1\}$, so $V_n$ is recursive. If $W_n$ is infinite, then for every $x\in K$ a sufficiently late stage has both $x\in K_s$ and $|W_{n,s}|>x$, while no $x\notin K$ is ever enumerated. Hence $V_n=K$, which is not recursive. Therefore $\boxed{n\in P⟺f(n)\in Q,P{\le }_{m}Q}$. As usual the effective numbering indexes all programs; if malformed codes are included, send them to a fixed index of $K$.

A fraction $1-k$ of adults survives each time step; $k$ is the adult mortality fraction. Adults produce $\mu a_n$ larvae, which mature one step later with recruitment reduced by adult-dependent competition through $1/(1+a_n)$. Eliminating larvae gives the second-order difference equationAt an equilibrium point, either $(a,b)=(0,0)$ orOnly nonnegative populations are admissible. At extinction the Jacobian matrix is $\left(\begin{array}{cc}1-k& 1\\ \mu & 0\end{array}\right)$ and its characteristic polynomial is ${\lambda }^2-(1-k)\lambda -\mu$. Its positive root exceeds $1$ exactly when $\mu >k$. For $0<\mu <k$ both roots have modulus less than $1$; at $\mu =k$ the roots are $1,-k$, so linearization is marginal. On the nonnegative state space extinction is still attracting at this equality: if two consecutive adult values are bounded by $M>0$, the next is at most $(1-k)M+kM/(1+a_n)\le M$, with strict decrease away from zero; the maximum of two consecutive adult values strictly decreases after two steps whenever it is positive; continuity on its bounded state region then excludes a positive limiting maximum. Thus the extinction equilibrium point is unstable exactly when the positive equilibrium point exists, with equality understood through nonlinear rather than strict linear stability.

At the positive equilibrium point, the trace and determinant of the Jacobian matrix are $T=1-2k+k^2/\mu$ and $-k$. The Jury stability criterion for ${\lambda }^2-T\lambda -k$ requires $1-T-k>0$, $1+T-k>0$ and $1-k>0$. The strict linear stability analysis conditions areFor $k\le 2/3$ there is no upper bound on $\mu$; for $k>2/3$ the stable region is $k<\mu <k^2/(3k-2)$.

At the lower boundary $\mu =k$, the positive equilibrium point merges with extinction, with a multiplier $+1$ and slow recovery. At the upper boundary a multiplier reaches $-1$ (the other is $k$), giving alternating adult/larval fluctuations. The nonlinear map confirms a supercritical period-doubling bifurcation, as follows. For $k>2/3$, put $h=1-k$ and ${\mu }_c=k^2/(3k-2)$. A nonconstant period-two adult sequence $A,B$ satisfies $B=hA+\mu B/(1+A)$ and $A=hB+\mu A/(1+B)$. Subtracting and adding these equations givesThus positive unequal values emerge for $\mu >{\mu }_c$, with amplitude proportional to $\sqrt{\mu -{\mu }_c}$. The two larval phases are $\mu B,\mu A$. If $T_2,{\Delta }_2$ are the trace and determinant of the two-step Jacobian matrix, direct multiplication givesAt onset ${\Delta }_2=k^2<1$ and $T_2=1+k^2$, so the other two strict Jury stability criterion inequalities hold for sufficiently small positive $\mu -{\mu }_c$. Hence just beyond the upper boundary, a stable period-two population cycle replaces the stable equilibrium. This is a local conclusion, not stability for arbitrarily large reproduction rates.

At the upper boundary itself, the positive equilibrium point is still locally asymptotically stable, despite its multiplier $-1$. To decide this equality case, apply the centre manifold theorem for a discrete dynamical system. Put $u=a-a_{\ast }$ and write the centre graph as $b-b_{\ast }=H(u)$ with $H^{\prime }(0)=-{\mu }_c$. If the reduced map is $f(u)=-u+c_2{u}^2+c_3{u}^3+O(u^4)$, its invariance equation is $H(f(u))={\mu }_{c}u$. Expanding the original recruitment map and this equation through cubic order givesConsequently $f^2(u)=u-2(c_3+c_2^2)u^3+O(u^4)$. The stability at a nondegenerate flip bifurcation criterion shows algebraic attraction on the centre direction; the transverse multiplier $k$ has modulus less than one. Including this boundary, the complete local asymptotic-stability condition for a positive population is thereforeThe shaded figure shows the strict linear-stability region; its upper boundary adds this nonhyperbolic attracting case.

Demographic stochasticity near the lower boundary can lead to absorption at extinction; near the upper boundary it excites alternating fluctuations and can blur the deterministic period-doubling bifurcation. These qualitative predictions depend on the chosen stochastic recruitment and mortality rules.

With constant masses, differentiate the moment of inertia twice:For each pair, $F_{ij}=-G{m}_i{m}_j(r_i-r_j)/|r_i-r_j{|}^3$ and $F_{ji}=-F_{ij}$. Hence its contribution is $(r_i-r_j)\cdot F_{ij}=-G{m}_i{m}_j/|r_i-r_j|=V_{ij}$. Summing over unordered pairs gives $\sum r_i\cdot F_i=V$. Time-averaging over $[0,T]$ yieldsFor a bound system with $I^{\prime }(T)=o(T)$, or a stationary equilibrium with zero average left-hand derivative, the limit is the virial theoremBounded spatial extent together with bounded velocities suffices for the derivative condition; possible gravitational collisions must be excluded or otherwise regularized.

For the initially homogeneous sphere, $V_i=-3G{M}^2/(5R_i)$ and $K_i=0$. Conservation of energy and the virial theorem imply $E_f=V_f/2=V_i$, hence $V_f=2V_i$. With the usual homologous-sphere approximation, $V\propto -1/R$, soThese are the conventional collapse estimates. A final virial equilibrium is not, by itself, guaranteed to remain homogeneous: if $V_f=-{\alpha }_{f}G{M}^2/R_f$, the actual relation is $R_f/R_i={\alpha }_f/(2{\alpha }_i)$ with ${\alpha }_i=3/5$. Thus the factor of two applies exactly to the gravitational radius, and to the outer radius only under the stated structural approximation.

Here “non-interacting” means collisionless apart from gravity. Baryonic gas can collide, convert ordered motion to thermal energy, and radiate it. If radiative cooling is effective, the fixed-energy virial state loses pressure support and contracts further. Baryonic cooling can destabilize the collisionless virial state; baryons are not inevitably unstable if cooling is slow or heating and pressure support maintain equilibrium.

Zorn lemma states that a partially ordered set in which every chain in a partially ordered set has an upper bound has a maximal element. Include the empty chain in a partially ordered set, so the hypotheses imply that the set $P$ is nonempty. Suppose there were no maximal element. Every chain in a partially ordered set $C$ has an upper bound $u$, and some $v>u$; therefore the set of elements strictly above every member of $C$ is nonempty. The axiom of choice selects one such element $f(C)$ for each chain in a partially ordered set (and an element of $P$ when $C$ is empty).

By Hartogs theorem, there is an ordinal $\kappa$ which does not inject into $P$. Transfinite recursion defines $x_{\alpha }=f(\{x_{\beta }:\beta <\alpha \})$ for all $\alpha <\kappa$: previous elements form a strictly increasing chain in a partially ordered set, including at limit ordinal stages. All $x_{\alpha }$ are distinct, giving the forbidden injection. This proves Zorn lemma; the choice of $f$ is the use of the axiom of choice.

Apply Zorn lemma to linearly independent subsets of $\mathbb{R}$ over $\mathbb{Q}$, ordered by inclusion. A union along a chain in a partially ordered set is linearly independent because each finite linear relation occurs in one member of that chain in a partially ordered set. A maximal independent set spans $\mathbb{R}$, since a vector outside its span could be adjoined. Thus $\mathbb{R}$ has a Hamel basis over $\mathbb{Q}$.

For a finite basis, the Steinitz exchange lemma proves equality of basis sizes. This also rules out an infinite basis when a finite spanning set exists: write each member of the finite spanning set using finitely many elements of another basis; their finite union spans, and independence leaves no other basis elements. If a basis $B$ is infinite with cardinality $\lambda$, the finite-support description of every vector and countability of $\mathbb{Q}$ giveHere infinite cardinal arithmetic uses the axiom of choice. Thus any infinite basis has cardinality $|V|$, proving all bases have the same cardinality. The zero space has its unique empty basis.

A graph Ramsey number $R(s,t)$ is the least $N$ such that every red-blue edge colouring of the complete graph $K_N$ has a red $K_s$ or a blue $K_t$. At a vertex in $K_{R(s-1,t)+R(s,t-1)}$, either at least $R(s-1,t)$ neighbours have red incident edges or at least $R(s,t-1)$ have blue incident edges. In the first case find a red $K_{s-1}$ and adjoin the vertex, or a blue $K_t$; the second case is symmetric. ThusStarting with $R(2,t)=t$ and $R(s,2)=s$, induction gives the binomial upper bound for a Ramsey numberFor the lower construction, partition $2t-2$ vertices into two classes of size $t-1$, colour inside-class edges red and between-class edges blue. Red cliques have at most $t-1$ vertices, and the blue graph is bipartite, so has no odd cycle.