MudoBog's blog

An interesting task I came up with
By MudoBog, 10 years ago, In English

Hi guys! Today I wanted to share a task I came up with, while doing a test in Discrete mathematics. The statement is simple: You are given a positive integer N. Your task is to find the number of partitions of a number 2*N in exactly 3 positive integers, such that if you take any two of those, their sum is greater than the remaining integer. Notice that the partition of a number 2N in exactly 3 integers is a set of three integers a, b and c such that: a+b+c = 2N , and the order of these integers is not important. I want to see how tough the problem is. I guess some people will easily solve it, however I wanted to hear about ideas on solving it. At the end, I will post a solution if no one who reads this post solves it. Thanks!

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Integers or Positive Integers? upd: sorry i was foolish because it is obvious that we cannot use negative integers

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Positive ones, sorry! Forgot to mention

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it didnt matter we cant use negative integers anyway

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      1 <= x[0] < N (because if it is higher than N then x[0] >= 2N — x[0])
      1 <= x[1] < N (same)
      1 <= x[2] < N (same again)
      x[0] + x[1] + x[2] = 2N -> C(2N-1,3-1 = 2) ways to do this
      we have to reduce the number of ways which either x[0] is more than N or x[1] or x[2] ...
      -> N <= x[i] < 2N-1 (x[i] cant be higher than 2N-1 because then x[a[i][1]] or x[a[i][2]] will be zero then it is ok this is the only thing we have to exclude) -> x[0] + x[1] + x[2] = N+1 (substracting N-1 from it since we will give N-1 to x[i] at the end) -> C(N,3-1 = 2) * 3(i = 0,1,2) -> Final answer = C(2n-1,2) — 3 * C(N,2) a bit more or less

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Correct! Although I used a completely different approach. Nice idea though!

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +13 Vote: I do not like it

        I think you forgot that the order of a, b, c is not important. Therefore you counted most of partitions multiple times (6 times if a, b, c are all different, three times in case that two of them are equal and once if they are all equal).

        → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Is partition of 2N a set, or a multiset (i.e. is it possible that a = b)?

Also, there is a shorter way to state the problem:

"What is the number of different triangles with a given perimeter 2N such that all their edges have integer lengths? Two triangles are considered different if they are not congruent."

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Assuming that numbers may not be distinct, let k=(2*N) so, if(k%3==0):
answer : k/3,k/3,k/3
if(k%3==1):
answer : (k-1)/3,(k-1)/3,(k-1)/3 + 1
if(k%3==2):
answer : (k-2)/3,(k-2)/3 + 1,(k-2)/3 + 1
exceptional cases : k=2(i.e N=1),k=4(i.e N=2)

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +13 Vote: I do not like it

We can use use Reyna 's approach to count number of different triplets (where the order is important) (a, b, c). We counted most of partitions (where the order isn't important) {a, b, c} 3! = 6 times. However, there are different partitions where two elements are equal, so we counted them only three times (or only once if all elements are equal). If 3|N, there is one partition that was counted only once, because all its elements are equal.

So the final number should be

→ Reply