3
$\begingroup$

This problem asks to use Well Ordering Principle to prove any integer greater than or equal to 8 can be represented as the sum of nonnegative integer multiples of 3 and 5.

Here's where I'm at:

For the sake of contradiction assume that there is a nonempty set C such that, C :: = {n >= 8 (only positive integers) | n CAN'T be represented as a linear combination of 3 and 5}

By WOP C contains a least element m. m >= 9 because n=8 can be represented as a linear combination of 3 and 5.

I'm stuck here. I have to find a contradiction that shows C is an empty set but not sure how to approach this. Any hints? Thanks.

$\endgroup$
4
  • $\begingroup$ "prove that any integer greater than or equal to 8 can be represented as$\ldots$" could be construed as "Pick any integer greater than or equal to 8 and prove that it can be represented as$\ldots$". But I don't think that's what you mean. Just say "every" instead of "any" and all ambiguity vanishes. $\endgroup$ Aug 10, 2014 at 22:27
  • 1
    $\begingroup$ Show this minimal criminal can't be $\gt 10$, and then show it is not $8$, $9$, or $10$.. $\endgroup$ Aug 10, 2014 at 22:31
  • 2
    $\begingroup$ @MichaelHardy What is the difference between saying "Prove that every integer $\geq 8$..." and "Prove that any integer $\geq 8$..."? I am not the original poster of the problem, but I am confused by how saying "every" changes the problem $\endgroup$
    – layman
    Aug 10, 2014 at 22:31
  • $\begingroup$ @user46944 : "Pick any card" does not mean "Pick every card". "Prove that any X is Y" can similarly mean "Pick any X and prove that it is Y". But "Any X is Y" without further context means "Every X is Y". But "Prove that every X is Y" cannot mean "Pick any X and prove that it is Y". ${}\qquad{}$ $\endgroup$ Aug 10, 2014 at 23:04

5 Answers 5

6
$\begingroup$

If $m$ can't be represented as a sum of non-negative integer multiples of $3$ and $5$, then neither can $m-3$. Therefore $m$ cannot be greater than $10$, as if $m \geq 11$ then $m-3 \geq 8$, and thus $m-3$ would be in $C$, contradiction since $m$ is the least element of $C$. Now we just check the few remaining cases, which are $m=8,9,10$.

$\endgroup$
5
  • $\begingroup$ Just note that this argument nicely generlizes if we replace the symbols $3,5,8$ with $a,b,a+b$; in which case: every number at least $a+b$ can be written as a multiple of $a$ and $b$. Also, the remaining cases would then be the integers from $a+b$ upto $a+b+min\{a,b\}-1$ (I think!). $\endgroup$ Aug 11, 2014 at 19:16
  • $\begingroup$ @Moses Not true. For example, if $a=2$ and $b=4$ then you can only get even numbers. If $a$ and $b$ are relatively prime then this will probably work. $\endgroup$ Aug 12, 2014 at 0:23
  • $\begingroup$ Good call! Maybe just an even-odd pair suffices, rather than relatively prime. I dunno; nonetheless, good thoughts :) $\endgroup$ Aug 12, 2014 at 16:11
  • $\begingroup$ The OP's example is not even-odd. Also, $12$ and $15$ cannot give you $28$, for example; $12$ and $15$ have $3$ as a common factor, so they only generate a subset of the multiples of $3$. $\endgroup$ Aug 12, 2014 at 22:47
  • $\begingroup$ Neat, so relatively prime may be it :) $\endgroup$ Aug 13, 2014 at 21:32
1
$\begingroup$

As soon as you can represent three consecutive integers as $3x+5y$, you can represent them all by just adding a $3$ to the previous representations. Since $8=3+5,9=3+3+3$ and $10=5+5$, all the integers $\geq 8$ can be represented.

Another way to prove this is to consider that: $$ r(n)=|\{(a,b)\in\mathbb{N}^2:3a+5b=n\}|$$ is the coefficient of $x^n$ in the product: $$ (1+x^3+x^6+x^9+\ldots)(1+x^5+x^{10}+\ldots),$$ hence: $$\begin{eqnarray*}r(n)&=&[z^{n}]\frac{1}{(1-z^3)(1-z^5)}\\&=&[z^n]\left(\frac{1}{15(1-z)^2}-\frac{1}{5(1-z)}+h(z)\right)\end{eqnarray*}\tag{1}$$ where: $$h(z) = \sum_{\xi\in Z}\frac{\operatorname{Res}\left(\frac{1}{(1-z^3)(1-z^5)},z=\xi\right)}{\xi-z}$$ and $Z=\left\{\exp\frac{2\pi i}{3},\exp\frac{4\pi i}{3},\exp\frac{2\pi i}{5},\exp\frac{4\pi i}{5},\exp\frac{6\pi i}{5},\exp\frac{8\pi i}{5}\right\}$. Since the sum of the residues is $0$, the contribute to the coefficients given by the residues in $Z$ can never exceed $\frac{|Z|}{5}=\frac{6}{5}$. Hence we just need to prove that for any $n\geq N$, $$[z^n]\left(\frac{1}{15(1-z)^2}-\frac{1}{5(1-z)}\right)>\frac{6}{5}$$ holds, in order to prove that any $n\geq N$ can be represented as $3x+5y$. However: $$[z^n]\left(\frac{1}{15(1-z)^2}-\frac{1}{5(1-z)}\right)=\frac{n+1}{15}-\frac{1}{5},$$ hence we can take $N=21$ and fill the remaining cases ($n\in[8,20]$) by hand.

$\endgroup$
0
1
$\begingroup$

My proof is similar to Gyu Eun Lee's:

Let S(n) be the proposition that n is an integer greater than or equal to 8, and P(n) be the proposition that n can be written as integer multiples of 3 and 5.
Let C be the set of counterexamples, C::={n | S(n) and NOT(P(n))}. By W.O.P, there exists a smallest element in C, call it m. We verify P(8), P(9), P(10), so m must be greater than 10 to be a counterexample. Then the number (m-3) is greater than or equal to 8 and less than m, so P(m-3) holds; it follows P(m) must hold as well (m is (m-3) plus a multiple of 3), contradicting NOT(P(m)). Thus C is in fact empty.

$\endgroup$
0
$\begingroup$

Can we do it as follows?

  1. Let P(n) = for all natural number n >= 8, exists k_1, k_2 such that n = 3k_1 + 5k_2
  2. Let C = {n >=8|NOT(P(n))}
  3. Assume C is not empty. By well ordering principle, there exists a smallest element d in C.
  4. d does not equal to 3k_1 + 5_k2 for any integer k_1, k_2
  5. check: P(8),P(9),P(10) holds, so d > 10.
  6. d > d - 1 >= 8
  7. so d - 1 = 3k_1 + 5k_2 for some k_1, k_2
  8. then d = d - 1 + 1 = 3k_1 + 5k_2 + (6 - 5) = 3(k_1 + 2) + 5(k_2 - 1). A contradiction
$\endgroup$
0
$\begingroup$

Let P(t) is the property that for every $t \geq 8$ there are exist $k_1,k_2$ such that $t = 3k_1 + 5k_2$.

Let C be the set : C ::= {t $\in N$ || NOT(P(t))}.

For the purpose of obtaining contradiction we assume that C is not empty.

There is the smallest element, $t_0 \in C$

$t_0 \geq 11$ since P(8),P(9),P(10) holds.

We have that :

$t_0 - 1 = 3k_1 + 5k_2$

$t_0 = 3(k_1 + 2) + 5(k_2 - 1)$

which contradicting the fact that $t_0$ can not be written as a linear combination of 3 and 5

$ -> $ C is empty

$\endgroup$
1
  • $\begingroup$ I see him/her stuck at proving this question when using WOP and i want to check whether my answer is correct $\endgroup$
    – Lê Lâm
    Jul 10, 2021 at 4:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .