Tag Info

Hot answers tagged frobenius

123

For the more visually inclined, arrange all positive integers in a 5-wide chart, as follows: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 ....

16

The largest solution you cannot obtain is: Reason: Additionally:

12

Answer: The three denominations are $65$, $72$ and $97$. How did I detect this answer? I searched the list of primitive Pythagorean triples at [link to triple list], while using the Frobenius applet available at [applet link]. Based on my search I know that the answer to the puzzle is unique; still, I would like to see a clean mathematical argument for this ...

10

None of the numbers less than 134 can be obtained with this set of stamps. All of the numbers in the range 134-143 can be obtained with a single stamp. None of the numbers between 143 and 2 * 134 can be obtained with a combination of these stamps. More generally, numbers that lie in the range between (n-1)143 and n(134) cannot be obtained. Because the stamps ...

10

I think the answer is

9

The general picture here is as follows: if you have two positive integers $m,n$ with no common factor then every integer bigger than $mn-m-n$ can be written as $am+bn$ with $a,b$ non-negative integers, but $mn-m-n$ itself can't. Proof: First, suppose $mn-m-n = am+bn$. Then $(b+1)n$ is a multiple of $m$, and therefore (since $m,n$ have no common factor) so ...

8

This problem is an instance of the Frobenius coin problem. In fact, the coin values form an arithmetic sequence, whose Frobenius number has the special form: $$g(a, a+d, \ldots, a+sd) = \left(\left\lfloor\frac{a-2}{s}\right\rfloor+1\right)a + (d-1)(a-1)-1$$ Here we have: \begin{align} g(999, 1000, 1001) &= \\ g(999, 999+1, 999+2\times 1) &= \... 7 I think it is- The following facts hold- There can be at most one 1000-coin. Otherwise we replace 2 1000-coins with (999+1001) There can be exactly one type of coin from 999 and 1001, otherwise we replace two of them with 2 1000-coins. There can be at most 500, 999-coins. Other wise we can replace 501, 999-coins with 499, 1001-coins and one 1000 coin. ... 5 with 5-cent stamps and 17-cent stamps you can find any number that ends with 4 and 9 with the equation below after 39 (considering you have at least one 5-cent and one 17-cent stamp); 5n+34\ where\ n>0 Similarly, you can find any number that ends with 2,7,1,6,3,8,0,5 after the numbers stated in the equations below: 5n+17\ where\ n\geqslant 0 after ... 3 Consider the following equivalent representations: \begin{align} 1000 + 1000 &= 999 + 1001 \\ 499 \times 1001 + 1000 &= 501 \times 999 \\ 500 \times 999 + 1000 &= 500\times 1001 \end{align}  The first shows that a unique representation can have no more than one $1000$, and cannot contain both $999$ and $1001$. The second shows that a ...

3

Some conditions for a representation $999d_1 + 1000d_2 + 1001d_3 = N$ not to be unique. If $d_2 \ge 2$, then $(d_1+1, d_2-2, d_3+1)$ is also a valid representation of $N$. For $N$ to have a unique representation, we must have $d_2 = 0$ or $1$. If both $d_1 \ge 1$ and $d_2 \ge 1$, then $(d_1-1, d_2+2, d_3-1)$ is a valid representation of $N$, so at least ...

2

The amounts can be written as 999$x$ + 1000$y$ + 1001$z$. If we want to add 1 to it: We can increase $y$ and decrease $x$ by 1. We can increase $z$ and decrease $y$ by 1. If neither can be done ($x$ and $y$ = 0), we can increase $x$ by 500 and decrease $z$ by 499 at the very least. So, 1001*498=498498 can't rise to 498499 and any amount starting from ...

2

What your basically asking is Thankfully, Wolfram Alpha has a built-in function for that So the answer is

2

I solved this by considering modulus. Once we can make a number x from the stamps, we can then make any x + 5y by adding y more 5-cent stamps. So, once we can make a number x for each modulus of 5, we can make all the remaining numbers. So, we can make a chart of n, where n is the number of 17-cent stamps, show its value in cents (n*17), and show which ...

1

I'm not sure if this even qualifies as a puzzle; it's more of a math problem. There's a simple formula given on Wikipedia for finding the Frobenius number for a given arithmetic sequence. We can now substitute the values $a=134$, $d=1$ and $s=9$. Using it, we get the answer 2009 as already given by @IvoBeckers

Only top voted, non community-wiki answers of a minimum length are eligible