DiegoAE's blog

Dhaka Regional 2008 — Math problems
By DiegoAE, 12 years ago, In English

Greetings,

I have found a couple of very interesting math problems on the Dhaka 2008 problemset:

  1. Puzzles of Triangles

  2. Stopping Doom's Day

The first one is about counting in how many ways you can put a right triangle over a square taking into account some constraints(I know it has to do with prime factorization). The second one is about computing the following function modulus 10007:

and n ≤  = 2 * 109

I would find very useful any hint/comment that you can give me about these problems.

Thanks in advance.

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

»
12 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Hint for the second problem: There exists an exact polynomial to calculate T(n). However, the method to discover it would be heavily related to math. Instead, by knowing it would be a degree 10 polynomial, we can use Newton's Divided Difference Method. One more thing to note is that T(n) = T(n % 10007), so we only need the first 10007 values of T.

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

    Thanks for replying flashmt. Your hint was very helpful, now I see how to solve the problem but I find very difficult to come up with an idea like that for solving a problem.

    → Reply