AoPSWiki
Art of Problem Solving holds many free classes called Math Jams.
Click here for transcripts to past Math Jams.

Brute forcing

From AoPSWiki

Revision as of 19:53, 24 January 2009 by Bugi (Talk | contribs)
(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Brute forcing is generally accepted as the term for solving a problem in a roundabout, time-consuming, uncreative, and inconvenient method.


Given the problem "How many outfits can you create with thirteen hats and seven pairs of shoes?", a method involving brute force would be to list all 91 possibilities.

Another method of brute force is the Greedy Algorithm. As an example, given two sets \{{a}_1,{a}_2,\ldots,{a}_n\} and \{b_1,b_2,\ldots,b_n\} how can we maximize the sum of \sum_{i,j \in n} a_ib_j? We sort the sets such that they are in increasing or decreasing order; then, the maximal sum is a_1b_1 + a_2b_2 + a_3b_3 + \ldots a_nb_n. The "greedy" part is when we maximize the sum each step by taking the largest possible term to add.

See the Rearrangement Inequality for consequences of the example (and a more formal proof).

See also

Stay informed about new Art of Problem Solving developments.
Click here to join our mailing lists.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • FoundationPrivacyContact Us