Wikipedia:Reference desk/Archives/Mathematics/2007 December 6

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 6

desktop tower defence

I'm trying to figure out the number of possible arrangements of pellet towers. You can build 16 towers (I'm just going with what you start out with). There are 25 x 21 squares on the board, however, the spaces overlap. So if you put a tower in the upper left hand corner (1,1), you could not put another tower in (1,2). How many possible arrangements of the 16 towers are there? 70.171.229.76 (talk) 01:32, 6 December 2007 (UTC)

In case you haven't noticed, there is another, more subtle, restriction: you can't place towers so as to completely block off one of the entrances. As a first supercrude estimate, the answer is between 10²⁰ and 2x10³⁰. Algebraist 01:42, 6 December 2007 (UTC)

Oh yeah I forgot about that part... Let's just assume for this that that doesn't apply and that the only restrictions are the ones I mentioned above. 70.171.229.76 (talk) 02:17, 6 December 2007 (UTC)

OK, let's first consider the 25*21 grid, and say we were allowed to take any cell, except ones we've chosen. This gives ${\dfrac {525!}{509!}}=O(10^{43})$ as an upper bound. To calculate a lower bound, consider the 13*11 non-overlapping grid, which gives ${\dfrac {143!}{127!}}=O(10^{34})$. To calculate a better lower bound, consider that every cell we choose removes itself and 8 surrounding cells (adjacent and diagonals), which gives us something $\prod \limits _{j=0}^{15}\left(525-9j\right)=O(10^{42})$. Of course, ones on the edge remove 6, and corners remove 4. I'll think about this later. mattbuck (talk) 16:13, 7 December 2007 (UTC)

The bounds I gave are essentially the same as your first two, but I have been taking the towers to be indistinnguishable, so we disagree by a factor of 16!. Algebraist 16:54, 7 December 2007 (UTC)

Oops, my bad, forgot the 1/16! I needed to multiply by. mattbuck (talk) 16:57, 7 December 2007 (UTC)

Big O notation has a technical meaning; I would use here ≈ instead.

Since our upper and lower bounds differ only by a factor of roughly 10, we can get much better estimates by way of simulation. In each iteration, choose 16 locations randomly (I don't even think checking for total overlap is worthwhile); check if it is legal. Then calculate the proportion of legal arrangements. Multiply by the total number of unrestricted possibilities, and you get your estimate. This can also work with the additional requirement that the creeps must have a path to the exit. -- Meni Rosenfeld (talk) 17:23, 8 December 2007 (UTC)

I have run such a simulation, and concluded that the result, disregarding the path requirement, is extremely likely to be between $2.05\cdot 10^{29}$ and $2.07\cdot 10^{29}$. -- Meni Rosenfeld (talk) 19:03, 12 December 2007 (UTC)

Find the prime factorization 330

What is the prime factorization 330. —Preceding unsigned comment added by 69.119.211.11 (talk) 04:27, 6 December 2007 (UTC)

The first prime numbers are 2, 3, 5, 7, 11, 13, 17, 19. Try if some of them divide 330, and can be multiplied together to get the prime factorization of 330. PrimeHunter (talk) 04:37, 6 December 2007 (UTC)

See also Prime factorization, in case you don't know what this means.  --Lambiam 14:14, 6 December 2007 (UTC)

cryptography

Can some one please suggest some good books on cryptography. Thanks--Shahab (talk) 08:59, 6 December 2007 (UTC)

For general/historical interest, Simon Singh's "The Code Book" is a great read. However, it's not very technical and there is very little on modern cryptography. 134.173.93.150 (talk) 09:32, 6 December 2007 (UTC)

Books on cryptography might interest you. I'm biased, but if you want a comprehensive formal treatment, Goldreich's Foundations of cryptography might be a good choice. -- Meni Rosenfeld (talk) 16:23, 6 December 2007 (UTC)

More math help

My teacher, as unhelpful as ever, now assigned us new problems. I got several other problems like this using guess and check, but it was going so slow, that I wondered whether there was a better way to do this.

Number 1: FACTOR: $21x^{3}+7x^{2}y-35xy^{2}-42x$ On this one, I factored out the Greatest Common Factor and got $7x(3x^{2}+xy-5y^{2}-6)$. I'm not sure what to do now.

Number 2: FACTOR: $0.09x^{3}-0.66x^{2}y+1.21xy^{2}$ I don't know how to start on this either. Is it prime (irreducable)?

Number 3: FACTOR: $x^{2}-3xy-6x+18y$ I also thought this was prime.

I need to understand how to do this. S♦s♦e♦b♦a♦l♦l♦o♦s ^{(Talk to Me)} 22:02, 6 December 2007 (UTC)

On 2, there is at least one factor you can pull out quite quickly, and at the same time you may want to consider pulling out a factor of, say, 1/100, to make things look a bit nicer. For 3, see if you can divide it into two expressions with two terms each, that when you factorise separately they have a common factor. For 1, I *think* it's irreducible from that point, but don't quote me on that. Confusing Manifestation(Say hi!) 22:42, 6 December 2007 (UTC)

OK, so I make 1: $9x^{3}-66x^{2}y+121xy^{2}$? S♦s♦e♦b♦a♦l♦l♦o♦s ^{(Talk to Me)} 23:11, 6 December 2007 (UTC)

I may be stupid, but what is the goal of this and when is a term irreducible? I can factor any arbitrary function of x and y out of any of the terms. I suppose you want the result to be "simple" in some sense, but in what sense exactly? —Preceding unsigned comment added by 84.187.91.68 (talk) 23:56, 6 December 2007 (UTC)

Now, for 2, take out a common factor of x, and note that what remains has a particular, and hopefully familiar, form. It may help to notice that both 9 and 121 are squares, and that 66 is a multiple of their square roots... -- Leland McInnes (talk) 01:02, 7 December 2007 (UTC)

What you're doing in problems 1 and 3 here is factoring by grouping. The tip-off that this is a likely strategy is the fact that you're factoring a polynomial with four terms. The example in the wikipedia article, is, unfortunately, needlessly complicated. This should apply for all three problems. After you've pulled out all the GCFs, the next thing to do is look at the first pair of terms and see if you can factor out a common factor (a challenging problem set might require you to try terms one and three if terms one and two don't have a common factor, but that doesn't apply here). We then factor out a common factor from the last two terms. We should get some factor multiplied by a binomial + some other factor multiplied by a binomial with the two binomials matching. Then we can treat those binomials as a GCFs and get binomial times binomial.

Let's look at an example problem, factoring $x^{2}-3x-xy+3y$. In this case are first terms are x² and -3x. We can factor out an x and get $x(x-3)$. Repeating the process on the last two terms we factor out y and get $y(-x+3)$ but remember that we can also pull out a negative and get instead $-y(x-3)$. That gives us an overall expression of $x(x-3)-y(x-3)$.

We finish up by factoring out the (x-3) from each term and end up with $(x-y)(x-3)$ (do you see where that x-y came from?) That should be enough to get you through this problem set. Donald Hosek (talk) 01:29, 7 December 2007 (UTC)

Quick update, on problem 1, you can (and should) try the grouping algorithm, just to see what happens when it doesn't apply, which in this case it doesn't. Donald Hosek (talk) 01:35, 7 December 2007 (UTC)

For problem 2, after you've factoring out GCFs, the fact that you've got perfect squares in the first and last terms suggests that you should use the perfect square pattern to try factoring. Donald Hosek (talk) 01:32, 7 December 2007 (UTC)

(cancel indent) Yes, 3x^2+xy-5y^2-6 is irreducible, unless I'm more drunk than I thought. Since it's quite unlikely you'd be set an example which fails to factor nicely, you might want to check you've got the question right. Algebraist 02:10, 7 December 2007 (UTC)

Sorry, I was eating dinner and doing some English homework. I compied the problems number for number, and in the directions, it says that some of the problems may actually be prime. Let me get my sheet out and evaluate everything... I will comment further. S♦s♦e♦b♦a♦l♦l♦o♦s ^{(Talk to Me)} 02:44, 7 December 2007 (UTC)

Yes, Leland, I forgot to factor out x and I noticed it while eating...I finished solving 2. I should have gotten it earlier, but I wasn't paying attention. ... Ah, I see what you are saying, Donald (Allow me to call you that). The example in the wikipedia article was overly-complicated. I do see where the x-y came from (excellent example). OK, I see how it doesn't work on 1. S♦s♦e♦b♦a♦l♦l♦o♦s ^{(Talk to Me)} 02:59, 7 December 2007 (UTC)

Thank you everyone on your helpful assistance! S♦s♦e♦b♦a♦l♦l♦o♦s ^{(Talk to Me)}

Years

Why do you guys believe in years? Years are not actually real. Neither are months or weeks. —Preceding unsigned comment added by Bane of Durin (talk • contribs) 23:53, 6 December 2007 (UTC)

A year is the length of time it takes the Earth to complete one full orbit of the sun and is quite "real", just like days, in the sense that it has an astronomical basis. Months are based on the lunar year, i.e. the time it takes for the moon to complete one full orbit of the Earth, but for historical reasons the calendar months are no longer synchronised with the lunar cycle. Weeks are religious in origin, with many religions striking upon a 7 day week. The reason months and weeks are still used even though there is no astronomical basis for them is the same reason hours, minutes and seconds are used. It's convenient to have units of time of varying length, and the week is deeply ingrained into much of human culture as part of the labour cycle. So it's not that people "believe" in these things, they're just lengths of time which are useful when discussing time intervals and for establishing human schedules. Maelin (Talk | Contribs) 00:26, 7 December 2007 (UTC)

Why do you believe in "Why"? And "are" and "or". These aren't real. How silly of you. risk (talk) 01:29, 7 December 2007 (UTC)