Problem 1 asks to show that if three numbers are given, each a power of 2 or of 3, or a product of powers of 2 and 3, then either one of these three numbers is a square, or else the product of some of them is a square.

Each of these numbers, and their products, can be written in the form with A number of this form is a square if and only if both and are even.

To a number we associate its “pattern of parities,” the pair Note that if has pattern and has pattern then their product has pattern

If one of the three numbers has pattern we are done. If two of the numbers have the same pattern, their product is a square, and we are done. So we may assume that the numbers have patterns and But then the product of the three of them is a square.

More generally, one can check that if positive integers are given (), and their prime factorizations together involve only primes, then there is a (non-empty) subset of these integers whose product is a square. Try to show this as an extra credit problem.

Problem 2 asks to show that if 9 lattice points are given in there are two such that the midpoint of the segment they determine is also a lattice point. Here, a lattice point is a point all of whose coordinates are integers.

As before, associate to each lattice point its pattern of parity, Note that the midpoint of the segment joining and is It follows that this midpoint is a lattice point iff and have the same pattern of parity.

But there are only 8 possible patterns: each of the three coordinates is either 0 or 1. Since 9 points are given, two must have the same pattern, and we are done.

Problem 3 asks for a list of 4 distinct integers without an increasing or decreasing subsequence of length 3.

There are many possible ways of doing this. For example,

43.614000-116.202000

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Tuesday, April 13th, 2010 at 10:59 am and is filed under 187: Discrete mathematics. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

Let $C$ be the standard Cantor middle-third set. As a consequence of the Baire category theorem, there are numbers $r$ such that $C+r$ consists solely of irrational numbers, see here. What would be an explicit example of a number $r$ with this property? Short of an explicit example, are there any references addressing this question? A natural approach would […]

Suppose $M$ is an inner model (of $\mathsf{ZF}$) with the same reals as $V$, and let $A\subseteq \mathbb R$ be a set of reals in $M$. Suppose further that $A$ is determined in $M$. Under these assumptions, $A$ is also determined in $V$. The point is that since winning strategies are coded by reals, and any possible run of the game for $A$ is coded by a real, […]

Yes. This is obvious if there are no such cardinals. (I assume that the natural numbers of the universe of sets are the true natural numbers. Otherwise, the answer is no, and there is not much else to do.) Assume now that there are such cardinals, and that "large cardinal axiom" is something reasonable (so, provably in $\mathsf{ZFC}$, the relevant […]

Please send an email to mathrev@ams.org, explaining the issue. (This is our all-purpose email address; any mistakes you discover, not just regarding references, you can let us know there.) Give us some time, I promise we'll get to it. However, if it seems as if the request somehow fell through the cracks, you can always contact one of your friendly edit […]

The characterization mentioned by Mohammad in his answer really dates back to Lev Bukovský in the early 70s, and, as Ralf and Fabiana recognize in their note, has nothing to do with $L$ or with reals (in their note, they indicate that after proving their result, they realized they had essentially rediscovered Bukovský's theorem). See MR0332477 (48 #1080 […]

The paper MR1029909 (91b:03090). Mekler, Alan H.; Shelah, Saharon. The consistency strength of "every stationary set reflects". Israel J. Math. 67 (1989), no. 3, 353–366, that you mention in the question actually provides the relevant references and explains the key idea of the argument. Note first that $\kappa$ is assumed regular. They refer to MR […]

Start with Conway's base 13 function $c $ (whose range on any interval is all of $\mathbb R $), which is everywhere discontinuous, and note that if $f $ only takes values $0$ and $1$, then $c+f $ is again everywhere discontinuous (since its range on any interval is unbounded). Now note that there are $2^\mathfrak c $ such functions $f $: the characteris […]

Yes, there are such sets. To describe an example, let's start with simpler tasks. If we just want $P\ne\emptyset$ with $P^1=\emptyset$, take $P$ to be a singleton. If we want $P^1\ne\emptyset$ and $P^2=\emptyset$, take $P$ to be a strictly increasing sequence together with its limit $a$. Then $P^1=\{a\}$. If we want $P^2\ne\emptyset$ and $P^3=\emptyset$ […]

The result was proved by Kenneth J. Falconer. The reference is MR0629593 (82m:05031). Falconer, K. J. The realization of distances in measurable subsets covering $R^n$. J. Combin. Theory Ser. A 31 (1981), no. 2, 184–189. The argument is relatively simple, you need a decent understanding of the Lebesgue density theorem, and some basic properties of Lebesgue m […]

No, not even $\mathsf{DC}$ suffices for this. Here, $\mathsf{DC}$ is the axiom of dependent choice, which is strictly stronger than countable choice. For instance, it is a theorem of $\mathsf{ZF}$ that for any set $X$, the set $\mathcal{WO}(X)$ of subsets of $X$ that are well-orderable has size strictly larger than the size of $X$. This is a result of Tarski […]