Revision as of 19:35, 19 November 2006

Reference Desk

November 13

Practical Application: Linear Programming

Hello,

I start a job tomorrow where I have to travel to stores and make sure that all Intuit products are on the shelf and looking organized. I have 14 stores, a starting destination and an ending destination. I have calculated the times (in minutes) it takes to go from each point to every other point. I must hit all 14 stores in 4 days. I do not get paid until I reach the first store (from the starting point), and I am off the clock once I finish my last store.

I took a class a few years ago that taught me how to solve this problem, but essentially I would like to minimize the amount of time for each of these 4 routes and minimize the amount of "off the clock driving" I do. I do not want to do more than 4 stores in any day.

Can anyone give me any guidance in this matter? For reference, I posted the times between all points here

Thanks --Yoyoceramic 03:17, 13 November 2006 (UTC)

That link doesn't work, it asks for a username and password. Can you post the data directly here ? StuRat 03:22, 13 November 2006 (UTC)

Sure, I also fixed it above.. http://www.trinitywiki.com/ROUTES.htm thanks --Yoyoceramic 03:23, 13 November 2006 (UTC)

This looks like a homework problem to me. But giving you the benefit of a doubt, I'd have to point out that the time between stops won't be fixed, but will vary by traffic, which will depend on the time of day. This, and other intangible constraints, like wanting to be near a good restaurant at lunch time, will make any calculations rather useless. Just chart out a "reasonable" path, then tweak it to account for traffic, etc., until you get to the best solution. Also, I'd want to see them listed on a map to come up with the initial path. StuRat 03:28, 13 November 2006 (UTC)

Also, I don't understand why your start and end locations are apparently different. You would want to find the four stores closest to the start location, and go to each of those first on each of the four days. Similarly, you would want to find the four locations closest to the end location, and go to those last on each of the four days. From there, I'd go with trial-and-error to find the next closest stores from those 8, and finally link them all together into a single path. StuRat 03:31, 13 November 2006 (UTC)

Thank you for giving me the benefit of the doubt, but to clarify, this is not a homework problem (although I can see why you might think that). You can find more about the Intuit Flexforce program I am apart of here: http://www.collegecentral.com/elon/BulletinDetail.CFM?MessageID=23173&UnivCode=ELO.

• Also, here is the map of the locations --Yoyoceramic 03:38, 13 November 2006 (UTC)

• The reason the Start and End are different is because I will start from my home each day and end up at my school (see map)--Yoyoceramic 03:38, 13 November 2006 (UTC)

I get "this collection no longer exists" when I look at the map. StuRat 04:00, 13 November 2006 (UTC)

Sorry about that, I don't know why that happened. Try this one

I still don't see any locations marked on the map. StuRat 04:10, 13 November 2006 (UTC)

Akk yeah sorry - I'm working on that - I am trying to figure out how to share it out... give me a minute --24.174.142.137 04:12, 13 November 2006 (UTC)

One way is to take a screen grab and post that to Misplaced Pages. StuRat 04:18, 13 November 2006 (UTC)

Here's one series of routes I've come up with that's "pretty good". You will likely want to tweak it to make it better:

            STOPS           TIME
       ----------------  -----------
Day 1:  6 - 11 - 1           36
Day 2:  8 - 10 - 9 -  2      62
Day 3: 13 - 12 - 3           44
Day 4:  7 -  4 - 5 - 14      47

StuRat 04:07, 13 November 2006 (UTC)

Thanks for the suggestion. Here is a map. 2 is a southern outlier, and the other numbers I drew on there because some flags overlap each other. --Yoyoceramic 04:21, 13 November 2006 (UTC)

OK, using that map I came up with this plan:

            STOPS            TIME
       -----------------  -----------
Day 1:  6 -  2 -  1           54
Day 2:  8 - 10 - 12 -  7      48
Day 3: 13 -  9 -  3           43
Day 4: 11 -  4 -  5 - 14      49

This plan makes the number of miles driven each day more consistent. StuRat 05:26, 13 November 2006 (UTC)

The problem is more like a variation on the Travelling salesman problem, which is much harder than linear programming. The best I've found is this:

            STOPS         TIME
       -----------------  ----
Day 1:  3 -  9 -  2        49
Day 2:  7 -  8 - 10 - 12   51
Day 3: 11 - 14 -  4 -  5   44
Day 4: 13 -  6 -  1        29
                          ----
                          173

 --Lambiam 12:53, 13 November 2006 (UTC)

A solution with a shorter total:

            STOPS         TIME
       -----------------  ----
Day 1:  4 - 12 - 10 -  5   52
Day 2:  7 - 11 - 14        34
Day 3:  8 -  3 -  9 -  2   50
Day 4: 13 -  1 -  6        29
                          ---
                          165

Slightly longer, but more balanced:

            STOPS         TIME
       -----------------  ----
Day 1:  1 -  6 -  2        42
Day 2:  4 - 12 - 10        47
Day 3:  7 - 11 - 14 -  5   36
Day 4:  8 -  9 -  3 - 13   43
                          ---
                          168

 --Lambiam 22:25, 13 November 2006 (UTC)

The total time is low, but remember they don't get paid until the first stop and are off the clock after the last stop, so we want the first and last stop to be as close to the start and end points as possible. I weighted that even higher than keeping the time low (I'd actually prefer the on-the-clock time to be as high as possible). StuRat 22:29, 13 November 2006 (UTC)

As demonstrated above, the total driving time using a reasonable route (which I could draw just by looking at the map in under 1 minute) should be under 3 hours. Some tweaking and guessing and such could potentially save 10, may be even 30 minutes off the total driving time. Now a question: how much combined time did you spend trying to solve this problem, creating the maps and the tables, typing etc? I admit this may be fun to play with numbers, but so is this attempt to ridicule you. (Igny 22:41, 13 November 2006 (UTC))

I would like to thank everyone for their advice. I had my first run today. Since I did not check back on the wiki until now, I did the run:

            STOPS         TIME
        -----------------  ----
 Day 1:  3 -  10 -  5 - 1   53

Which actually took a little longer than anticipated, but I think the traffic premium is universal throughout all the routes. --Yoyoceramic 23:01, 13 November 2006 (UTC)--24.174.142.137 22:59, 13 November 2006 (UTC)

I don't believe the slow down due to traffic is the same. There tends to be more traffic on highways heading into the city in the morning rush hour, and on highways heading out of the city in the afternoon rush hour. Timing your trips so you are doing inventory during rush hour will also save you from suffering sitting in traffic at that time. Another factor I try to figure into my drives is avoided driving into the Sun, which means not heading east at sunrise and west at sunset. StuRat 00:02, 14 November 2006 (UTC)

Using as the main objective to minimize unpaid time (UT), the best I've found is:

            STOPS           UT   TIME
       -----------------    --   ----
Day 1:  7 - 11 -  1         21    33
Day 2:  8 -  3 -  9 -  2    23    50
Day 3: 13 - 12 - 10 -  6    21    49
Day 4: 14 -  4 -  5         31    42
                            --   ---
                            96   174

To find this, I dusted off some programs I had lying around. The data was entered by copy/paste. Some time went into formulating the objective function and constraints, but a similar amount into formatting the output.  --Lambiam 10:29, 14 November 2006 (UTC)

Most complex strategic game for two players

Which is the most complex or most difficult strategic game for two players. Maybe these are two questions. I'm talking about any game that actually exists, has a certain tradition and that is played by lay people. I don't mean a game that was just devised by mathematicians to set a record in complexity. The game should not use random elements like shuffled cards, dice or random starting positions either. Is it go? Is it chess? Is it something else? Thanks in advance! Pat 85.2.50.69 11:46, 13 November 2006 (UTC)

This is a pretty nebulous question. The rules of go and chess are both quite simple, though they allow for extraordinarily deep strategy. Will you consider games without complete information? ×Meegs 12:12, 13 November 2006 (UTC)

In terms of the computational complexity of games, specifically two-player games with perfect knowledge and no randomness such as chess, go, checkers, etc., there isn't much difference between games: most are known or believed to be either PSPACE-complete or EXPTIME-complete. The difference between these two complexity classes doesn't seem to have much to do with the difficulty of actual play, but depends more on whether there is a guaranteed short number of moves after which the game ends (e.g. in Othello or Hex each move fills up a board position) or whether the longest possible game is much longer in number of moves than the board size (true in Chess unless you impose the fifty move rule). But that doesn't mean they are all equally easy for a human or computer to play, and it doesn't tell you whether the difficulty in each games is more strategic or tactical. In terms of difficulty of programming a computer to play as well as a human, Go seems to be king; some have claimed that this is due to its high branching factor but I'm not convinced by that argument because gomoku has the same branching factor but is much easier for computers. I guess to give a better answer, I'd need to know what the purpose of the question is — Bragging rights? Estimate of number of years of study needed to master the game? Interest in writing computer programs for hard problems? Studying human intelligence? —David Eppstein 18:51, 13 November 2006 (UTC)

Thanks to both of you! I dont know much about math and didn't realize this was a cloudy question. Nah Mr. Eppstein I'm neither a programmer nor a neurologist. I suck at chess and don't even know the rules of go. I read somewhere that go was the most difficult game in the world and more complex than chess. I just asked out of curiosity and for no other purpose. Thanks again. Pat 83.77.223.48 11:41, 14 November 2006 (UTC)

See Go_ranks_and_ratings#Game_depth for a summary of a "scientific"/"objective" argument for believing that go is "deeper"/more "complex" than chess. The idea is that you can quantitatively compare player-rating scales between different games by using the observed probability that a (slightly) lower-ranked player will win against a higher-ranked one. Then you discover that the rating ladder for go is longer than the one for chess. (Do we have a better article on this anywhere?) —Blotwell 15:15, 14 November 2006 (UTC)

I don't think anyone has directly said it yet, but Go is still a more difficult problem for computer scientists than Chess (see our article on Computer Go). To my knowledge, there is no computer Go player anywhere near as good (in terms of who it can match) as the famous Deep Blue which was able to go toe-to-toe with the world champion in Chess. - Rainwarrior 17:31, 14 November 2006 (UTC)

What are amicable numbers good for?

Can anyone any application of amicable numbers?Mr.K. 21:56, 13 November 2006 (UTC)

There are no applications as far as I am aware. JoshuaZ 22:00, 13 November 2006 (UTC)

Why do you have a concept without function? You could also say that numbers like 45-54 or 68-86 are the Yin-Yang numbers. But why would someone introduce a new useless concept? Mr.K. 22:07, 13 November 2006 (UTC)

Recreational mathematics. Some people like numbers, they like to play with them, so they figure some trivia just to keep themselves busy and entertained. Lots of interesting and arguably important fields in mathematics started out like that (like the study of tessellations)... In any case, it can't hurt, and it's always fun to play around with these concepts. ☢ Ҡi∊ff⌇↯ 22:17, 13 November 2006 (UTC)

Can you give an application of ballet, fire breathing, or Rubik's cube?  --Lambiam 22:37, 13 November 2006 (UTC)

Fitness, attracting members of the opposite sex, and driving yourself completely batty, respectively. - Braveorca 05:14, 14 November 2006 (UTC)

Well, now I understand why I can never hang on to a girl: I do ballet to attract members of the opposite sex and Rubik's cube for fitness... Joe 07:44, 14 November 2006 (UTC)

May we conclude that it was the fire breathing that drove you batty?  --Lambiam 10:32, 14 November 2006 (UTC)

I still don´t get the point of why do you have an invented concept. The problem is not the useful (useful=material) application of it, but the function of the concept within the science. And can someone answer me what about the yin-yang numbers? Should I start an article with them? Mr.K. 11:59, 14 November 2006 (UTC)

The truth is that it's not really a point of "why", but of "why not"? These concepts weren't described out of need, but out of curiosity. They may not play any significant role, but they are interesting as numerical curiosities. Simply that. You gotta keep in mind, though, that playing with numbers may reveal interesting and useful patterns, as it has before....

About your yin-yang numbers, you could write an article about them, but it would most likely get deleted. ;) ☢ Ҡi∊ff⌇↯ 12:31, 14 November 2006 (UTC)

There is a certain group of numbers of which only a handful have ever been proven to exist. So what do they call them? Well, it's obvious - normal numbers. Work that out if you can. JackofOz 05:27, 15 November 2006 (UTC)

November 14

Why generalised functions are called distributions

I would like to know whether there is any (historical) reason for using the term distributions for generalised functions. How do generalised functions generalize probability distributions, as claimed in distributions. Mairan 04:22, 14 November 2006 (UTC)

I don't think it answers your search for historical reasons, except that it gives you another link to look for your answer in, but I changed the redirect on generalised function so that it is now the same as generalized function. Perhaps this and distribution deserve to be merged, but generalised function and generalized function shouldn't go to different places. —David Eppstein 04:38, 14 November 2006 (UTC)

Perhaps, it is because it generalises measure in some sense and probability distributions are measures. Mairan 07:07, 14 November 2006 (UTC)

How to calculate Volume.

I want the formula or calculation to convert fuel level in a cylinderical tank lying horizontally having dimension of 1825mm Diameter and 3960mm long.We have a dip stick which gives the level in millimeter but we want that with the calculation or formula we can get that millimeter reading in liters. An answer to this Question will be highly appreciated.

The answer is not very simple. I hope you have some familiarity with algebra and trigonometry. I use radians below for angles, where the size of a right angle is π/2, instead of 90°. Also, for keeping the formulas general and readable, let R = 0.9125m be the radius (half the diameter) and L = 3.960m the length. If we take a cross section of the tank, we get a circle of radius R in which the fuel occupies a circular segment (see the yellow part of the picture there; you have to turn it upside down in your mind). If A is the area of that circular segment, then we have that the volume V = A × L. So the issue is how to calculate A. Using the same notation as in the article Circular segment, the angle θ is determined by d/R = cos(θ/2), where d = R − h. Therefore:

θ = 2 arccos((R − h) / R)

A = /₂R(θ − sin θ)

V = 1000 A L l/m

where the last factor 1000 comes from going from m (cubic metres) to l (litres).

Two examples. First, for h = 100mm:

h = 0.10000

(R − h) / R = (0.9125 − 0.1) / 0.9125 = 0.89041

θ = 2 arccos 0.89041 = 0.94510

sin 0.94510 = 0.81055

A = 0.5 × 0.9125 × (0.94510 − 0.81055) = 0.05601

V = 1000 × 0.05601 × 3.960 = 222

The second example is with h = 1100m, so h > R:

h = 1.10000

(R − h) / R = (0.9125 − 1.1) / 0.9125 = −0.20548

θ = 2 arccos(−0.20548) = 3.55550

sin 3.55550 = −0.40219

A = 0.5 × 0.9125 × (3.55550 − (−0.40219)) = 1.64770

V = 1000 × 1.64770 × 3.960 = 6525

 --Lambiam 10:11, 14 November 2006 (UTC)

help i want to pass in maths exams of mvita school based kenya

Help wed i will be doing MATHS AND ENGLISH i want to pass in them so please i want some formulas for maths

The plural of "formula" is "formulae". That should help with the English exam. Tompw 11:54, 14 November 2006 (UTC)

Please see pedantic. Both "formulas" and "formulae' are acceptable plurals of "formula".  --Lambiam 13:41, 14 November 2006 (UTC)

It is very difficult to give you advice, because you have not indicated at what level the exams are. There are dozens of formulas at each level, altogether hundreds. And if your exams are tomorrow, you have little time left to study. You need not only to know the formulas, but also how to use them.

For an elementary level, look at Fraction, Elementary algebra, Linear equation, and Quadratic equation.

Slightly more advanced: Logarithm, Logarithmic identities, Trigonometry, List of trigonometric identities.

For texts to study, visit the Wikibooks:Mathematics bookshelf.  --Lambiam 14:01, 14 November 2006 (UTC)

I would suggest talking to your teachers for advice for exams. Formulas is not correct; it is not acceptable in english, it may be where you are, but that makes it in no way less wrong.Englishnerd 18:49, 14 November 2006 (UTC)

Formulas is not acceptable in Latin. In English, for words with a Latin root, it is usually correct to use either the S pluralization or the original Latin plural. Check a dictionary, and you'll find both listed. - Rainwarrior 18:54, 14 November 2006 (UTC)

It actually is acceptable in Latin in the sentence Nonnullas formulas desidero. There used to be a time when scholars, when employing a Latin or Greek noun in a text in the vernacular, would put it in the appropriate grammatical case of its declensional paradigm.  --Lambiam 07:47, 15 November 2006 (UTC)

A dictionary? Whose authors probably speak some vulgar language like *gasp* English? I've always said that if you want to know how to speak English, there's no better source than a bunch of Romans who died two millennia ago. Millenniums. Sigh. Tesseran 05:33, 16 November 2006 (UTC)

BTW, formulas gets 36 million hits on Google, formulae 11 million. I'm not sure if Google's plural+singular function might be checking in and I normally detest Google for this kind of thing but it does agree with my expectation. Nil Einne 17:22, 20 November 2006 (UTC)

Solution of Travelling Salesman Problem using Hopfield nets

Has anyone solved the Travelling Salesman problem using Hopfield nets.If so then would you be kind enough to answer the following questions. 1.What is the probability of arriving at the shortest distance path for 5,8,10,12,15,18,20 cities? 2.Is it possible to attain 90% chance of finding the shortest path for 10 cities ? 3.How does the probability of finding the shortest path vary with the number of cities ? 4.Are there algorithms and heuristics to drastically increase the chance of finding the correct path ? 5.Is there any mathematical proof or theorem to suggest that the path lines which form the shortest path do not intersect inside the polygon formed but only at the vertices or outside the polygon.

It was difficult to find resources on these questions. If you would be kind enough to answer any one of them please e-mail me the answers at .

Did you follow the link given at Hopfield net? Apparently someone has. The questions concerning the probabilities can only be answered in regard to a specific collection of data sets, or a specified process for generating input data sets.  --Lambiam 18:45, 14 November 2006 (UTC)

Concerning question 4: Yes, there is an algorithm that gives you a very good chance indeed of finding the true shortest path. It is knowns as brute-force search. Unfortunately, it takes very long. No algorithms or heuristics are known to drastically increase that chance while taking polynomial time. As to question 5, if this is about the Euclidean TSP where the cities are points in the plane and the distances are the Euclidean distances, then it is not hard to show that if two segments intersect, say A1—A2 intersect B1—B2, where the direction of travel is the same for both, you get a shorter tour by "rewiring" this as A1—B2 and B1—A2 (thereby reversing the direction for part of the tour). Basically, in a convex quadrilateral, the sum of the length of the diagonals exceeds the sum of the lengths of two opposite sides.  --Lambiam 19:29, 14 November 2006 (UTC)

pi

Does pi ever end

Nope. Splintercellguy 23:55, 14 November 2006 (UTC)

That was the short answer. Here is a bit longer answer. All numbers with finite decimal representations are rational numbers, which means they can be written as a fraction p / q for integers p and q. (And in the special case of a finite decimal representation q is or divides a power of 10.) The number pi, on the other hand, is known to be irrational. This was already proved in 1761 by Lambiam Lambert. See further Pi#Numerical value and Pi#Properties.  --Lambiam 07:31, 15 November 2006 (UTC)

Just to clarify on Lambiam's response, some numbers without finite decimal representations can still be rationals. For example, 1/3 = 0.333..., etc. In fact, all recurring decimals are rational and all rationals have decimal expansions that either terminate or are recurring. The numbers which do not terminate and are not recurring are, as mentioned, the irrational numbers. Popular examples of irrational numbers are pi, e, and the square root of 2. Maelin (Talk | Contribs) 08:48, 15 November 2006 (UTC)

Just to clarify on Maelin's response, the same applies not only to decimal representation, but to every positional numeral system:

• for every natural radix p>1, each rational number has a recurring representation in the system with that radix p (this includes finite representations, which are recurring, too, with repeating zeros, like 1.17 = 1.1700000...),
• and each irrational number has infinite, nonrecurring representation in every positional numeral system.

--CiaPan 16:31, 15 November 2006 (UTC)

November 15

The phrase "quadratic in"

I am working through an example in a textbook and have reached the following equation:

${\displaystyle y^{2}-2y=x^{3}+2x^{2}+2x+3}$

The text then seeks to solve for y in terms of x, stating that this is a simple matter since the equation is "quadratic in y", and proceeds directly to:

${\displaystyle y=1\pm {\sqrt {x^{3}+2x^{2}+2x+4}}}$

I am unfamiliar with the phrase "quadratic in y" and do not understand how the solution was obtained. Any advice would be appreciated.

--202.168.12.132 04:04, 15 November 2006 (UTC)

I am not sure myself but maybe this happened

${\displaystyle y^{2}-2y=x^{3}+2x^{2}+2x+3}$

add one to both sides to "complete the square"

${\displaystyle y^{2}-2y+1=x^{3}+2x^{2}+2x+3+1}$

${\displaystyle (y-1)^{2}=x^{3}+2x^{2}+2x+4}$

${\displaystyle (y-1)=\pm {\sqrt {x^{3}+2x^{2}+2x+4}}}$

${\displaystyle y=1\pm {\sqrt {x^{3}+2x^{2}+2x+4}}}$

152.3.72.50 04:20, 15 November 2006 (UTC)

"Quadratic in y" means "involving no powers of y greater than the second power y". The origin of this terminology is related to the origin of the phrase "y squared", since "quadratus" is Latin for "square". McKay 04:55, 15 November 2006 (UTC)

Many thanks. My confusion is obliterated. --202.168.12.132 05:02, 15 November 2006 (UTC)

(after edit conflict) 'Quadratic in y' means that if you treat every other symbol but y as a constant, you get a quadratic equation. In other words, all terms involving y are either (something).y or (something).y^2, and not (for example), y^5, 1/y, ln(y), sin(y) or e^y.

The solution given is the normal quadratic solution ${\displaystyle (-b\pm {\sqrt {b^{2}-4ac}})/2a}$ with substitutions:

• ${\displaystyle a=1}$
• ${\displaystyle b=-2}$
• ${\displaystyle c=-(x^{3}+2x^{2}+2x+3)}$

--ColinFine 05:06, 15 November 2006 (UTC)

presenting our firm's finacial health before vanture capitalist

how to present financial health of the company in front of vanture capitalist to understanding them to invest in the company? what are the different tools to be used?

I don't think they would be as much concerned with the current financial health of the company as much as it's potential for growth. After all, even if you are in bankruptcy, they could fix that, if they see themselves making a nice profit by helping you out. You should, however, have a detailed budget of what you intend to do with the money they invest. StuRat 07:06, 15 November 2006 (UTC)

This is not really a mathematics question. Try Misplaced Pages:Reference desk/Miscellaneous. Think from their point of view: Why would they want to invest in your company? Basically you have to show that the expected profit is (much) larger than the money to be invested. What is your elevator pitch? One advice: if you are presenting in English, have your presentation checked for correct spelling and grammar.  --Lambiam 07:21, 15 November 2006 (UTC)

You will need to be able to explain clearly:

1. How much you want the VC to invest
2. What you will use the money for
3. How much equity you are prepared to give the VC in exchange for their investment - be prepared to negotiate on this
4. How long you will need this investment for - VCs are typically looking to invest for between 2 and 10 years
5. How much you think the company will be worth at the end of this period - this is the hardest part, as you will need to show credible financial projections and demonstrate that you understand your market, your competition etc. The VC will try to talk down your valuation - this is a negotiating tactic to make a case for receiving more equity - so you need to have confidence in your projections. Gandalf61 08:32, 15 November 2006 (UTC)

The venture capitalist would almost certainly expect to see a business plan. I expect there are articles on financial ratios and discounted cash flow you should look at. If I was the VC, I would be mostly interested in what my rate of return on investment would be - so it would be good to be able to give a projected internal rate of return. In the UK, and probably in North America and other countries, there are government funded bodies that can give you advice about this. You could talk with your accountant about this, but they will probably charge you a lot of money. There are many books published about writing business plans, plus a lesser number about pitching to venture capitalists.

I've just had a look at the financial ratios article, and it could be improved. But any textbook on management accounting will cover financial ratios. If you can, I suggest a trip to a public library to see what books they have. Do not be afraid to tell the librarian what you want to do and ask their help.

Tetromino Game

Suppose there is a game where you have an 8x8 grid that can only be filled with tetrominoes and the game ends once no more tetrominoes can be placed on the grid. What is the maximum number of squares that could be unfilled by the end of a game? --Tuvwxyz (T) (C) 22:23, 15 November 2006 (UTC)

After a bit of playing I've got 20. But I wouldn't know how to prove this mathematically. ;) Vespine 00:21, 16 November 2006 (UTC)

Hmm, just as I thought I was getting a theory I jsut came up with 28... Vespine 00:33, 16 November 2006 (UTC)

I managed 24. I'm not sure much better could be done than 28, but I can't think of any way to prove any of this other than an exhaustive search. Wasn't Tetris proven to be NP-Hard not so long ago? - Rainwarrior 02:34, 16 November 2006 (UTC)

An equivalent formulation would be: What is the minimum number of tetrominoes required to fill the board such that no more tetrominoes can be placed?

This may have a nice graph theoretic equivalent as well - I'm not too sure what it would be, perhaps a matching problem on a graph which represents the grid, and finding a minimal subgraph with certain properties? I'd have to think this one through a little bit more...--ManicLogic 02:33, 16 November 2006 (UTC)

I still think my 28 solution is correct. SPOILER: The 8x8 is split up into four 4x4 groups which are symmetrical about the centre. The very middle is occupied by a 2x2 square block, with each 4x4 corner quadrant containing only two T sections arranged back to back and offset by one, such that the 3 units adjacent to the corner are vacant. I hope that's a clear enough description to recreate it. Vespine 03:54, 16 November 2006 (UTC)

Is this what you mean?

. . t . . T . . . T t t T T t . T T t . . T t t . T . O O . t . . t . O O . T . t t T . . t T T . t T T t t T . . . T . . t . .

Here is 'my' solution:

. I I I I . . . . N N . . L L L N N . J . L . . T . . J I . O O T T J J I . O O T . . . I . T . . T T T I T T . . . T . . . T .

It's not as regular as yours, but gives the same result: 28. --CiaPan 16:59, 16 November 2006 (UTC)

Yes, that's what I came up with. Nice ASCII. :) Definitely still have no idea how to try to prove it! I started to think that 1/3 was the most that could be empty since the pieces of 2x3 area still fill only 2x2 area, leaving 2 units of area empty, but that's obviously wrong, it doesn't take into account leaving empty shapes into which tetrominos can’t fit, like the L shapes made of 3 units I've left in the corners, and the several 1x3 units you have in your pattern. Vespine 21:25, 16 November 2006 (UTC)

A thought... at most you can only have 3 connected empty spaces, and it would take at minimum 8 blocks to surround any 3 connected spaces. However, any boundary of blocks may be shared by two empty spaces, so perhaps this can be done with only four blocks per space. Thus, approximately 3/(3+4) of the space may be filled. With 64 blocks: 64*3/7 = 27. Additionally, the constraints put on the shapes of the tetrominoes (having to be vertically or horizontally connected) probably lowers this number (call it "estimated density of a maximally open solution" or something) a bit more, but the fact that the board has a closed edge counteracts it in the opposite way. This is light-years away from a proof, but maybe a reasonable explanation? - Rainwarrior 23:12, 16 November 2006 (UTC)

Maybe if I attacked the problem of how many open areas a square can touch. Either it's 0 (completely surrounded), 1 (a corner), 2 (a line), or 3 (an end). Since there are no tetrominoes of a single clock, there is no 4. It seems though, that you cannot introduce a 3 without indroducing a corresponding 1 elsewhere, which means that 2 is the best you can do on average, supporting my earlier idea. Hmm... Anyhow, I finally found my own 28:

. S S . . L . . . . S S . L . S L L L . L L S S . . L O O . S . . S . O O L . . S S L L . L L L S . L . S S . . . . L . . S S .

(You can use an L or anything else really to fill the middle hole instead of the O). - Rainwarrior 01:01, 17 November 2006 (UTC)

I wrote a computer program to take a look at this, but I think it would take about a month for this computer to enumerate all of the cases (searching every configuration of 9 or less pieces, since we know the best solution to be not worse than 9 pieces). So... interestingly... an answer by exhaustion is possible. I just can't give it to you at the moment. It will take time. Ha ha ha. - Rainwarrior 02:30, 17 November 2006 (UTC)

Oh wait, I missed one of the factors in that calculation. Change "month" to "forever". Nevermind. - Rainwarrior 02:41, 17 November 2006 (UTC)

November 16

variance of the total sample

Dear Sir/Madam,

I have a question on how to find variance of the total sample. Suppose we have a sample of size N. It is divided into k sub-samples of size f(k), f(1)+f(2)+ ... f(k)=1. n(1)+n(2)+ ... +n(k) = N where n(k) is the number (size) of sub-sample k. Suppose we know the mean and variance of each sub-sample, m(k) and var(k). Question: How can I calculate the variance of the total sample?

I am studying performance of students of different groups (regions). I have only data on regional performances (regional aggregates, no individual data). I want to evaluate total mean and variance from regional data. I would greatly appreciate your help and suggestions on reference texts. Thank you very much for your help in advance.

Best wishes,

Koo Woong Park, Economics researcher

I'm not quite sure what the role of f(k) is; I guess f(k) = n(k)/N. It is not used below. In computing the sample size, two methods are common, one in which a sum of squares is divided by the sample size ((1/n)×SUM), and one in which that sum is divideed by the sample size minus 1 ((1/(n−1))×SUM). The second avoids a bias of the first which underestimates the population variance; see further Variance. In the following, I assume the simpler method has been used in computing var(k); otherwise, they must be multiplied by (n(k)−1)/n(k) first. Writing M and VAR for the mean and variance of the total sample, the formulas are then:

M = (1/N) × Σ_k n(k)m(k)

VAR = (1/N) × Σ_k (n(k)var(k) + (m(k) − M))

 --Lambiam 06:14, 16 November 2006 (UTC)

Map of closest points

Say I want to make a map showing cities, but also the area where that city is the closest.

Within a defined area (eg. a country) if you pick a random point, you can work out the closest city. Around city A, you could define a region A, where at any point in the region, city A will be closer than any other city. How do you calculate the boundaries of this region? I think that these regions will be polygons.

I have tried searching wikipedia and google for an algorithm to do this, but cannot seem to find any.

I am eventually hoping to write a java application that can display this, given coordinates of the points.

Thanks in advance, RobBrisbane 06:41, 16 November 2006 (UTC)

See Voronoi diagram.  --Lambiam 06:46, 16 November 2006 (UTC)

Thanks, while that article does not have an algorithm, knowing what it is called a Voronoi diagram will certainly help. I think i've worked out in my head an algorithm - will try it out. --RobBrisbane 07:18, 16 November 2006 (UTC)

I'm not sure what you expect in the article itself. Through the references and links you can find descriptions of algorithms, and also complete implementations. A robust implementation must handle issues common to many algorithms in computational geometry. Especially important is the role of precision and its effect on accuracy and consistency. We also have a modest practical concern for time and space efficiency. Èuk Roman provides a detailed explanation of one well-known algorithm, that of Steve Fortune. Brief descriptions of several algorithms, though with no concern for robustness, are also online, along with a great deal of other material found through the Voronoi.com web site. Note that some algorithms prefer to compute a Delaunay triangulation, which is then trivial to convert to a Voronoi diagram. (This fact gets but one sentence in our article, despite its importance.) --KSmrq 10:13, 16 November 2006 (UTC)

The basis for all algorithms I know of is to use Delaunay triangulation; for algorithms see there. See further the external links to the CGAL library, which is of high quality.  --Lambiam 10:03, 16 November 2006 (UTC)

Yes, CGAL is a valuable resource. It does have two important limitations: (1) It is an integrated package of routines, making it awkward to extract a small, targeted piece. (2) For some applications its dual-license scheme may pose a modest barrier. --KSmrq 10:20, 16 November 2006 (UTC)

Mathematical Problem

I have a mathematical problem ....

Find the domain & the range of the function :

f(x) = 2x^2+6x-7

Please state what part of the question you don't understand so we can help you. Fredrik Johansson 13:49, 16 November 2006 (UTC)

Never mind that; this question is entirely ill-posed. Stating a formula for a function does not in general restrict or specify its domain, and its range is certainly dependent on that unmade choice. I can imagine this as ${\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {R} }$ (real numbers), or ${\displaystyle f\colon \mathbb {C} \rightarrow \mathbb {C} }$ (complex numbers), or even ${\displaystyle f\colon \mathbb {Z} _{n}^{*}\rightarrow \mathbb {Z} _{n}^{*}}$ (multiplicative group of integers modulo n for any ${\displaystyle n}$). The domain and codomain could even both be ${\displaystyle \mathbb {Z} +{\frac {1}{2}}}$ (the half-integers) or ${\displaystyle \mathbb {A} }$ (the algebraic numbers). The domain and codomain can be different, too, with ${\displaystyle f\colon \mathbb {Z} \rightarrow 2\mathbb {Z} +1}$ (the integers and the odd numbers). How is anyone supposed to learn math by working problems with no answer? (The actual content here is of course the links; perhaps the questioner will find useful information there.) --Tardis 16:47, 16 November 2006 (UTC)

The process of teaching maths - and much science for that matter - consists of telling half-truths and incomplete topics, which then get expanded, replaced, or even contradicted at a later level. To criticise a pedagogic question for being ill-formed relative to the whole of the subject is unreasonable. --ColinFine

Perhaps I was a bit too quick to judge; this question should presumably be interpreted in the recursion theory sense of the word "domain" for partial functions, with all functions at this level taken to be partial functions mapping the reals onto themselves. In that context (which is probably obvious, even if unspecified, to the student), the question certainly has a unique answer. I'll take leave of my soapbox now until some problem that is ill-posed due to thoughtlessness rather than reasonable circumscription arises. --Tardis 15:39, 17 November 2006 (UTC)

Have you read Domain and Range? —Preceding unsigned comment added by 129.162.1.42 (talk • contribs) 16:33, 16 November 2006

To get back to the actual question, there are many methods for solving this type of thing, depending on what you've already been taught. One of the simplest (but also somewhat time consuming) methods is the create a chart of values, then graph those values. I'll start you out:

x     f(x)
==    ====
-2    -11
-1    -11
 0     -7
+1     +1
+2    +13

Now, noticing that f(x) is the same (-11) when x = -1 or -2, this tells us the curve reaches a relative or absolute minimum or maximum in that area. Let's add x = -1.5 to the chart:

x     f(x)
==    ====
-2    -11
-1.5  -11.5
-1    -11
 0     -7
+1     +1
+2    +13

This type of quadratic graph is also symmetrical, so we can add a few more terms to the chart:

x     f(x)
==    ====
-5    +13
-4     +1
-3     -7
-2    -11
-1.5  -11.5
-1    -11
 0     -7
+1     +1
+2    +13

Now graph this chart. This should allow you to see the range and domain. StuRat 01:54, 17 November 2006 (UTC)

Assume we are working over the reals. First note that the highest term has an even power i.e. x, which will dominate the result for large numbers. If you have an odd power then the range will be the whole of R, but even powers will give ranges like if the coeff is negative. The local maxima and minima of the functions will occur when the first derivative is zero, so solve f'(x)=0 and evaluate f(x) at each point. All quadratics they can be written in the form f(x)=m(x-a)^2+n, so a bit of algebra will give a,m,n and the only min/max will occur at x=a. --Salix alba (talk) 09:44, 17 November 2006 (UTC)

I must agree with Tardis that, as presented here, the problem is ill-posed. However, we can make some educated guesses. A problem worded like this would not be seen in a sophisticated class, and this is most likely one of a number of homework problems. Perhaps another problem considers the function f(x) = (1+√x)/(2−x). Therefore we might reasonably assume subsets of the real numbers are sought, for both domain and range. In my example, we must exclude x values that are negative, as well as the isolated value 2; that could be taken to give us a domain. After finding the domain (the permissible inputs), we must explore the possible outputs. In general, this requires insight special to the function. In my example, we know that the square root will always give a non-negative value; and for x ≥ 0, we know that 2−x varies from 2 down to −∞. When x is exactly 0, the value of f(x) is exactly ⁄₂. As x increases toward 2, the denominator approaches zero, overwhelms the numerator, and forces the function value toward +∞. We skip exactly 2, to avoid a divide by zero. Now as x increases toward +∞, the numerator remains positive but the denominator is always negative; therefore the function value goes from −∞ toward 0. We conclude that the range is all of the real line except the half-open interval [0,⁄₂).

The actual given problem is somewhat simpler, but the general idea of partitions and trends applies. --KSmrq 09:48, 18 November 2006 (UTC)

watertesting a gas pipeline

My son needs to watertest a natural gas pipeline that is 5.25 inchs (ID) in diameter. How many gallons of water will it take per foot? thanks...Lyle Corder

email address removed to prevent spam

So, it's a cylinder? And you want the volume of each foot in gallons? So it's a cylinder that's a foot long? --Tardis 16:58, 16 November 2006 (UTC)

Find the area of a circle with a diameter of 5.25 inches (A = piR^2, where R = D/2). Then multiply that by a length of 12 inches to get the volume, in square inches, of one foot's length of pipe. Then convert that value to gallons (there are 231 cubic inches in a gallon). Post his work here for a check. StuRat 01:22, 17 November 2006 (UTC)

Is it sufficient to test a gas pipeline with water? Even if it is water-tight it could leak gas. Yet it seems to be done by professionals. Interesting.

Anyway, since we are given an inner diameter, we may assume a standard pipe with a circular cross section. We must also make another assumption, that the gallons are U.S. gallons, not imperial gallons (and not dry gallons). Then, by definition, a gallon is exactly 231 cubic inches. If we can calculate the volume of a foot of pipe in cubic inches, the rest is easy. That's what StuRat is walking through. To get cubic inches we must work entirely in inches, which is why we convert one foot to 12 inches. We can simplify the area calculation a little by writing A = ⁄₄D, with ⁄₄ approximately equal to 0.7854. By my reckoning, it should take more than 1 gallon and less than 5 gallons per foot. (We don't give full answers in case this is a homework question in disguise.) --KSmrq 10:29, 18 November 2006 (UTC)

Logic problem: Getting data from every computer onto every other computer efficiently

Hi all,

I'm faced with a problem that, were it written down (which it is now), I think would count as a reasonable logic puzzle.

I (will, on Monday) have data on 60 computers. The data do not overlap -- every computer has a different data file. I need to collect all data files and put them on all 60 computers. i.e. all 60 computers will need to have all 60 different data files on them.

The computers are not networked. The "simplest" way would be to use one CD-RW and go from computer to computer to burn all the data, and then go back to each computer and unload all the data. This, of course, requires sticking in a CD 120 times, and will take quite a while.

However, I have unlimited numbers of CD-RWs, and two or three other people to help me. I feel sure that there is some remarkably clever, more efficient way to do this. Can anyone think of a clever way?

Thanks for any thoughts!

--John

This is known as an all-to-all broadcast or all-gather in parallel computing. Unfortunately, no articles, but I do have a link to the MPI specification; perhaps further research will turn up clever implementations. However, I can say this: ${\displaystyle 2n-1=119}$ CD interactions is the best you can do, because each computer must both read data and write data, and every computer except one must be writing to a disc that doesn't have everything on it and thus another disc (or the same disc again) must be provided to finish reading. The algorithm you stated achieves this optimum, since the last computer you visit can read and burn at the same visit. So the only thing you can hope to achieve is to utilize your accomplices to parallelize the project. The best strategy that occurs to me is just to divide up the computers into ${\displaystyle m}$ (nearly) equal groups, one for each of your ${\displaystyle m}$ people. Then each of you go to each of your ${\displaystyle \sim n/m\!}$ computers and burn, then go to all ${\displaystyle n}$ computers and load. Again, the last computer you burn with can also read, so that's a total of ${\displaystyle n+m(n-1)}$ CD insertions; with ${\displaystyle m}$ people, it should take as long as one person doing ${\displaystyle n/m+n-1}$ insertions, which is a speedup over the optimal serial algorithm of ${\displaystyle {\frac {2n-1}{n(1+1/m)-1}}\approx {\frac {2}{1+1/m}}{\mbox{ for }}n\gg 1}$. So with 3 assistants you can only expect to get ${\displaystyle {\frac {2}{4/3}}=150\%}$ improvement. Hope this helps, and have fun! --Tardis 17:18, 16 November 2006 (UTC)

Ok, I almost understand your parallel solution, though not quite. Here's a solution I've come up with -- is it more or less efficient than the one you are suggesting (or is it the exact same solution)? The three people take 20 computers each, and burn the data onto one CD each (three CDs total). We then load all 60 files onto one computer. We then burn all 60 files onto 3 CDs. We then go around and each load the data onto 20 computers each.

This would be the same number of total interactions, but would only take the time required for 40 interactions (20 load, 20 unload), (+/- 1 for the "base" computer?).

Is that the right solution? Thanks! --John

1. Burn data on first pass: ${\displaystyle n}$ operations (parallel).
2. Pick one of the final computers and load everything on it: a free copy from the disc already there and then ${\displaystyle m-1}$ operations (serial).
3. Burning new discs, reusing whichever is last in it: ${\displaystyle m-1}$ operations (serial).
4. Putting data on all other computers: ${\displaystyle n-1}$ operations (parallel).

So your total cost is ${\displaystyle 2n+2m-3}$ disc insertions (although perhaps burns should count as costly?), which is better than my ${\displaystyle n+mn-1}$ if ${\displaystyle n+2m-2<nm}$ or ${\displaystyle 2m-2<n(m-1)}$ or ${\displaystyle 2<n}$, which it certainly is. But you have serial operations; your total time is ${\displaystyle \left\lceil {\frac {n}{m}}\right\rceil +2m-2+\left\lceil {\frac {n-1}{m}}\right\rceil \approx 2\left({\frac {n}{m}}+m-1\right)}$, which is better than my ${\displaystyle n/m+n-1}$ if ${\displaystyle {\frac {n}{m}}+2m-1<n}$ or ${\displaystyle 2m(m-1)+1<n(m-1)}$, which it is for ${\displaystyle m\ll n}$. So that is better all around. --Tardis 18:29, 16 November 2006 (UTC)

(after edit conflict) Well, I would try this: pass a CD A through computers 1..30 to collect their data, while your friend does the same with disk B on comps 31..60. When you're finished, store files 1..30 from A on comp.30, and let him store files 31..60 on comp.60. Then you swap CDs, so you can update the B with files 1..30 from comp.30 (and comp.30 with files 31..60 from B disk), and your friend updates A with files 31..60 (and comp.60 with files 1..30 from A). Then you both walk back and fill remaining 29 of your respective 30 computers with 60 files. This way each of you sticks a disk 60 times, and each CD gets sticked 60 times, so you save approx. half of time.

For N people (N dividing 60) the process splits into three phases:

1. each person collects data from 60/N computers on a disk,
2. disks are circulated (N-1) times on N computers, to collect 60 files on N comps and N disks,
3. disks walk back through 60/N-1 comps each.

Each person makes (and each disk undergoes) 2·60/N + N - 1 read/write operations, ie. N=4 people do the work in 33 steps. If N does not divide 60, some fractions add to the above estimation. --CiaPan 17:30, 16 November 2006 (UTC)

(Note my different notation; my ${\displaystyle m=N}$.)

1. Collecting: ${\displaystyle n}$ operations (parallel).
2. Circulating and updating ${\displaystyle m}$ computers: ${\displaystyle m(m-1)}$ operations (parallel).
3. Redistributing: ${\displaystyle n-m}$ operations (parallel).

So the total cost here is ${\displaystyle 2n+m(m-2)}$ disc insertions, which is certainly competitive for ${\displaystyle m\ll n}$. Since it's all parallel, the total time is just ${\displaystyle 2\left\lceil {\frac {n}{m}}\right\rceil +m-2}$, as you said (except that you forgot one of your ${\displaystyle -1}$s), which is precisely ${\displaystyle m}$ time steps shorter than John's time whenever ${\displaystyle \left\lceil {\frac {n}{m}}\right\rceil =\left\lceil {\frac {n-1}{m}}\right\rceil }$ (which is true for ${\displaystyle n=60}$ except at ${\displaystyle m\in \{1,59,\dots \}}$; at ${\displaystyle m=1}$ all these become the same algorithm). --Tardis 18:29, 16 November 2006 (UTC)

Conclusion: CiaPan's answer is always the best of these three for reasonable ${\displaystyle m}$, although oddly enough for ${\displaystyle m>3}$ its total amount of work is larger than John's; it just parallelizes better. (At ${\displaystyle m\in \{1,3\}}$ the amount of work is the same, and at ${\displaystyle m=2}$ it's better because of the extreme efficiency of 1 swap.) My answer is horrible: it's best (in terms of time) only for ${\displaystyle m>n}$, and better than John's semi-serial algorithm for ${\displaystyle m>n/2}$. It's better (in terms of work) than CiaPan's handshaking algorithm only for ${\displaystyle m>n}$, and it's the best in work only for ${\displaystyle m=0}$, where the math breaks down! --Tardis 18:29, 16 November 2006 (UTC)

There is another factor which we all missed – it's the read/write time. We count the number of operations only, assuming the work is split among people and does not parallelize any further. But that's wrong, this way we simplify the problem. In the real situation one can handle several read/write operations on different computers at (almost) the same time: put a disk into a drive, start the read/write program and, while the operation in progress, go to another computer to start R/W on it, and so on.
Assuming that you can run k R/W actions before the first one completes, you perform k+1 actions in less than twice the single action's time, thus reducing the total time almost by factor ~ (k + 1)/2. The actual gain depends on the ratio of the disk and software handling time to the actual R/W time. And also on the distance you must walk from one computer to the next one. :)
Things get even more complicated when we realize that R/W's take a variable amount of time – appending one file to a CD in the first phase is shorter than appending 10 or 30 files in phase 2, and burning generally needn't be same fast as reading in phase 3...  --CiaPan 19:13, 16 November 2006 (UTC)

Thanks so much for all the answers! It's going to take a little time to digest... As for CiaPan's last comment, indeed this is true, and is a gain I used to good effect today when putting the initial program on all 100 computers myself. With three CDs and good timing, I managed to almost always have 2 drives spinning while I was loading the third.

Thanks a lot! --John

(feel free to keep hashing out the finer math points, if you like)

You said that they are "not networked together", but do they all have Internet access ? If so, this may provide a way to pass files directly between them (via FTP, for example). StuRat 01:13, 17 November 2006 (UTC)

One more approach, may be a bit crazy. Force parallelizing as far as you can, and you get a logarithmic algorithm...

• For two computers you need two CD's: insert them into drives, burn, swap, read — done.
• For four computers take four disks: write simultaneously one file on each, swap disks in computer pairs (1,2) and (3,4), next swap disk pairs, so that comp.1 and 2 get files from 3 and 4, and comps. 3 and 4 get files 1 and 2. This way after two swaps you spreaded 4 files among 4 computers.
• In the next step swap four disks from computers 1..4 with (similarly prepared) four disks from 5..8, and so on — after S swaps you get 2 computers updated with 2 files.

That works fine as long as we have the power of 2 computers. For the given case of 60 computers you'll have to add 4 virtual computers. These are just placeholders on the last table, where you put additional 4 CDs.
The whole routine consists of 7 steps or phases:

1. Put 60 disks into drives and write one file on each (4 spare disks get 'written' no files).
2. Swap every pair of disks (disk n and n+1 for every odd n). Disks 61..64 don't need swapping ;) On each comp append that comp's file to a CD, and copy file from CD to local HD. Now you have 2 files on each comp and each CD.
3. Swap pairs of disks in every four (i.e. swap (1,2) with (3,4), (5,6) with (7,8), ... (57,58) with (59,60)). Disks 60..64 don't need swapping. Add 2 files from each HD to CD, and copy 2 files from CD to HD. Now you have 4 files on each disk.
4. Swap fours of CDs in eights. This is the first step involving four spare disks — CDs 57..60 go to the desk, CDs 61..64 get loaded into computers 57..60. Again copy all four files from each CD to HD and append new four files from HD to CD. Now every CD contains 8 files (except CDs 57..64 which contain 4 real files no 57..60 and 4 ghost files 61..64).

...and so on, until in step 7 you swap disks 1..32 with 33..64 and copy 32 files from each CD 1..28 onto HD 33..60, and 28 files from each CD 33..64 onto HD 1..32. Done! This step contains a CD–to–HD copying only.

The whole process would take only ${\displaystyle 7=\lceil \log _{2}60\rceil +1}$ steps, however each step consists of loading, reading, burning, ejecting and swapping of sixty CDs. That totals to as much as 7×60=420 load-copy-burn-eject sequences. If you can hire 8 people for CD juggling, this method offers you a huge saving of the total process time (only 7 parallel phases!) On the other hand, if you try to do it yourself alone, it would take you much longer than simple algorithms discussed above—the whole gain achieved on parallel R/W would be lost on sequential load-run-eject actions. --CiaPan 03:30, 17 November 2006 (UTC)

November 17

Transportation problem

It is surprising to see that there is no wiki for such a famous problem. Could some one please create one? "Assignment problem" also needs cleanup. I need to study these problems, not at a detail level which would ofcourse require a text book. A wiki with usual depth will suffice.

Thanks and regards,

Did you have a look at Transportation theory? Welcome to Misplaced Pages, the 💕 that anyone can edit. If you can improve Assignment problem, you're welcome to do so.  --Lambiam 10:11, 17 November 2006 (UTC)

The article on Transportation Theory doesn't even consider an algorithm to solve the Transportation Problem, whereby goods are to be sent from several sources to several destinations at minimal total cost. A common one is to use Vogel's Method to get a good initial solution, then improve this by successively replacing one route in use by another not in use. The process is similar in concept to the basic iteration done in the Simplex Method for general linear programming, but done within a table whose rows and columns represent sources and destinations, and whose cell values are the flow along that particular route.

In fact, the article seems to be ludicrously abstract and essentially useless in its present form.81.151.247.61 21:07, 19 November 2006 (UTC)

US - Imperial measurements

How come fluid ounces are different in US customary measurements to those in the Imperial System, when both are based on the density of water? Both measurement systems use the same ounce, and the density of water is pretty much the same globally, ignoring slight changes due to temp/pressure. Laïka 10:05, 17 November 2006 (UTC)

I would guess it's salt fresh water versus ocean water, which have different densities. StuRat 10:34, 17 November 2006 (UTC)

I guess you meant fresh water vs. ocean water. :-) CiaPan 11:29, 17 November 2006 (UTC)

No; even if one was sea water, the measures are still out. They would be closer for brine, but brine seems like a slightly odd choice, given that pure water would be more practical. Laïka 16:19, 17 November 2006 (UTC)

Who said practicality had anything to do with imperial/customary units? Let's not forget the ugly Fahrenheit scale that use some bizzare value of uncertain origin as it's 0 point Nil Einne 17:31, 20 November 2006 (UTC)

Actually, while the Imperial fluid ounce was based on the density of water (at 16.7 °C), the US fl.oz is derived from the US gallon, which is a volume measurement defined as 231 cubic inches. Thus the Imperial gallon and US gallon have entirely distinct operational definitions. (Well, not any more, now that both are defined in terms of SI, but they used to.) EdC 00:06, 18 November 2006 (UTC)

This begs the question of when and why the two countries went their separate ways. The article on gallon offers some background. --KSmrq 10:40, 18 November 2006 (UTC)

November 18

Implicit differentiation

Hello. I don't understand how to differentiate equations like ${\displaystyle y=sin(x+y)}$ for y where y is also part of another function. Could somebody walk me through the steps of this example or a similar one?--El aprendelenguas 23:17, 18 November 2006 (UTC)

Not sure about in general but in this case:

y=sin(x+y) so arcsin (y) = x+y, then x= arcsin (y) - y.

dx/dy can be easily found and by extension dy/dx .

dx/dy = 1/sqrt(1-y*y) - 1 = / sqrt (1-y*y)

dy/dx = sqrt (1-y*y) / (1-sqrt(1-y*y))

In this case I've simply rearranged so that x and y are separate - give another example if you wish..

Probably not what you where asking for? Need more explanation etc or is that ok? —The preceding unsigned comment was added by 87.102.9.39 (talk • contribs) 00:18, November 19, 2006 (UTC).

In the above "sqrt(1−y)" needs to be replaced by "± sqrt(1−y)", since x = sin Z has other solutions than Z = arcsin x, such as Z = π − arcsin x.  --Lambiam 00:42, 19 November 2006 (UTC)

Here is another way:

y = sin(x+y), so (d/dx)y = (d/dx)sin(x+y).

Using the chain rule, this gives:

y' = (1+y')cos(x+y).

The trigonometric function can be eliminated with the identity cos α + sin α = 1:

y' = ±(1+y')sqrt(1−y),

from which you can retrieve the earlier solution by solving for y'. The sign can flip only when |y| = 1, and this differential equation has more solutions (for example, the constant function y = 1) than the original equation. The whole thing is a bit tricky, since you can see when you graph the function that y' → ∞ as x → 0.  --Lambiam 01:07, 19 November 2006 (UTC)

Taking derivative means to find the rate of change AT A GIVEN POINT (a,b) satisfying ${\displaystyle b=sin(a+b)}$. Why ${\displaystyle y'=cos(a+b)/}$ is NOT an acceptable answer? Twma 08:09, 19 November 2006 (UTC)

Is it because any values of a and b can be used regardless of whether those values satisfy the original equation? (bit confused, feels like I am back at school ??) —The preceding unsigned comment was added by 83.100.138.99 (talk • contribs) 17:14, November 19, 2006 (UTC).

To me it is, except I used x and y instead of your a and b. Then your answer is essentially equivalent to my y' = (1+y')cos(x+y). I added the next steps to relate this to 87.102.9.39's answer.  --Lambiam 18:45, 19 November 2006 (UTC)

Since we have an implicit equation, it may be of interest to take a different approach. We are looking at the zero set of the function f(x,y) = y−sin(x+y). A normal to such a curve at a point can be found as the gradient of f, which is the vector ∇f(x,y) = (−cos(x+y),1−cos(x+y)). Rotating the normal clockwise 90° gives a vector tangent to the curve, in this case (1−cos(x+y),cos(x+y)). The slope of this is the derivative of y with respect to x, namely ⁄_1−cos(x+y). For example, at (0,0) the curve is vertical (y′ = +∞); at (⁄₂−1,1) it is horizontal (y′ = 0); and at (π,0) it tilts downward (y′ = −⁄₂). This approach seems both simpler and more flexible.

However, I wonder if the question was really meant to be about how to solve a differential equation, y′ = sin(x+y). --KSmrq 09:42, 19 November 2006 (UTC)

I can't make sense of what users "Lambian" and "KSmrq" have done here - can anyone confirm that their maths makes no sense (or otherwise)? (Please read original question) —The preceding unsigned comment was added by 83.100.138.99 (talk • contribs) 12:47, November 19, 2006 (UTC.

Makes sense to me. If you want to find dy/dx for the curve defined by the equation y=sin(x+y) then implicit differentiation gives you dy/dx=cos(x+y)/(1-cos(x+y)) and a little more work gives you dy/dx as a function of y alone, if you want it in that form. Try sketching the curve to see what is happening - probably easiest to use the inverse formula x=arcsin(y)-y, and take values of y from -1 to 1. Gandalf61 13:09, 19 November 2006 (UTC)

Lambian is basically just differentiation both sides of the equation wrt x. When you find an x, you just get dx/dx = 1, when you find a y just replace it by y'=dy/dx, the rest follows from the standard rules of differentiation, in particular the chain rule. This is a purely formal process, applying standard rules, so don't worry too much about the implications. In this example a lot of the complication comes from the particular example chosen, which takes some algebra to turn the formal solution y'=(1+y') cos(x+y) into a solution involving just y'. You may find it easier to consider a simpler equation say y=x. --Salix alba (talk) 13:35, 19 November 2006 (UTC)

Assuming you're the original questioner, can you say something about your background knowledge? For example, do you know and understand the chain rule? Have you read the article on implicit functions? Can you point out where it is you get stuck when trying to understand it?  --Lambiam 15:56, 19 November 2006 (UTC)

It was me who said "I can't make sense of..." - I couldn't understand what you two were doing - I added the first reply - gandalf and salix alba explained what you were up to and now it makes a bit more sense.. (No idea what happened to the original question asker)

Say if I needed to differentiate x^3+x^2+2=y^7+y+4 I would use : z=x^3+x^2+2 and find dz/dx and dz/dy. dy/dx is given by (dz/dx)/(dz/dy) That's (effectivly) the same method as you used, yes? —The preceding unsigned comment was added by 83.100.138.99 (talk • contribs) 16:26, November 19, 2006 (UTC).

Yes, if you use z=y^7+y+4 to find dz/dy, but note that this only works if you can separate the variables as in f(x)=g(y). For a case like sin(x − sin y) = cos(y + cos x) you need a more general method.  --Lambiam 18:11, 19 November 2006 (UTC)

Yes, i get (1-cos y*dy/dx)cos(x-siny)=-(dy/dx-sinx)sin(y+cosx) then rearranging..is this right? —The preceding unsigned comment was added by 83.100.138.99 (talk • contribs) 18:24, November 19, 2006 (UTC).

Looks right to me. If you read Implicit function (and understand partial derivatives), you can see how to do this so that you don't need the tedious rearranging (assuming the purpose is to bring dy/dx out). By the way, please sign your contributions using 4 tildes like this: ~~~~. Thank you.  --Lambiam 18:55, 19 November 2006 (UTC)

Seem like just using the chain rule - I probably was taught this at some point but forgot it because I never needed to use it. Thanks for bringing it up. Who knows maybe one day I will actually really use it. Thanks.83.100.138.99 19:01, 19 November 2006 (UTC)

November 19

Mathematical modelling problem

I am a landlord. I am interested in buying a house near a large organisation to rent out to that organisations personnel.

The most important number for me to try to estimate, is the likely time that the house I buy will stay empty before it is let to someone. If it is going to be too long a time, then it is not worth investing.

I have some statistics, and I would like to know if I have sufficient information to estimate this number. There are 360 households who rent houses in the surrounding area. Each household stays in the area for four years before moving on. There is a list of 40 vacant houses that new personnel coming in can choose from.

It is easy to see that there will be 360/4 = 90 new households arriving in the area every year and looking for something to rent.

But is it possible to estimate the average time that a vacant house will take to let please? There may be a simple solution that I am not quite seeing, or it may be more complex and require assumptions about the relevant probability distributions.

Would the answer in fact be 40/90 years, or slightly over five months, or have I got this wrong please?

I arrive at the same result, under the assumption that every house is rented out at least every now and then. My reasoning goes as follows: There are 360+40 = 400 houses for 360 households, so the occupancy rate is 90% and the vacancy rate is 10%. Per "turn" between one household moving in and the next, the average occupancy time is 4 years, which accounts for 90%. The vacancy time, which accounts for the remaining 10% = 10/90th of 90%, is therefore 10/90 × 4 years = 5+ months. Of course, there is no guarantee that any particular single house will see a rate anywhere near the average.  --Lambiam 16:15, November 19, 2006 (UTC)

Quartic equation

for a quadratic x^2+ax+b=0 a solution(s) is found using the substitution x=y-a/2

for a cubic x^3+ax^2+bx+c=0 solutions are found using the substitution x=y-a/3 and then y=z-a'/3z (a' is a new coefficient found in the equation in terms of y)

as I'm sure you will be aware.

My question is:

Can a quartic (x^4+ax^3+bx^2+cx+d=0) be solved by substuting x=y-a/4, then y=z-a'/4z followed by a further substitution of q = fn(z) {as yet unknown to me?} It seems likely that a cubic involving (q^4) terms would be formed just as the solution to the cubic involves a quadratic involving (z^3) terms. If so what is the substitution.. If not can anyone explain why this pattern breaks down. Thank you83.100.138.99 18:45, 19 November 2006 (UTC)

What is a'? If it is the coefficient of z^3, then a' = 0. If it is the coefficient of z^2, what good does this do? Did you study Ferrari's method (see Quartic equation)?  --Lambiam 19:03, 19 November 2006 (UTC)

As per Cubic_equation#Cardano.27s_method then a' would be p in the depressed cubic(in the wiki page it is expressed in terms of t not y. In the quartic I assumed it would be α in the depressed quartic (as shown in ferrari's method - the wikipedia page)

• Misplaced Pages Reference Desk archive