 Lv 758,123 points

# Awms A

Questions26
• ### Catalan Numbers and beyond!?

First off, let me warn you that this comes from my messing around with the Catalan numbers. It's, as far as I know, not a textbook problem, so there may not be a solution. Point being this: I appreciate any input, but don't spend too much time if you start pulling out your hair.

On the other hand, it could be a very simple problem and I'm just have a brain fart, which could always happen.

----------

As you might already know, the Catalan numbers

1/(n+1) * [ (2n) choose n ]

count a lot of things. For instance, they count the number of monotonic lattice paths on an n by n grid of squares such that the path doesn't go above the diagonal.

See, for instance:

https://en.wikipedia.org/wiki/Catalan_number

I want to throw a curve ball at this situation. I want to add a rectangle to the right side of this n x n square so that we end up with a n x k rectangle. Then we count the number of monotonic lattice paths on this n x k rectangle which doesn't go above the diagonal of the ORIGINAL square.

There's a way to count this recursively by looking at how high the path is when it finally reaches the right side of the square, but this recursive solution doesn't actually help me.

So the question: Is there a closed form (it can involve a finite sum, but nothing recursively defined) which counts this?

Thanks!

• ### How is the modulus (%) implemented in C++?

For various reasons, I've become quite curious about what the % operator does _internally_ in C++.

For instance, one could define N%k for 0 < k < N by repeated subtraction, as in

while(N >= k) {

N -= k;

}

return N;

but this would be very bad ( floor(N/k) steps is too much!! ).

Therefore, I was wondering:

How is the modulus (%) actually implemented in C++?

Is it dependent on the compiler or the system you're running on?

Is there any online documentation which answers this type of question? (I have similar questions about integer division, bitwise operators, comparison operators, etc.)

-----------

Alternatively, here is a more explicit question. Its answer should be fairly illustrative, with or without the previous answers...

Suppose N is some non-negative integer, stored as an unsigned int, or an unsigned long long, etc... What is the difference between

N % 4

and

N & 3

?

2 AnswersProgramming & Design6 years ago
• ### Is there anywhere to report glitches in Yahoo Answers?

I keep on running into more and more problems with the new format.

Glitches like...

* Punctuation will randomly become giberish code, most often with apostrophes

* In responding to comments to your answer, it will interpret the "less than" and "greater than" symbols as part of code or something, so instead of a clarification, the response ends up being nonsense.

And of course, I have some gripes that aren't related to glitches, persay, like...

* No way to edit responses to comments when the above happens.

* Putting the answers between your text box and the question makes it so you sometimes cannot see the question you're trying to answer while you're answering it.

Is there anywhere to report these issues to someone who might be able to work on them?

I know nearly all the people on here aren't in contact with Yahoo at all, but it would be nice if there were some way to know whether they're even aware of such issues...

• ### Find the limit (fairly difficult, may be related to Maclaurin series of e^x)?

Find the given limit:

lim { e^-n * (1 / 0! + n / 1! + n^2 / 2! + n^3 / 3! + ... + n^n / n!) }

as n goes to infinity.

This was a problem on a friend's exam a while back. I ended up evaluating the limit after he and I talked about it, but I had to use some decently high-level tools on the way. If anyone is interested, I'll give the sketch of what I did, but I'm curious to see if anyone can solve it differently.

• ### Set theory and Infinite cardinals?

So this might have a quick solution, but I'm having a mental block for some reason... anyway, here it is:

Let X be a set such that |X| is infinite. Prove there is a subset A of X such that

|A| = |X \ A|.

That is, the cardinality of A is equal to the cardinality of its complement.

Is there a quick direct proof of this? (as opposed to a proof by contradiction)

• ### Minimal primes and ring extensions?

Suppose R is a subring of S and suppose p is a minimal prime ideal of R.

Prove or disprove:

p is contracted.

i.e. There is some prime ideal q of S such that q intersected with R is p.

• ### In first-order logic, is this argument valid?

Every x is an integer.

Therefore some x is an integer.

-----

For how simple this argument seems, it's causing me lots of headaches. Personally, I don't want it to be valid...

• ### Does "Topology" by Munkres ever mention filters?

I just started looking through Munkres, since my current Topology class is using it. However, it surprises me that I find no mention to filters (though he does have a short section about nets). A quick look at the index shows no mention of filters.

First, do you know if filters ever appear in the Munkres' "Topology" (2nd ed.)? E.g. as an exercise, without naming them, etc.

Second, it is my experience that filters are more natural to the study of topology than nets are. Do you know if there is a reason why Munkres never seems to mention filters, while he does have a set of exercises for nets? I.e. Is there a school of thought among topologists that prefers nets over filters?

Thanks!

• ### How do you interpret a phrase like "right-wing nut jobs" or "dirty liberals"?

Would the speaker be referring to the admittedly smaller group of people who are both "right-wing" and "nut jobs" (resp. "dirty" and "liberals"), or would the speaker be referring to everyone "right-wing"/"liberal" and stating "nut job"/"dirty" is implied?

• ### Why do most critics never finish the Donald Berwick quotation?

"It’s not a question of whether we will ration care. It is whether we will ration with our eyes open. And right now, we are doing it blindly."

When the news first hit, I saw the full quotation, but ever since, it has been

"It’s not a question of whether we will ration care. It is whether we will ration with our eyes open."

in every mention I've seen in the news and on blogs.

Why do you think most critics never finish the quotation?

Do they think that last phrase doesn't give more information on Berwick's philosophy, or do they think finishing the quotation would hurt their point?"

And if it's the latter, what is the role of news? Is it to inform or to persuade?

• ### Find the limit of the area bounded by the diagonals?

Let n be a positive integer and consider a regular (2n+1)-gon with sidelength 1.

Now, draw every diagonal the polygon has. Due to symmetry, this gives us a picture that is somewhat pleasing to the eye. For instance, see

http://en.wikipedia.org/wiki/File:4-simplex_graph....

http://en.wikipedia.org/wiki/File:6-simplex_graph....

http://en.wikipedia.org/wiki/File:8-simplex_graph....

http://en.wikipedia.org/wiki/File:10-simplex_graph...

Note that at the center of the original (2n+1)-gon sits another (2n+1)-gon bounded by the drawn diagonals.

Now the questions:

(1) Find the area of the smaller (2n+1)-gon as a function of n.

(2) As n goes to infinity, does this expression converge? If so, to what value?

• ### Coin-Flipping Game : Who Will Win?

Suppose we flip a fair coin three times. Then HTH (first heads, then tails, then heads) and TTH (first two tails, then heads) are equally likely to occur.

Now, flip a fair coin repeatedly until we flip either HTH or TTH in a row. If TTH shows up before HTH, then I win. If HTH shows up before TTH, you win.

What is the probability that you win? If we were gambling and I paid out 1:1, would you play?

• ### Zero divisors vs. singular matrices?

Let A and B be nonzero n-by-n matrices (say, with entries in the complex numbers) such that

AB = 0.

We can easily see that both A and B are singular.

However, suppose we start with just the assumption that A is a nonzero singular matrix. Then is A a "zero divisor"?

i.e. Can we find a nonzero matrix B such that AB = 0.

If A is always a zero divisor, can you prove it?

And if it isn't always a zero divisor, can you find a counterexample?

• ### When does the Zariski topology on a commutative ring form a locally compact space?

Definitions (just for completion's sake, mostly):

For the definition of the zariski topology, see http://en.wikipedia.org/wiki/Zariski_topology#The_...

X is locally compact = Every point of X has a compact neighborhood.

I don't even know if the answer is known or, if it is known, whether it is interesting. However, I found myself thinking about it after one of the Ph.D students wrote something on my white-board.

• ### LCD? A question about notation?

So I'm well aware of the lack of consensus in what notation to use...

We have lcm(x,y) = [x,y] = x v y

and we have gcd(x,y) = gcf(x,y) = (x,y) = x ^ y.

I mean, I could even understand sup(x,y) for the first and inf(x,y) for the second, if we're defining them in terms of the divisor lattice.

However, there is one notation that I personally find to be incorrect:

LCD(x,y) = Least Common Denominator of x and y

to mean the same as the least common multiple of x and y.

(for supporting evidence, note http://dictionary.reference.com/browse/denominator )

So finally to the question (actually a few):

(1) What notation do you use?

(2) What country do you live in?

and the more important one for me:

(3) Do you know of any textbooks which use the notation LCD(x,y) to mean the least element such that both x and y divide it?

(And before anyone says it, yes I know that one needs to find the least common multiple of the denominators to compute the least common denominator - note the difference in semantics though)

• ### Can I tilt a sony bravia back on its stand?

I just bought a Sony Bravia 42" TV. It was the store model, so the stand was installed already; however, it seems to lean forward a little bit. I don't think it'll matter, but my fiancee is worried it may fall forward.

Is there a way to adjust how the TV is mounted on the stand so it tilts back a little more? The only thing I can think of is putting something under the stand so that it's uneven, and I'm not likely to do that - it seems like it may be more dangerous than the current problem.

• ### Quotient Rings of Polynomial Rings + Isomorphisms =?

I'm taking a course in commutative rings (at least, that's what it's supposed to be) but the instructor has never constructed a single isomorphism. Point being, he assigned some problems and I don't even know how to think about them, moreover explicitly find an isomorphism.

Let C denote the field of complex numbers and <f> the principal ideal generated by f.

Show that

C[x, y] / <x^2 + y^2 - 1> = C[x, x^-1]

( = denotes an isomorphism )

• ### Anyone know a good site for learning linear algebra (Jordan form)?

In particular, I'm trying to find a good explanation of how to find the Jordan canonical/normal form of a given n x n matrix. As of right now, I have looked at the wikipedia page (doesn't really help) and Dummit/Foote (would help, probably, but that particular topic is hard to follow in it).

So if anyone able to explain or send me to a decent site that explains how to find the Jordan canonical/normal form, I'd be most grateful!

Thanks.

• ### A "hard" question about the number 10...?

Actually, I have no clue whether this is hard or not...

Prove or disprove:

10 cannot be written as the difference of squares of rational numbers.

• ### "Interesting" numbers and the Hangman paradox in proof theory?

First off, wikipedia gives a *decent* discussion of the hangman paradox. If you don't know it, you can find it here:

http://en.wikipedia.org/wiki/Unexpected_hanging_pa...

Now, normally, we don't seem to care much about this paradox in mathematics, since there isn't even consensus on where the paradox originates from. However, it occurs to me that a standard proof that appears in mathematical literature may be an instance of this same paradox.

-----

Proof that all natural numbers are interesting:

First, let N be the set of natural numbers and X the set of interesting natural numbers. We want to show that N is a subset of X.

Suppose otherwise, that there is an element n of N that isn't interesting, then the set N\X is nonempty.

Since N is well-ordered, N\X has a least element - call it y. Well, the fact that y is the least natural number that isn't interesting makes it interesting. Thus y is interesting and y is not interesting. Contradiction.

Therefore every element of N is interesting. Q.E.D.

-----

Now, this proof may just be included in books in a tongue-and-cheek manner, but it seems like a disservice to mention it but not mention its connection to such a famous paradox. After all, when we finish the proof, any single element is just one element in a sea of other "interesting" elements, making it rather boring (which to me shows the connection to the paradox).

Does anyone know enough about proof theory to confirm or deny that these situations are identical?