Frobenius numbers are solutions to the coin problem. Let be coin denominations; what is the smallest sum of money that cannot be obtained using these coins? More formally, define the Frobenius number as the greatest number that is not a linear combination with . The Frobenius number exists if and only if and . A special case of Frobenius numbers involves the interestingly named McNugget numbers, and there is a well-known formula when given by sometimes known as the Chicken McNugget Theorem.
This post is mostly copied and pasted from my posts in this thread on MHF.
Problem statement: Let and let be the number of k-subsets of such that when the elements are ordered from least to greatest, the absolute difference of any two adjacent elements is less than . Find a formula or algorithm to determine for arbitrary .
Everyone knows what continued fractions are, right? Continued fractions have interesting properties and can be used to obtain best rational approximations for real numbers, among other things. Here is an example of a finite continued fraction:
This post, like the last one, is an offshoot of a thread on Math Help Forum. The situation is: Suppose there is an m×n chess-like board and we wish to fill in all the (1×1) squares according to: all squares are either black or white, and the probability that a square is black is . What is the probability that a randomly filled board will contain at least one 2×2 black square?
I came across a good programming exercise over on this thread at Math Help Forum (I’m “undefined”), and here are the results. This program reproduces the charts and expected value on this page over at The Wizard of Odds for an infinite deck. I realise the code could be cleaner, but I’m pleased with the performance of the underlying algorithms. On my laptop with modest specs, calculation takes about 20 milliseconds.