What you’re looking for is always found in the last place you look

I wanted to challenge myself to come up with a proof for the common saying that you always find what you’re looking for in the last place you look. Or you could claim I was bored, but you’ll need a proof for that.

Proposition

For a given search method for a searchable item, that item will always be found in the last search.

Definitions

Search
A look in a single place.
Searchable Item
An item that can be found within the limitations of the searcher.
Search Method
A sequence of searches. Every search method is consistent; that is, given a search item and method, the search method consists of the same sequence of searches each time it is invoked.

Assumptions

  1. A search item cannot be found in less than 1 search.
  2. The search does not end prematurely; that is, the item will always be found.
  3. The search method is capable of finding the item.
  4. The search method is efficient; that is, once the item is found, no further searches are conducted.

Proof

Claim

An item cannot be found in less than s searches using a given search method.

Proof of Claim

Proof by induction

Let s be the number of searches.

Base Case

Let s = 1.

By assumption 1, an item cannot be found in less than 1 search, so the base case holds.

Inductive Case

Assume a sequence s = k searches are in a search method. Since the search method is efficient, if the item were found in k – 1 searches, the kth search would not occur. Therefore, the item cannot be found in k – 1 searches of the search method. Recurse.

By induction, the item cannot be found in less than s searches using a given search method.

Let n be the number of searches in the given search method for the given item.

By the claim, the item cannot be found in n – 1 searches. Therefore, the item must be found on the nth search, which is the last search.

Q.E.D.

Advertisements

`$name' says...

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: