Lecture Notes: Casework Counting & Sum of Cubes

Introduction to Counting Problems

• Multiple Paths: Often more than one way to solve counting problems.
• Objective: Count the number of ways to get from point A to point B.
• Challenges: Counting paths manually can lead to repeating counts or missing paths.

Simplifying the Problem

• Focus on Subsections: Make the problem simpler by breaking it down.
• Example Breakdown:
  • From A to X: 3 ways.
  • From X to B: 2 ways.
  • Total through X: 3 x 2 = 6 ways.
• Repeat for Y and Z:
  • Y: 1 way from A, 4 ways to B (1 x 4 = 4 ways).
  • Z: 2 ways from A, 5 ways to B (2 x 5 = 10 ways).
• Total Paths: Add paths through X, Y, Z.
• Verification: Ensure all paths are counted, none are double-counted.

Casework Counting Strategy

• Definition: List cases, ensure no overlap, and ensure coverage.
• Application: Each path from A to B goes through exactly one of X, Y, Z.
• No Overlap: Paths do not go through more than one intermediary.

Real-World Application: Hardy and Ramanujan Story

• Historical Context: Ramanujan's mathematical prowess and collaboration with Hardy.
• Famous Incident: Hardy's taxi number (1729) perceived as boring.
• Ramanujan's Insight: Smallest number expressible as the sum of two cubes in two different ways.

Counting Numbers Sum of Cubes

• Problem Setup: Count numbers <1000 expressible as sum of two positive cubes.
• Initial Attempts: Listing each manually proved inefficient.
• Organized Approach:
  • Limit cubes by observing max cube value.
  • Systematically determine valid combinations.
• Elimination: Only consider cubes <= 9.

Detailed Step-by-Step Process

• Begin with Largest: Start with largest cube (9 cubed), work down.
• Calculate Combinations:
  • 9 cubed: Combine with cubes < 271.
  • 8 cubed: Combine with smaller cubes, excluding duplicates.
  • Continue Down: Repeat for each decreasing cube.
• Avoid Overlap: Define cases by largest cube and avoid reusing combinations.

Verifying Results

• Complete Coverage: Each possible sum is in one case.
• No Duplicates: Ramanujan's insight ensures uniqueness below 1729.
• Total Count: 41 numbers <1000 can be expressed as the sum of two positive cubes.

Conclusion

• Casework Counting: Clearly define cases, ensure coverage, avoid overlap.
• Real-World Relevance: Effective method for structured problem-solving in combinatorics.