Блог пользователя MudoBog

An interesting task I came up with
Автор MudoBog, 10 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Positive ones, sorry! Forgot to mention

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      it didnt matter we cant use negative integers anyway

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

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

        → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

        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).

        → Ответить
»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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."

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

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

→ Ответить