Chicken McNugget Theorem

-

Problem Post #01

Given a positive integer N, determine whether you can make N by summing up some non-negative multiple of A and some non-negative multiple of B where A and are relatively prime numbers.

( একটা ধনাত্বক পূর্নসংখ্যা N দেয়া আছে । তোমাকে বলতে হবে N কে A এবং B এর গুনিতক এর যোগফল আকারে প্রকাশ করা যায় কিনা ।  অর্থাৎ N = xA + yB আকারে প্রকাশ করা যায় কিনা যেখানে x এবং y রিলেটিভ প্রাইম সংখ্যা । )

Solutions: The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers A, B, the greatest integer that cannot be written in the form xA + yB for nonnegative integers x, y is 
AB - A - B.

( এই থিওরি মতে যেকোন দুইটা রিলেটিভ পজিটিভ প্রাইম সংখ্যা A এবং B এর জন্য সবচেয়ে বড় যে সংখ্যাটা xA + yB  ফর্ম এ লেখা যাবে না সেটা হলো A*B - A - B অর্থাৎ A*B - A - B  এর থেকে বড় সকল সংখ্যা  xA + yB আকারে প্রকাশ করা যাবে )

A consequence of the theorem is that there are exactly
 positive integers which cannot be expressed in the form xA + yB.

Comments

Post a Comment

Popular posts from this blog

URI 2994 Solution

-
URI 2994 - How much earn a Doctor?  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 SELECT d . name , ROUND (t . salary, 1 ) FROM doctors as d INNER JOIN ( SELECT id_doctor, SUM( (hours * 150 ) + ((hours* 150.0 * w . bonus) / 100.0 ) ) AS salary FROM work_shifts AS w INNER JOIN attendances AS a ON w . id = a . id_work_shift GROUP BY id_doctor ) AS t ON t . id_doctor = d . id ORDER BY t . salary desc ;
Read more

URI 2996 Solution

-
 URI 2996 - Package Delivery 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 SELECT year , sender, receiver FROM packages AS p INNER JOIN ( SELECT id_package, name AS sender FROM packages INNER JOIN users ON id_user_sender = id WHERE address <> 'Taiwan' ) AS sub1 ON sub1 . id_package = p . id_package INNER JOIN ( SELECT id_package, name AS receiver from packages INNER JOIN users ON id_user_receiver = id WHERE address <> 'Taiwan' ) AS sub2 ON sub2 . id_package = p . id_package WHERE color = 'blue' OR year = 2015 ORDER BY year DESC , sender DESC ;
Read more