Combinatorics

Discrete Mathematics

Topics Set Theory & Boolean Algebra Logic & Proof Techniques Combinatorics & Counting Graph Theory Number Theory (Divisibility, Modular Arithmetic) Recurrence Relations Finite Automata & Formal Languages Discrete Probability

Important Theorems De Morgan’s Laws (Logic & Boolean Algebra) Pigeonhole Principle (Combinatorics) Inclusion-Exclusion Principle (Counting) Euler’s Formula for Graphs ( Handshaking Lemma ( Chinese Remainder Theorem (Number Theory) Fermat’s Little Theorem ( RSA Cryptosystem & Modular Inverses Master Theorem (Recurrence Relations)

Read more >

Peg Solitaire

Personal Motivations

I grew up as a child with this puzzle in my house. My mother could solve it, along with a couple members on her side of the family.

Mum never knew the algorithm, nor any techniques beyond "My hand just knows"; as a result I spent 4 determined days in my youth working it until I had solved it.

/projects/csp/peg-solitaire/
coffee-pegs.jpg
the one on my own coffee table

During these 4 days, I learned a heuristic: to consider the L shape `___|` and realise that for every such set, you can perform legal operations until you are left with a single marble. Then, since there are 32 marbles, you can do this 8 times until you have 4 remaining, and finally perform this "L-trick" one last time til a single peg remains in the middle of the board.

Read more >