DILR guide, section 8

Routes and scores, plus two mini-types

Routes sets reward a systematic list; scoring sets reward testing the unknown at its low end, middle and high end. Both are common sources of TITA questions.

Worked set 7, easy. Attempt it in 15 minutes first.

Routes and networks

Five towns, A to E, are joined by two-way roads with these travel times in minutes: A–B 10, A–C 15, B–C 4, B–D 12, C–D 6, C–E 20, D–E 8. There are no other roads.

Questions

  1. (TITA) What is the fastest time from A to E?
  2. (TITA) If road B–C is closed, what is the fastest time from A to E?
  3. (TITA) How many routes from A to E visit no town twice?
  4. (TITA) What is the fastest time from A to E that avoids town C?
Show solution

Draw the five towns and seven roads, then list every route by its first step so none is missed.

RouteTime (minutes)
A–B–C–D–E10 + 4 + 6 + 8 = 28
A–B–C–E10 + 4 + 20 = 34
A–B–D–E10 + 12 + 8 = 30
A–B–D–C–E10 + 12 + 6 + 20 = 48
A–C–E15 + 20 = 35
A–C–D–E15 + 6 + 8 = 29
A–C–B–D–E15 + 4 + 12 + 8 = 39

Answers. (1) 28, via A–B–C–D–E. (2) 29, via A–C–D–E. (3) 7. (4) 30, via A–B–D–E.

Takeaway. Enumerate routes by first step and never skip a branch. With five or six towns, a complete list takes under two minutes and answers every question at once.

12 minutes, timed

Practice set 7: one-way routes

Six towns, P, Q, R, S, T and U, are joined by one-way roads with these travel times in minutes: P→Q 5, P→R 8, Q→R 2, Q→S 7, R→S 3, R→T 9, S→T 4, S→U 10 and T→U 3. There are no other roads.

Questions

  1. (TITA) What is the fastest time from P to U?
  2. (TITA) How many different routes lead from P to U?
  3. (TITA) If the road R→S is closed, what is the fastest time from P to U?
  4. (TITA) What is the fastest time from P to U that avoids T?
Show answers

(1) 17, via P→Q→R→S→T→U. (2) 8. (3) 19. (4) 20. Work forward one town at a time. Fastest arrival: Q 5, R 7 (via Q), S 10 (via R), T 14 (via S), U 17 (via T). Number of routes: each town’s count is the sum of the counts of the towns with roads into it, so Q 1, R 2, S 3, T 5, U 8. Without R→S: S becomes 12, T 16 and U 19. Avoiding T: U = S + 10 = 20.

Takeaway. On one-way networks, never list routes by hand; carry the best time and the route count forward town by town.

Worked set 8, medium. Attempt it in 15 minutes first.

Scores with a drop-high, drop-low rule

Five judges score each dancer out of 10, in whole numbers. The highest and the lowest scores are dropped (one of each, even if tied), and the result is the average of the middle three. Xena’s known scores are 6, 7, 8 and 9, and her fifth score, m, is unknown. Yash’s known scores are 8, 8, 9 and 10, and his fifth score, n, is unknown.

Questions

  1. What are Xena’s lowest and highest possible results?
  2. (TITA) If Xena’s result is 23/3, what is m?
  3. What are Yash’s lowest and highest possible results?
  4. Can Xena finish ahead of Yash?
Show solution

Test the unknown in three bands.

  • Xena, m ≤ 6: the middle three are 6, 7, 8, giving 7. For 6 ≤ m ≤ 9: the middle three are 7, 8 and m, giving (15 + m)/3, between 7 and 8. For m ≥ 9: the middle three are 7, 8, 9, giving 8.
  • Xena’s result 23/3 means (15 + m)/3 = 23/3, so m = 8.
  • Yash, n ≤ 8: the middle three are 8, 8, 9, giving 25/3 ≈ 8.33. For 8 ≤ n ≤ 10: the middle three are 8, 9 and n, giving (17 + n)/3, between 8.33 and 9.

Answers. (1) 7 and 8. (2) 8. (3) 25/3 (about 8.33) and 9. (4) No: Xena’s best (8) is below Yash’s worst (8.33).

Takeaway. With a sorting rule, an unknown can sit below, inside or above the known values. Test all three bands and the extremes appear on their own.

12 minutes, timed

Practice set 8: scores with a rule

Four judges score each of three singers out of 10, in whole numbers. The highest and lowest scores are dropped (one of each, even if tied) and the middle two are added. Kavya’s known scores are 6, 9 and 7, plus an unknown k. Leela’s scores are 8, 8, 5 and 10. Meher’s known scores are 7, 7 and 8, plus an unknown m.

Questions

  1. (TITA) What is Leela’s final score?
  2. What are Kavya’s lowest and highest possible final scores?
  3. Can Meher finish strictly ahead of Leela?
  4. If both unknown scores are 8, who finishes higher, Kavya or Meher?
Show answers

(1) 16: the middle two of 5, 8, 8, 10. (2) 13 and 16: if k ≤ 6 the middle two are 6 and 7; between 6 and 9 they are 7 and k; at 9 or above they are 7 and 9. (3) No: Meher’s middle two are 7 and 7 (m ≤ 7), 7 and m (7 to 8) or 7 and 8 (m ≥ 8), so her best is 15. (4) A tie at 15: Kavya gets 7 + 8 and Meher 7 + 8.

Mini-type: truth-tellers and liars

Each of A, B and C either always tells the truth or always lies. A says “B is a liar”. B says “C is a liar”. C says “A and B are both liars”. Who tells the truth?

Solution: assume C is truthful. Then A and B are liars; but A lying means B is truthful, a contradiction. So C lies, and B’s statement “C is a liar” is true: B is truthful. A’s statement “B is a liar” is then false, so A lies. Check: C’s claim that both A and B lie is false, as it should be. Answer: only B tells the truth.

The method: assume one person’s type, follow the chain, and drop the assumption the moment it contradicts itself.

Mini-type: painted cube

A 4 × 4 × 4 cube is painted on every face and cut into 64 unit cubes. With n = 4: three painted faces 8, two faces 12 × 2 = 24, one face 6 × 2² = 24, and no paint 2³ = 8. Check: 8 + 24 + 24 + 8 = 64.