Combinatorics Post # 1: Double Counting

by niyu, Jul 1, 2017, 5:52 AM

In this post, I'll be talking about double counting. This is mainly to set the stage for future combinatorics posts, in which this fundamental technique will be used extensively.

Heuristics: Double Counting is probably the most fundamental concept in combinatorics. The main idea of double counting is to count some quantity in two different ways. Often, the main difficulty of a double counting problem is the figuring out the specific quantity to double count. In this post, I'll be showing several problems that highlight this technique.

Let's begin!

The following problem is a very basic double counting problem, but it highlights the kinds of things that come up in this technique well.

Problem 1:
Solution

Our next problem is from combinatorial geometry.

Problem 2: IMO 1989/3
Solution

The following $4$ problems are more challenging examples of this technique.

Problem 3: IMO 1998/2
Solution

Problem 4: Iran Olympiad
Solution

Problem 5: Russia 1999
Solution

Problem 6: USAMO 2011/6
Solution

To conclude, we present a problem from the USA TST.

Problem 7: USA December TST 2014/3
Solution: "Use Obvious Inequalities" - Gabriel Dospinescu
This post has been edited 7 times. Last edited by niyu, Jul 9, 2017, 7:02 PM

Comment

5 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Nice post and nice problems :)

by Ankoganit, Jul 12, 2017, 2:57 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
@Ankoganit Thanks :D
This post has been edited 1 time. Last edited by niyu, Jul 31, 2017, 11:14 PM

by niyu, Jul 13, 2017, 1:08 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
you're a god

by wu2481632, Jul 27, 2017, 6:45 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
@wu2481632 Thanks :D

by niyu, Jul 27, 2017, 11:01 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
woah cool

by Mattthebat2569, Dec 13, 2022, 1:03 PM

Shouts
Submit
  • POST MOAR ABOUT COMBINATORICS PLZ

    by Tem8, Aug 5, 2024, 10:29 AM

  • hello so good

    by Mattthebat2569, Dec 13, 2022, 1:03 PM

  • i think you should post here more

    by Welp..., Oct 12, 2020, 4:01 AM

  • howrusogood

    by fukano_2, Sep 29, 2020, 11:21 PM

  • hi :surf:

    by Kanep, Sep 19, 2020, 8:55 PM

  • /bump $\quad$

    by budu, Jul 3, 2020, 6:12 AM

  • graph theory is cute :love:

    by Welp..., Jul 4, 2019, 6:19 PM

  • Great problem, it helped me on a mathcounts problem. Thanks

    by Team_Penguiners, May 1, 2019, 1:14 AM

  • Thank you! :)

    by niyu, Nov 30, 2018, 5:01 AM

  • the functional equation one is awesome :love:

    by targo___, Nov 30, 2018, 3:56 AM

  • wow reacts only

    by Welp..., Aug 19, 2018, 5:10 PM

  • @yayups no u

    by niyu, Aug 19, 2018, 12:06 AM

  • with the power of DUE HOANG :love: :love: :love: :love: :love:

    by Welp..., Aug 18, 2018, 3:28 AM

  • How do you get so good

    by yayups, Aug 16, 2018, 7:32 PM

  • revive yet again

    by Welp..., Aug 15, 2018, 4:40 AM

50 shouts
About Owner
  • Posts: 830
  • Joined: Nov 16, 2015
Blog Stats
  • Blog created: Jul 1, 2017
  • Total entries: 41
  • Total visits: 8062
  • Total comments: 40
Search Blog
a