Back to Algorithmic Arguments for Tacos

Proofs and Theorems for Optimal Taco Consumption

The Fundamental Theorem of Taco Consumption

Let G be a graph with vertices representing tacos, edges representing toppings, and vertices representing consumers. Then for any given consumer, the number of tacos they can consume, denoted by |C|, is maximized when the graph G is a tree.

		Algorithm 1: TACO-MAX
		for i = 1 to |E|
			if edge i is a leaf node
				add edge i to the MST
			endif
		endfor
		return MST
	

The Pigeonhole Theorem of Taco Variety

For any given set of tacos, T, and any set of toppings, P, if |T| < |P| then there exists a taco in T that has at least two toppings in P that are not present in any other taco in T.

		Algorithm 2: TACO-VARIETY
		for each taco t in T
			for each topping p in P
				if t contains p and p is not in any other taco in T
					print "Taco " t " has unique topping " p
				endif
			endfor
		endfor
	

The Traveling SalesTaco Theorem

Given a set of tacos, T, and a set of toppings, P, and a set of salesmen, S, there exists a salesman who can sell all tacos in T with all toppings in P, if and only if the graph G is a Hamiltonian circuit.

		Algorithm 3: SALES-TACO
		for each salesman s in S
			if s can sell all tacos in T with all toppings in P
				print "Man, " s " can sell all tacos!"
			endif
		endfor
	

More Proofs and Theorems Back to Algorithmic Arguments for Tacos