Wikipedia:Reference desk/Archives/Mathematics/2008 July 2

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.

July 2

Cube Path

Take the n-dimensional cube graph, where the vertices are labeled by ordered n-tuples of zeros and ones and two vertices are adjacent iff their labels differ in exactly one digit. How long can a simple path be, when any two vertices on the path that are adjacent in the cube are consecutive in the path? (Excluding, for instance, 00>10>11>01, because 00 and 01 are adjacent but not consecutive.) I've constructed examples with length exponential in n, of order 2^(n/2), but I'm pretty sure they can be a lot longer than that. I also checked OEIS for (1,2,4,7,12), but no luck. Black Carrot (talk)

Your graph has 2ⁿ vertices, each vertex has n neighbours, so there's 2ⁿ × n/2 = n×2ⁿ⁻¹ edges to traverse — so that's the minimum length of the path meeting conditions you gave. For n even all vertices have an even degree, so there exists an Eulerian circuit over the graph. For n odd there's no such circuit. However you can traverse your graph this way: separate two sub-graphs, corresponding to (n−1)-dimensional hypercubes; traverse one of them with an Eulerian circuit; use the n-th edge from a start vertex to get to the other sub-graph; traverse it with an Eulerian circuit; now go a Hamiltonian path for a subgraph, but make every other step in each of the two subgraphs, jumping between them with remaining 2ⁿ⁻¹ edges. This way you'll visit all edges with a path no longer than 2×((n−1)×2ⁿ⁻²)+2ⁿ⁻¹×2 = (n−1)×2ⁿ⁻¹+2ⁿ = (n+1)×2ⁿ⁻¹, which is only 1/n-th worse than the first minimum approximation. --CiaPan (talk) 13:17, 2 July 2008 (UTC)

I think you missed the adjacency restriction in the question: an Eulerian path is certainly irrelevant as it is never simple on a graph with all-even degrees. A Hamiltonian path is also irrelevant because it will necessarily contain non-consecutive adjacent vertices: the first vertex is adjacent to more than one vertex and yet is connected to only one other. (All this for $n>1$.) The only thing that comes to mind for me is that each step removes approximately n vertices from the set you can visit because you didn't choose to visit them when you could, but this is all but useless as the same vertices may be removed many times (if we extend your example to $n=3$, 000 and 110 both exclude 010 if we extend the path instead to 111). Moreover, the longest paths would presumably exploit this to exclude each excluded vertex as close to n times as possible. --Tardis (talk) 15:45, 2 July 2008 (UTC)

I had the same thought, and did manage to get an upper bound on the length of n(2^(n-1)-1)/(n-1) with a simple counting argument, which amounts to excluding about half the vertices. I found a name for the problem last night by following links. It's apparently the snake-in-the-box problem. Black Carrot (talk) 01:22, 3 July 2008 (UTC)

Sorry, I must have misread your question. I thought you want to get every pair of adjacent vertices as a 'consecutive pair' in a path, ie. visit ever edge in a graph. I missed the word 'simple' in 'simple path. --CiaPan (talk) 05:26, 3 July 2008 (UTC)

In case you're interested, I'm working on a brute force program to try to find the longest paths satisfying the above criteria. For dimensions of 2, 3, 4, 5, and 6, I get maximum path lengths of 3, 5, 8, 14, and 27, not allowing for closed paths. This is significantly below the upper limit derived above. The 7th dimension exceeds my computing capacity, but I've confirmed that paths of at least 49 exist. -- Tcncv (talk) 06:29, 3 July 2008 (UTC)

Tcncv - at first I thought your figures were off by 1, then I realised you were maybe counting vertices in the path rather than edges. Anyway, according to OEIS A099155, maximum path length (counting edges) for 7 dimensions is 50. Apparently exact maxima are not know beyond 7 dimensions, only lower bounds. Some of the references on the OEIS page about genetic algorithms may intetrest you. Gandalf61 (talk) 10:27, 3 July 2008 (UTC)

Birthday coincidences

A question I recently posed on the Miscellaneous desk threw up a comment that got me wondering. The example given was a family with 3 generations (daughter, father and grandfather) all born on 29 February. I then came up with a case of parents whose 3 children were all born on 29 February, in different leap years. Which of these 2 scenarios is more likely, and what are the chances of each? -- JackofOz (talk) 11:48, 2 July 2008 (UTC)

Are you assuming all days of a given year are equally likely, or are you basing it off a real-world distribution, like from the census? You'd also have to come up with the probability that a family would produce children at four-year intervals, rather than the more traditional two years or less. Black Carrot (talk) 12:09, 2 July 2008 (UTC)

I never got to the stage of thinking about making any assumptions. I suppose a more generally formulated question would be:

(a) What are the chances of 3 generations of a family being born on the same day of the year, and would it differ if the date was 29 February as opposed to a more frequently-occurring date?

(b) What are the chances of 3 children of the same parents being born on the same day of different years, and would it differ if the date was 29 February as opposed to a more frequently-occurring date?

My main interest is knowing which of (a) and (b) is more likely. I'm less interested in the specific numbers, but I guess if you have to work them out in order to compare them then you may as well 'fess up. -- JackofOz (talk) 12:23, 2 July 2008 (UTC)

Are you assuming the grandfather only had one child and that child only had one child? Otherwise the number of children that could possibily be produced by the multi-generational scenario would be higher and thus increase the likelihood of hitting the '3 generations with birthdays on Feb 29th' threshold.--droptone (talk) 12:32, 2 July 2008 (UTC)

Another factor that would make (b) less likely is the fact that the single family would have less time to have children compared to (a). Assuming one mother, I'd say a reasonable maximum would include 6 leap years. This would be higher for (a). For an irrelevant and unhelpful but interesting and slightly related phenomenon, see Birthday problem. Zain Ebrahim (talk) 13:15, 2 July 2008 (UTC)

The chance, that a randomly chosen date is 29 February, is a=1/(4*365+1), because there is one 29 February in four years. The chance, that three randomly chosen dates are all equal to 29 February, is a*a*a. The chance, that three random dates are equal to one another, is a*a*a+(1−a)*(1/365)*(1/365). Bo Jacoby (talk) 13:02, 2 July 2008 (UTC).

And if you're talking about a grandfather's birthday, then you may need to take into account that 1900 wasn't a leap year - i.e. in the Gregorian calendar there are 97 leap years every 400 years, i.e. the chance of a Feb 29th is 97/146097 Richard B (talk) 13:32, 2 July 2008 (UTC)

As a first approximation User:BoJacoby is right the probabilities are the same.

However I've spotted the possiblity of a 'trick question' ie twins/triplets. This would make the probability of the filial offspring being born on the same day more likely than different generations being born on the same day; all other things being equal...87.102.86.73 (talk) 13:53, 2 July 2008 (UTC)

I think Jack dealt with that with "..the same day of different years,.." in (b) above. Zain Ebrahim (talk) 13:55, 2 July 2008 (UTC)

Um yes, how silly of me.

It's possible that the birthdays of offspring of parents may cluster in certain seasons.. I don't know if the same effect applies as much between generations.. I'd imagine a trip to the science desk would be in order to find out more about that.87.102.86.73 (talk) 14:37, 2 July 2008 (UTC)

My sisters and I were all born 9 months after my parents' wedding aniversary give or take a few days. Hence it seems entirely plausible that sentimental factors can influence the likelihood of children being born during a particular time of year. Dragons flight (talk) 00:37, 3 July 2008 (UTC)

Join the club, DF. I know exactly where, exactly why, and almost exactly when I was conceived. But not exactly how  :) -- JackofOz (talk) 01:22, 3 July 2008 (UTC)

Well, JackofOz, when a Mummy and a Daddy love each other very much, ... ;) --Tango (talk) 01:26, 3 July 2008 (UTC)

Gee, I never knew that :). When I said "not exactly how", I meant "not exactly how". Think Kama Sutra and all the choices it affords. -- JackofOz (talk) 01:58, 3 July 2008 (UTC)

Word Problem

Cost for a station to test alligators in the lake for West Nile Virus. The cost for the station is $2,500 for setup costs an $3.00 to administer each test. How do I write an expression tht gives the total cost to test x animals? How do I write an expression tha gives the average cost per animal? How do I find the cost per animal for 10 animals. 100 animals. 1,000 animals? How many animals should be tested for the average cost to be $5.00 per animal? What happens to the average cost to test the animals? Would the average cost evera fall below $3.00? —Preceding unsigned comment added by 68.92.198.65 (talk) 15:16, 2 July 2008 (UTC)

From the very top of the page "Do your own homework. The reference desk will not give you answers for your homework, although we will try to help you out if there is a specific part of your homework you do not understand. Make an effort to show that you have tried solving it first."

That said, how much does it cost to test 0 alligators? How much to test 1? 2? 10? 100? x? What average do you think you need to use?... 86.130.120.230 (talk) —Preceding comment was added at 15:27, 2 July 2008 (UTC)

The article on total cost might be a good place to start. --Prestidigitator (talk) 19:51, 2 July 2008 (UTC)

The article on linear equation may be of help too.--droptone (talk) 19:58, 2 July 2008 (UTC)

How many can be administered in one test? Assuming its 1, look at the linear equation link--68.231.202.21 (talk) 20:50, 2 July 2008 (UTC)

I suggest you go and speak to your teacher. This is a pretty simple example of that type of question so if you can't do it, it suggests you haven't been taught how (at least, not successfully), so you need to go back and learn how to turn such descriptions into equations. --Tango (talk) 22:54, 2 July 2008 (UTC)

Re suggestion "go and speak to your teacher": I don't read this question as being definitely a school question. The wording "How do I write an expression..." does slightly suggest this, but it's by no means certain, and it could well be the questioner is looking at the economic feasibility of setting up such a testing station. On that basis I'll go ahead and answer it.

1. Total cost to test x animals: (2500 + 3x).

2. Average cost per animal: (2500 + 3x)/x.

3. Cost per animal for 10 animals: replace "x" with 10 in expression "2" above: (2500 + 3*10)/10 = $253.00.

4. Cost per animal for 100 animals. 1,000 animals: use "3" above as an example.

5. How many animals for $5.00 average cost: solve equation "5 = (2500 + 3x)/x" to get x = 1,250 gators.

6. Average cost goes down the more gators that are tested.

7. Would the average cost ever fall below $3.00? No, impossible if it always costs $3.00 to test one animal.

On a general note, there are a whole lot more costs that should be taken into consideration. Also, where does that $3.00 come from? Is it necessarily a fixed cost?--217.171.129.73 (talk) 12:21, 3 July 2008 (UTC)

I suggest that any diseased gators be "retired", and their skins sold to pay for the testing. StuRat (talk) 04:24, 3 July 2008 (UTC)

To 217.171.129.73, who conjectures the original poster to be actually an alligator tester: the title "Word problem" strongly reeks of homework, in my opinion... Nevertheless, no harm done, I believe. Original poster, is the problem clearer now? Goochelaar (talk) 13:42, 3 July 2008 (UTC)

First timer anons with homework questions almost never come back :( -hydnjo talk 16:17, 3 July 2008 (UTC)

OK, I see your point.--92.40.205.184 (talk) (formerly 217.171.129.73) 17:51, 3 July 2008 (UTC)