Monthly Archives: July 2019

Formal PIE

I’ve been talking informally about the Principle of Inclusion-Exclusion but I realized it would be useful to state it more formally before proceeding to some proofs. The only problem is that a fully formal statement of PIE has a lot … Continue reading

Posted in combinatorics, pattern | Tagged , , , , , | 5 Comments

Have a piece of PIE

Commenter Stuart LoPresti gave a very nice analysis answering the questions at the end of my last post. And indeed, the punchline is that the answers are very similar to the answers to the post before that. PIE If we … Continue reading

Posted in pattern, probability | Tagged , | 6 Comments

Probabilistic PIE

Commenters Sylvain B., xpil, and Christian Luca all gave correct answers to the challenge from my previous post. If the probability that someone likes X is , then the probability they don’t like X is . Therefore the probability that … Continue reading

Posted in pattern, probability, solutions | Tagged , | 7 Comments

A probabilty puzzle

Suppose that we have surveyed a certain population of people, and have determined the following probabilities: The probability that a person likes anchovies is . The probability that a person likes to read books is . The probability that a … Continue reading

Posted in challenges, probability | Tagged , | 9 Comments

Computing the Euler totient function, part 4: totient of prime powers

I’ve been on a bit of a hiatus as I’ve been travelling with my family for the past month. So here’s a recap. Our story so far Recall that the Euler totient function, , counts how many numbers from to … Continue reading

Posted in arithmetic, computation, counting | Tagged , ,