Bring discrete mathematics together.

(a)

One predicate is ((3y<kn) or (3y=kn)) and kn<3y+3. The image formula is ∃n [((3y<kn) or (3y=kn)) and kn<3y+3]. It is equivalent to 3y≤kn<3(y+1). Since k>0, the integer preimages are exactly ceil(3y/k)≤n≤ceil(3(y+1)/k)−1. An interval with lower endpoint greater than its upper endpoint gives no preimage. The upper bound uses a ceiling minus one because the original upper inequality is strict, including when its endpoint is integral.

• 1 point: Gives both the permitted-symbol predicate and its existential image formula with the correct strict upper bound.
• 1 point: Derives both integer preimage bounds correctly, including an integral upper endpoint and empty intervals.

(b)

Write any n uniquely as n=3q+r with q∈Z and r∈{0,1,2}. Then F_5(n)=5q+floor(5r/3), giving 5q,5q+1,5q+3 respectively. Thus the image is exactly the residue classes 0,1,3 modulo 5. Each output has one preimage: 5q↦3q, 5q+1↦3q+1, 5q+3↦3q+2. The three residue classes are disjoint and each displayed n produces its output, proving both exhaustiveness and uniqueness. Since −2=5(−1)+3, its preimage is −1. The value −1 has residue 4 modulo 5 and is absent.

• 1 point: Derives all three output cases from division with remainder valid on Z.
• 1 point: Proves the exact image and the unique preimage formulas in both directions.
• 1 point: Computes the negative examples correctly rather than using truncation toward zero.

(c)

For k=1 or 2, 0 and 1 have the same output 0, so the map is not injective. For any y, choose n=ceil(3y/k). Then kn≥3y and kn<3y+k≤3y+2<3y+3, proving surjectivity for k=1,2. For k=3 the map is the identity and is bijective. For k≥4, if n increases by at least one, kn/3 increases by more than one, so its floor increases by at least one; hence the map is injective. It is not onto: among n=0,1,2,3 the three consecutive output increments are positive integers summing to F_k(3)−F_k(0)=k≥4, so one increment is at least two. An integer strictly between those consecutive outputs is missed globally because the map is strictly increasing. Therefore injectivity holds exactly for k≥3, surjectivity exactly for k≤3, and bijectivity only for k=3.

• 1 point: Proves noninjectivity and surjectivity for both k=1 and k=2.
• 1 point: Handles k=3 and proves strict increase for all k≥4.
• 1 point: Proves a genuinely omitted value for every k≥4 and states the full classification.

Targeted review:

• Quantified arithmetic specifications
• Injectivity and surjectivity
• Integer division with remainder

(a)

The representations are 54=7·2+10·4, 55=7·5+10·2, 56=7·8+10·0, 57=7·1+10·5, 58=7·4+10·3, 59=7·7+10·1, 60=7·0+10·6. These are seven consecutive base values. For any n≥61, n−7≥54; therefore a strong-induction hypothesis covering all smaller totals down to 54 applies to n−7 without falling below the proved range.

• 2 points: Gives all seven correct nonnegative representations; award one of these two points if exactly one representation is missing or incorrect.
• 1 point: Explains why seven consecutive bases cover the subtraction step and checks its first eligible input.

(b)

Assume all integers from 54 through n−1 are feasible, with n≥61. The smaller value n−7 has representation 7a+10b by the hypothesis, so n=7(a+1)+10b with nonnegative coefficients. Together with the base block this proves the claim. Constructively, repeatedly subtract 7 while the current total exceeds 60. Each such step leaves a value at least 54 and strictly decreases it, so eventually the value lies in 54,…,60. Use its listed representation and add the number of subtractions to the coefficient of 7. From 103, seven subtractions reach 54, giving a=2+7=9,b=4 and 103=63+40.

• 1 point: States a valid strong-induction hypothesis and proves the step with nonnegative coefficients.
• 1 point: Defines a terminating construction and proves it remains in the allowed domain.
• 1 point: Produces and checks the requested representation of 103.

(c)

If 53=7a+10b with a,b≥0, reduction modulo 7 gives 3b≡4, hence b≡6 modulo 7 (multiply by 5). Nonnegativity implies b≥6 and thus 10b≥60>53, a contradiction. The proof above covers all n≥54. Any proposed N≤53 would include the infeasible value 53 among its required totals, so 54 is the smallest threshold.

• 1 point: Derives the residue restriction on b and the nonnegativity contradiction.
• 1 point: Combines the obstruction with the induction to justify minimality of the threshold.

Targeted review:

• Strong induction and base ranges
• Integer domains and division

(a)

If the root is c/d in lowest terms with c,d positive, then bc^r=ad^r. For a prime p write α=v_p(a),β=v_p(b),γ=v_p(c),δ=v_p(d). Equality gives β+rγ=α+rδ. Since a,b are coprime, at most one of α,β is positive. The equation implies α−β is divisible by r, so every positive exponent in either a or b is divisible by r. Coprimality of c,d also shows exactly how numerator and denominator arise: if α>0, then β=0 and γ>δ, forcing δ=0, so α=rγ; similarly β>0 forces γ=0 and β=rδ. Primes absent from both a,b satisfy γ=δ and hence both zero. Conversely, divide each exponent of a and b by r to build positive integers c and d. Then c^r=a,d^r=b, so c/d is the positive root. This also handles a=1 or b=1, whose prime exponent lists are empty.

• 1 point: Writes the reduced rational root and correct integer equation including the denominator.
• 1 point: Uses prime exponents and coprimality to prove the divisibility requirement on both numerator and denominator.
• 1 point: Explains why cancellation or primes absent from a,b do not create an exception.
• 1 point: Constructs the rational root in the converse and handles exponent-zero/unit boundaries.

(b)

The displayed fractions are reduced because their numerator primes differ from 5. Every exponent for U is divisible by 6, so its positive sixth root is 2²·3³/5=108/5. For V, suppose the root is c/d in lowest terms. Then 5^6c^6=2^12·3^17d^6. Taking the exponent of 3 gives 6v_3(c)=17+6v_3(d), impossible modulo 6. Thus the sixth root of V is irrational. The denominator exponent 6 is compatible with a rational root but cannot repair the numerator exponent 17. Positivity selects the stated positive root.

• 1 point: Checks reduction and applies the exponent criterion to U.
• 1 point: Computes the exact positive value 108/5.
• 1 point: Derives the explicit exponent equation for V from a rational-root assumption.
• 1 point: Uses its modular contradiction and explains why denominator cancellation cannot rescue it.

Targeted review:

• Prime factorization and divisibility
• Contradiction and rationality

(a)

The integer formed by taking each prime’s minimum exponent divides every a_i. Every common divisor has exponent at most each v_p(a_i), hence at most the minimum, and therefore divides this constructed integer. It is the gcd. Taking maximum exponents gives a common multiple dividing every common multiple, hence the lcm. Only finitely many primes appear in the finite family, so the constructed products are finite. For two inputs, min(α,β)+max(α,β)=α+β at every prime. The product gcd(a,b)lcm(a,b) and ab thus have identical prime exponents and are equal by uniqueness.

• 1 point: Proves the minimum construction is the gcd using both divisibility claims.
• 1 point: Proves the maximum construction is the lcm and notes the finite products.
• 1 point: Derives the product identity prime by prime.

(b)

Take x=y=2. Neither is divisible by 4, so w(2)=0, while xy=4 gives w(4)=1. The product combines two factors of 2 into one factor of 4. In fact w(n)=floor(v_2(n)/2), and floors of half-exponents need not add. Prime exponents add because prime factorization counts individual prime factors; a composite block can be assembled across the two multiplicands.

• 1 point: Supplies and verifies an explicit failed additive identity.
• 1 point: Explains the composite-factor mechanism, for example using floor(v_2(n)/2).

(c)

A necessary compatibility condition is that gcd(18,30)=6 divide the residue difference 14−8=6, which holds. Write z=14+18t. The second condition gives 18t≡−6≡24 modulo 30, equivalent to 3t≡4 modulo 5 after division by 6. Since 3 has inverse 2 modulo 5, t≡3 modulo 5. Thus z=68+90k for every integer k. Substitution verifies both original congruences. Conversely each solution had the displayed t and must satisfy that reduced congruence, so no others exist. The period is lcm(18,30)=18·30/6=90; the difference of any two solutions is divisible by both moduli and hence by 90.

• 1 point: Uses the gcd compatibility check and correctly reduces the equation for t.
• 1 point: Finds the full integer family and verifies both congruences.
• 1 point: Proves completeness and connects the period to the lcm without invoking a coprime hypothesis falsely.

Targeted review:

• Prime exponent reasoning
• Congruences and compatibility

(a)

The domains are D(E)∩D(F) and {x in D(E)∩D(F): F(x)≠0}, respectively. Constants and the variable return rational values at rational inputs. For an Add node, the induction hypotheses give two rational defined child values, whose sum is rational. For a Div node, they give rational child values with a nonzero denominator by the domain rule, so the quotient is rational. These are every constructor of a finite expression.

• 1 point: Gives both domain formulas, including the nonzero defined denominator condition.
• 1 point: Covers both leaves and both recursive constructors in a rational-value structural induction.

(b)

Fix F and x in D(F), and put y=F(x). Induct on E. For Const(c), both substituted and original-at-y expressions are defined with value c. For Var, the substituted expression is F and the original-at-y value is y, so both are defined and agree. For Add(U,V), each child is defined at x after substitution exactly when its original is defined at y, by the induction hypotheses; when defined, the corresponding child values agree. Hence the conjunction of child-definedness and their sum agree. For Div(U,V), the same equivalence holds for both children, and equality of the denominator values makes the nonzero-denominator conditions equivalent; their quotients then agree. The induction covers every finite E. Composition also explicitly requires x in D(F), giving the stated intersection formula. It cannot be removed: take E=Const(7) and F=Div(Const(1),Var). Then E[F]=Const(7) has domain all rational numbers, while E∘F has domain all nonzero rational numbers.

• 1 point: States a strengthened definedness-and-value induction and handles constant and variable leaves with x in D(F).
• 1 point: Proves both directions for Add using both child hypotheses.
• 1 point: Handles both child domains and the denominator nonzero test for Div, then deduces the domain intersection.
• 1 point: Supplies a genuine constant-expression counterexample with the two different domains.

(c)

F requires x≠2. E requires t≠1, so F(x)≠1 further requires x≠3. On the resulting domain Q without {2,3}, E(F(x))=1. The constant expression 1 alone is defined at x=3, but the original outer denominator is zero there. At x=2 the inner function is undefined. Cancellation preserves values on the original domain but does not fill either excluded input.

• 1 point: Derives both exclusions x=2 and x=3 from the nested original domains.
• 1 point: Gives the constant value 1 on that domain and explains an invalid extension at x=3 or x=2.

Targeted review:

• Strengthened structural induction
• Composition and intermediate domains

(a)

Initially 0≤6≤11, 0≤8≤13, the total is 14, and x≡0, y≡2 modulo 3. In a transfer from x to y the source guard ensures x−3≥0 and the destination guard ensures y+3≤13; the other two bounds are preserved since x decreases and y increases. The reverse transfer has the symmetric argument. Each move changes the total by zero and each coordinate by a multiple of 3. Thus induction proves all claims, including y≡2 modulo 3.

• 1 point: Checks every invariant at the initial state.
• 1 point: Uses the source and destination guards to preserve all capacity bounds in both directions.
• 1 point: Proves conservation and both congruences under either move and concludes induction.

(b)

Conservation and bounds require 1≤x≤11: y=14−x must lie between 0 and 13. The congruence leaves x=3,6,9, giving (3,11),(6,8),(9,5). Both outer states are reached from (6,8) by one legal move, so all three are reachable; the necessary invariant excludes every other candidate. The state (7,7) satisfies the bounds and total but has x not divisible by 3, so it is unreachable. Any similarly justified counterexample is acceptable.

• 1 point: Uses all invariant restrictions to obtain exactly the three candidates.
• 1 point: Provides legal paths realizing each candidate, establishing sufficiency for this specific list.
• 1 point: Gives and justifies a bound-safe, total-preserving but unreachable state.

(c)

No forced termination holds: (6,8)→(3,11)→(6,8) can repeat forever, and every move is guarded. There is no reachable terminal state: (3,11) can move to (6,8), (9,5) can move to (6,8), and (6,8) has both moves. The operator can still choose to stop at any of these states; voluntary stopping is not disabledness of all transitions.

• 1 point: Gives an explicit infinite legal cycle, rather than inferring termination from a finite state space.
• 1 point: Checks the reachable states for enabled moves and distinguishes voluntary stopping from terminality.

Targeted review:

• Guarded state invariants
• Safety and termination

(a)

The three chains {A,D,F}, {B,E,G}, {C} partition the vertices. An antichain uses at most one member of each, so its size is at most 3. There is no precedence across these three chains, so choosing C, one vertex from the first chain, and one from the second always gives size 3. The nine maximum antichains are {A,B,C},{A,C,E},{A,C,G},{B,C,D},{C,D,E},{C,D,G},{B,C,F},{C,E,F},{C,F,G}. To have size 3, every antichain must select one member of each partition chain, so this list is exhaustive.

• 1 point: Proves the upper bound 3 using a chain partition and transitive comparability.
• 1 point: Shows that one choice from each chain is an antichain of size 3.
• 1 point: Lists all nine distinct maximum antichains without an invalid set.
• 1 point: Explains why every maximum antichain has this form, certifying completeness.

(b)

One schedule is worker 1: A on [0,1], D on [1,2], F on [2,3], C on [3,4]; worker 2: B on [0,1], E on [1,2], G on [2,3], then idle. All four precedence constraints and the same-time finish/start rule are satisfied. A length-three chain forces completion time at least 3. Seven units of work on two workers force time at least 7/2. More strongly, each worker executes an integer number of whole unit jobs, so one must execute at least 4 jobs and needs at least 4 elapsed time units, even if arbitrary real start times are allowed. The displayed schedule attains 4. Width 3 describes mutually incomparable jobs, not their complete resource-constrained timing; it does not replace either lower-bound argument.

• 1 point: Supplies a complete schedule finishing at 4 with no overlap on a worker.
• 1 point: Checks every precedence edge and states the length-three-chain bound.
• 1 point: Proves the four-unit work-allocation lower bound, valid even with real start times.
• 1 point: Combines the lower bound and attaining schedule and distinguishes width from makespan.

Targeted review:

• Precedence and limited resources
• Comparability in partial orders

(a)

The proposal sequence is A→X, B→X, B→Z, C→Y, D→Z, B→Y, C→X, A→Y, A→Z, D→Y, D→X. The final pairs are A–Z, B–Y, C–X, with D unmatched. A prefers X and Y to Z, but X prefers C to A and Y prefers B to A. B prefers X and Z to Y, but X prefers C to B and Z prefers A to B. C prefers Y to X, but Y prefers B to C. D prefers every receiver to being unmatched, but X prefers C to D, Y prefers B to D and Z prefers A to D. These exhaust possible blocking pairs.

• 1 point: Gives the ordered proposal trace with the correct replacements and rejections.
• 1 point: Identifies all three final pairs and unmatched D.
• 1 point: Checks every proposer-preferred alternative, including all three alternatives for D, against the receiver ranking.

(b)

Each proposer advances through its list without repetition, so there are at most 4·3=12 proposals. A receiver that has ever received a proposal always holds someone thereafter, and replaces that person only with someone it prefers. At termination at least one proposer is free because at most three can be held. That free proposer has exhausted all three receivers; consequently every receiver has received a proposal and remains occupied. For a putative blocking pair p,r, proposer p must have proposed to r: a free proposer exhausted its list, and a matched proposer previously proposed to every receiver it prefers to its final partner. When r rejected or displaced p, it held someone it preferred to p; its subsequent held partners only improve. Its final partner is therefore preferred to p, contradicting blocking. This proves stability for every eligible-proposer schedule.

• 1 point: Proves the no-repeat finite proposal bound.
• 1 point: Uses an exhausted free proposer and persistent receiver occupancy to prove all receivers are filled.
• 1 point: Proves stability using prior proposals and monotone receiver improvement for both matched and unmatched proposers.

(c)

Let the only mutually acceptable pairs be A–X and B–Y; C and D list nobody, Z lists nobody, and the other four lists contain only their respective one partner. A–X and B–Y form a stable matching with C,D,Z unmatched, since there is no unpaired mutually acceptable pair. An exhausted free proposer need not have proposed to all receivers: C and D have empty lists. Thus the complete-list argument that every receiver has received a proposal fails. No-repeat termination remains valid, but universal receiver saturation does not.

• 1 point: Gives a concrete stable incomplete-list example with an unfilled receiver and checks acceptability/blocking.
• 1 point: Identifies the failed exhausted-list-to-all-receivers implication without falsely rejecting termination.

Targeted review:

• Unequal sides and proposal invariants

(a)

There are C(12,6)=924 displays. Let A exclude all red and B exclude all blue. Each has C(9,6)=84 displays. Their intersection consists of choosing all six neutral designs, so |A∩B|=C(6,6)=1. Inclusion–exclusion gives 924−84−84+1=757.

• 1 point: Counts the full unordered sample space as 924.
• 1 point: Identifies both exclusion counts as 84 and the intersection as the single all-neutral display.
• 1 point: Adds the intersection back and obtains 757.

(b)

Partition by exactly two or exactly three red designs. With two red, choose C(3,2) red sets and then four from the nine nonred designs, excluding choices of four neutral: 3[C(9,4)−C(6,4)]=333. With three red, choose three nonred designs with at least one blue: C(9,3)−C(6,3)=64. Total 397. Part (a) also admits exactly one red and therefore does not enforce the changed condition.

• 1 point: Uses disjoint exactly-two/exactly-three red cases.
• 1 point: Correctly excludes blue-free choices in both cases, obtaining 333 and 64.
• 1 point: Obtains 397 and identifies the exactly-one-red defect in reusing part (a).

(c)

The changed event is a subset of the original event, so the conditional probability is 397/757. The denominator 924 answers the unconditional changed-requirement question. Red and blue counts in a fixed-size selection are not justified as independent: for instance, conditioning on no red gives probability C(6,6)/C(9,6)=1/84 of no blue, whereas the unconditional probability of no blue is 84/924=1/11. Thus multiplying the marginal success probabilities has no valid independence premise.

• 1 point: Uses nesting and the conditional sample space to obtain 397/757.
• 1 point: Explains which different probability 397/924 represents.
• 1 point: Supplies a concrete dependence check or valid fixed-size-selection argument against multiplying unsupported marginals.

Targeted review:

• Return to overlapping exclusions and inclusion–exclusion

(a)

Isolation requires absence of four distinct incident edges. By edge independence its probability is (2/3)^4=16/81. Linearity gives E[X]=5·16/81=80/81, without assuming independent vertex indicators. A Bernoulli indicator has variance (16/81)(65/81)=1040/6561.

• 1 point: Counts four required absent edges and obtains 16/81.
• 1 point: Uses linearity to obtain 80/81 without claiming independent vertex events.
• 1 point: Computes indicator variance 1040/6561.

(b)

The two incident-edge sets each have size four and share exactly edge uv, so their union has seven edges. Both vertices are isolated with probability (2/3)^7=128/2187. Covariance is 128/2187−(16/81)^2=(384−256)/6561=128/6561, positive. Multiplying isolation probabilities would count the shared absent-edge requirement twice as if independent.

• 1 point: Identifies exactly seven distinct required absent edges, including the one-edge overlap.
• 1 point: Obtains joint expectation 128/2187.
• 1 point: Subtracts the product of means and obtains positive covariance 128/6561.

(c)

Var(X)=5·1040/6561+2C(5,2)·128/6561=7760/6561. The binomial variance would be only 5200/6561, incorrectly omitting covariance. Also X=4 is impossible: if four vertices are isolated, no edge can touch any of them, and the remaining vertex has no possible neighbor and is isolated too. A Binomial(5,16/81) assigns positive probability to four.

• 1 point: Includes all ten unordered covariance pairs with factor two.
• 1 point: Obtains 7760/6561 and contrasts the binomial variance.
• 1 point: Proves that exactly four isolated vertices is impossible, contradicting the proposed binomial law.

Targeted review:

• Return to indicator sums and covariance

(a)

A two-trial block fails only on two failures, so its success probability is 1−1/4=3/4. A three-trial block succeeds only on three successes, so its probability is 1/8. Functions of disjoint collections of mutually independent trials are independent: joint block events factor by summing the factored elementary outcomes within each block. The indicators are not identically distributed, so the usual binomial model does not apply. More conclusively, the mean forces a hypothetical Binomial(100,p) to have p=1/2, whose variance 25 differs from the actual variance below.

• 1 point: Derives probabilities 3/4 and 1/8 from the elementary trials.
• 1 point: Connects disjoint blocks and mutual trial independence to joint indicator independence.
• 1 point: Rejects a common-probability binomial model with a correct nonidentical-probability or moment argument.

(b)

E[Y]=60(3/4)+40(1/8)=50. Independence gives Var(Y)=60(3/4)(1/4)+40(1/8)(7/8)=125/8. Since Y is integer, 41≤Y≤59 is exactly |Y−50|<10. Chebyshev bounds its complement P(|Y−50|≥10)≤(125/8)/100=5/32. Thus the requested probability is at least 27/32. This is a rigorous bound, not an exact probability or a normal approximation.

• 1 point: Obtains mean 50 and variance 125/8 by summing the unequal Bernoulli moments.
• 1 point: Identifies the complement with deviation at least 10, including Y=40 and 60.
• 1 point: Applies Chebyshev and obtains the lower bound 27/32 with its bound interpretation.

(c)

Write Y=60U+40V, where independent U,V have success probabilities 3/4 and 1/8. The mean is still 50 by linearity. But Var(Y)=3600(3/16)+1600(7/64)=675+175=850. Indicators within each family are now identical rather than independent, so the old variance and its Chebyshev guarantee do not follow. Indeed Y can only be 0,40,60,100; none lies between 41 and 59, making the requested probability zero under this redesign.

• 1 point: Retains mean 50 and expresses the redesigned count as 60U+40V.
• 1 point: Computes variance 850 using squared coefficients and independence only between U and V.
• 1 point: Explains the lost block independence and demonstrates failure of the old interval guarantee, ideally from the four-point support.

Targeted review:

• Return to moment bounds and their hypotheses

(a)

One attempt succeeds with probability (2/3)(1/2)=1/3. Its failure probability is 2/3. Independent fresh attempts give probability (2/3)^3=8/27 of three failures and no success; hence success by the cap has probability 19/27. A failed attempt contains a blue token, but that information does not alter a newly independently shuffled full collection. This multiplication would not apply to a retained remainder.

• 1 point: Uses without-replacement conditional probability to obtain single-attempt success 1/3.
• 1 point: Obtains capped failure 8/27 and success 19/27.
• 1 point: Identifies the independent full reset that justifies multiplying attempt failure probabilities.

(b)

Attempt one is always used, attempt two is used with probability 2/3, and attempt three with probability 4/9. Summing these indicators yields expected attempts 1+2/3+4/9=19/9 and work 2·19/9=38/9. All runs, including the 8/27 capped failures, are included. An unlimited geometric process would have mean three attempts and work six, but this process stops after at most three attempts regardless of success.

• 1 point: Identifies the three attempt-use probabilities 1,2/3,4/9.
• 1 point: Obtains expected attempts 19/9 and work 38/9 without conditioning on success.
• 1 point: Distinguishes the finite-cap stopping rule from the unlimited geometric expectation.

(c)

Failure of the first pair means that pair contained the unique blue and exactly one green, so the last token is green with conditional probability one. Thus R always succeeds. It uses two inspections with probability 1/3 and three with probability 2/3, so expected work is 2(1/3)+3(2/3)=8/3. The reviewer ignores the observed composition: the remainder is not a fresh sample from the original proportions. Here R has greater success probability and lower expected work than F, but it uses a different success rule and retained information. This concrete comparison does not establish superiority of arbitrary retention policies.

• 1 point: Conditions on the failed pair and proves the remaining token is green with certainty.
• 1 point: Obtains success probability one and expected work 8/3.
• 1 point: Diagnoses the unconditional-proportion error and qualifies the comparison by the changed information and success rule.

Targeted review:

• Return to fresh restarts, finite caps and retained information