Hints to exercises
Fill in the blanks:
- \(p\) is a \(\underline{~~~~~~~~~~~~~~}\) number, and
- \(p\) is greater than \(\underline{~~~~~~~~~~~~~~}\).
All you have to do to show that some number is odd, is produce the integer \(k\) that the definition of “odd” says has to exist. Hint: the same number could be used to prove that \(128\) is even.
You want to argue about the sum of two generic rational numbers. Maybe call them \(a/b\) and \(c/d\). The definition of ``rational number’’ then tells you that \(a\), \(b\), \(c\) and \(d\) are integers and that neither \(b\) nor \(d\) are zero. You add these generic rational numbers in the usual way — put them over a common denominator and then add the numerators. One possible common denominator is \(bd\), so we can express the sum as \((ad+bc)/(bd)\). You can finish off the argument from here: you need to show that this expression for the sum satisfies the definition of a rational number (quotient of integers with non-zero denominator). Also, write it all up a bit more formally.
Suppose that \(x\) is an odd number and \(y\) is an even number. Since \(x\) is odd there is an integer \(k\) such that \(x=2k+1\). Furthermore, since \(y\) is even, there is an integer \(m\) such that \(y=2m\). By substitution, we can express the sum \(x+y\) as \(x+y = (2k+1) + (2m) = 2(k+m) + 1\). Since \(k+m\) is an integer (the sum of integers is an integer) it follows that \(x+y\) is odd.
If we write \(x+y\) for the sum of two integers that is even (so \(x+y = 2k\) for some integer \(k\)), then we could subtract what from it to obtain \(x-y\)?
Begin your proof like so:
Suppose that \(x\) is a real number such that \(\frac{2}{3}< x < \frac{3}{4}\).
You need to multiply all three parts of the inequality by something to “clear” the fractions. What should that be?
The definition for the floor of \(12x\) will be satisfied if \(8 \leq 12x < 9\) but unfortunately the work done previously will have deduced that \(8 < 12x < 9\) is true. Don’t just gloss over this discrepancy. Explain why one of these inequalities is implied by the other.
You may be tempted to write “Since x is odd, it can be expressed as \(x = 2k+1\) where \(k\) is an integer.” This is slightly wrong since the variable \(k\) is already being used in the statement of the theorem. But, except for replacing \(k\) with some other variable (maybe \(m\) or \(j\)?) that is a good way to get started. From there it’s really just algebra until, eventually, you’ll find out what \(k\) really is.
The premise that \(6 \!\mid\!(a+b)\) is a bit of a red herring (a clue that is designed to mislead). The premise that you really need is that \(a+b\) is even. Can you deduce that from what’s given?
Suppose that \(x\) is a real number and \(x\not\in{\mathbb Z}\). Let \(a = \lfloor x \rfloor\). By the definition of the floor function we have \(a \in{\mathbb Z}\) and \(a \leq x < a+1\). Since \(x \not\in{\mathbb Z}\), we know that \(x \neq a\) and so we may strengthen the inequality to \(a < x < a+1\). Multiplying this inequality by \(-1\) we obtain \(-a > -x > -a - 1\). This inequality may be weakened to \(-a > -x \geq -a - 1\). Finally, note that (since \(-a-1 \in{\mathbb Z}\) and \(-a = (-a-1)+1\) we have shown that \(\lfloor -x \rfloor = -a-1\). Thus, by substitution, we have \(\lfloor x \rfloor+\lfloor -x \rfloor = a + (-a-1) = -1\) as desired.
Well, the statement is that the evenness of a product is the sum of the evennesses of the factors.
This one is pretty straightforward. Be sure to not reuse any variables. Particularly, the fact that \(a \!\mid\!b\) tells us (because of the definition of divisibility) that there is an integer \(k\) such that \(b = ak\). It is not okay to also use \(k\) when the statement “\(b \!\mid\!c\)” is converted.
Cross multiply and solve for \(x\). If you need to divide by an expression, it had better be non-zero!
From the definition of divisibility, you get two integers \(j\) and \(k\), such that \(a = jb\) and \(b = ka\). Substitute one of those into the other and ask yourself what the resulting equation says about \(j\) and \(k\). Can they be any old integers? Or, are there restrictions on their values?
A savings account where we are not depositing or withdrawing funds has a balance that is growing geometrically.
You don’t need all the hypotheses. If \(a\) and \(c\) have different signs, then \(ac\) is a negative quantity
This follows very easily by the method of working backwards from the conclusion. Remember that when multiplying or dividing both sides of an inequality by some number, the direction of the inequality may reverse (unless we know the number involved is positive). Also, remember that we can’t divide by zero, so if we are (just for example, don’t know why I’m mentioning it really…) dividing both sides of an inequality by \(x^2\) then we must treat the case where \(x=0\) separately.
Use the definition of divisibility.
If you work backwards from the conclusion on this one, you should eventually come to the inequality \((x-1)^2 \geq 0\). Notice that this inequality is always true — all squares are non-negative. When you go to write-up your proof (writing things in the forward direction), you’ll want to acknowledge this truth. Start with something like “Regardless of the value of \(x\), the quantity \((x-1)^2\) is greater than or equal to zero as it is a perfect square.”
This is very similar to an earlier problem. See if you can find it.
Use the definition of the binomial coefficients as fractions involving factorials. For example, \[\binom{n}{k} = \frac{n!}{k! (n-k)!}.\]
Write down the definitions, both of the left hand side and the right hand side and consider how you can convert one into the other.
The critical step is to subtract and add the same thing: \(f(x)g(x+h)\) in the numerator of the fraction in the limit which gives the definition of \(\frac{\mbox{d}}{\mbox{d}x} \left( f(x) \cdot g(x) \right)\). Also, you’ll need to recall the laws of limits (like “the limit of a product is the product of the limits — provided both exist”.)
The best hint for this problem is simply to write down the contrapositive statement. It is trivial to prove!
The contrapositive is \((p \!\mid\!x) \; \implies \; (p \!\mid\!x^2)\).
Well, if there was a largest integer — let’s call it \(L\) (for largest) – then isn’t \(L+1\) an integer, and isn’t it bigger? That’s the main idea. A more formal proof might look like this:
Suppose (by way of contradiction) that there is a largest integer \(L\). Then \(L \in {\mathbb Z}\) and \(\forall z \in {\mathbb Z}, L \geq z\). Consider the quantity \(L+1\). Clearly \(L+1\) is an integer (because it is the sum of two integers) and also \(L+1 > L\). This is a contradiction so the original supposition is false. Hence there is no largest integer.
Assume there was a smallest positive real number — might as well call it \(s\) (for smallest) — what can we do to produce an even smaller number? (But be careful that it needs to remain positive — for instance \(s-1\) won’t work.)
Suppose that \(x\) is rational and \(y\) is irrational and their sum (let’s call it \(z\)) is also rational. Do some algebra to solve for \(y\), and you will see that \(y\) (which is, by presumption, irrational) is also the difference of two rational numbers (and hence, rational — a contradiction.)
Well, the problem says to do this by contraposition, so let’s write down the contrapositive: \[ \forall x, y \in {\mathbb Z}, \; x=y \implies x+y \; \mbox{is even}.\] But proving that is obvious!
The contrapositive would be: \[ \forall a,b \in {\mathbb R}, \; (a \in {\mathbb Q}\land b \in {\mathbb Q}) \, \implies ab \in {\mathbb Q}. \] Wow! Haven’t we proved that before?}
If both \(a\) and \(b\) are odd then their squares will be 1 mod 4 — so the sum of their squares will be 2 mod 4. But \(c^2\) can only be 0 or 1 mod 4, which gives us a contradiction.
Suppose by way of contradiction that \(a,b,c,d \in {\mathbb R}\) satisfy \(ab=cd=1\) and that \(a<c\) and \(b \leq d\). By multiplying the inequalities we get that \(ab < cd\) which contradicts the assumption that both products are equal to 1 (and so must be equal to one another).
It sort of depends on what is meant by “a reasonably large range of inputs.” For example the polynomial \(p(x) = 2x+1\) gives primes three times in a row (at \(x=1,2\) and \(3\)). See if you can do better than that.
The intent of the problem is that you find three numbers, \(a\), \(b\) and \(c\), that are all powers of \(2\) and such that \(a\) divides the product \(bc\), but neither of the factors separately. For instance, if you pick \(a=16\), then you would need to choose \(b\) and \(c\) so that \(16\) doesn’t divide evenly into them (they would need to be less than \(16\)…) but so that their product is divisible by \(16\).
Here’s some Sage code that would test this conjecture:
n = 1 for i in [2..8]: n = factorial(i) - n show(factor(n))Of course it turns out that going out to \(8\) isn’t quite far enough.
I would definitely seek help at your friendly neighborhood CAS. In Sage you can loop over the first several prime numbers using the following syntax.
for p in [2,3,5,7,11,13]:If you want to automate that somewhat, there is a Sage function that returns a list of all the primes in some range. So the following does the same thing.
for p in primes(2,13):This statement and the next are negations of one another. Your answers should reflect that.
If a number is irrational, isn’t its negative also irrational? That’s actually a pretty huge hint.
This one and the next are negations too. Aren’t they?
The two numbers could be equal, couldn’t they?
List all of the divisors of \(36 = (2\cdot 3)^2\). See if any of them are bigger than \(6\).
We’d want \(ac\) to be positive (so \(a\) and \(c\) have the same sign) but nevertheless have \(b^2-4ac > 0\). It seems that if we make \(b\) sufficiently large that could happen.
While one could perform fairly complicated arithmetic, expanding expression like \((16k+13)^4\) and then regrouping to put it in the form \(16q+1\) (and one would need to do that work for each of the odd remainders modulo \(16\)), that would be missing out on the true power of modular notation. In a “\(\pmod{16}\)” calculation, one can simply ignore summands like \(16k\) because they are \(0 \pmod{16}\). Thus, for example, \[\begin{align*} (16k+7)^4 \pmod{16} & = 7^4 \pmod{16} \\ & = 2401 \pmod{16} \\ & = 1. \end{align*}\]
So, essentially one just needs to compute the \(4\)th powers of \(1, 3, 5, 7, 9, 11, 13\) and \(15\), and then reduce them modulo 16. An even greater economy is possible if one notes that (modulo 16) many of those cases are negatives of one another — so their \(4\)th powers are equal.
It is probably obvious that the “cases” will be the possible remainders when divided by \(6\). Numbers of the form \(6q+0\) will be multiples of \(6\) and are clearly not prime. The other forms that need to be eliminated are \(6q+2\), \(6q+3\), and \(6q+4.\)
Write the sum as \(n + (n+1) + (n+2)\).
If there are two pebbles on any node we will be able to reach all the other nodes using pebbling moves (since every pair of nodes is connected).
It should be clear that the pebbling number is at least \(8\) — \(7\) pebbles could be distributed, one to a node, and the \(8\)th node would be unreachable. It will be easier to play around with this if you figure out how to draw the cube graph “flattened-out” in the plane.
The 2-digit challenge is do-able by hand (just barely). The \(4\) digit question certainly requires some computer assistance!
Note that \(15 = 3^2 + 2^2 + 1^2 + 1^2\). Also, if \(15\) were expressible as a sum of fewer than \(4\) squares, the squares involved would be \(1\), \(4\) and \(9\). It’s really not that hard to try all the possibilities.
The following Sage code generates all the numbers up to \(100\) that can be written as the sum of at most \(3\) squares.
var('x y z') a = [s^2 for s in [1..10]] b = [s^2 for s in [0..10]] s = [] for x in a: for y in b: for z in b: s = union(s,[x+y+z]) s = Set(s) H = Set([1..100]) show(H.intersection(s))By trichotomy, x is either zero, negative, or positive. If x is zero, its square is zero. If x is negative, its square is positive. If x is positive, its square is also positive.
If you know something about determinants it would help here. The determinant will be 0 if there are two identical rows (or columns) in the finished array. Also, if there is a row or column that is all zeros, player Zero wins too. Also, cyclically permuting either rows or columns has no effect on the determinant of a binary array. This means we lose no generality in assuming player One’s first move goes (say) in the upper-left corner.
Can you say “Pythagorean triple”? I thought you could.
\(6^3\) can be expressed as such a sum.
How about even integers? Is there a smallest one? That’s my example! You come up with a different one!
Consider the set \(\{ 1, 1/2, 1/4, 1/8, \ldots \}\). Does it have a smallest element?
Yeah, I’m going to keep weaseling…
Unique existence proofs consist of two parts. First, just show existence. Then, show that if there were two of the things under consideration that they must in fact be equal.
If at first you don’t succeed, try googling “scissor paper rock lizard spock.”