Wikipedia:Reference desk/Archives/Mathematics/2011 February 27

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.

February 27

Combinatorics/probability question

We have $N$ objects, each labeled with a natural number between $1$ and $S$. There are $N_{1}$ 1s, $N_{2}$ 2s, ..., and so on. We choose a permutation of the objects uniformly at random to get a string of $N$ labels. What is the expected number of times that differing labels appear consecutively?

I ran some simulations and it became clear that the answer for $S=2$ is $2{\frac {N_{1}N_{2}}{N}}$, or $2N{\frac {N_{1}}{N}}{\frac {N_{2}}{N}}$, but I don't really understand why, and more importantly for me, I don't know how to generalize to $S>2$. Any ideas?

Thanks — Rotcaeroib (talk) 00:50, 27 February 2011 (UTC)

Consider special (and limiting) cases before the general case. Let N be a big number. The label i occurs with probability N_i/N. A pair of consecutive i 's occurs with probability (N_i/N)². A pair of consecutive identical labels occurs with probability Σ(N_i/N)². The expected number of pairs of consecutive identical labels is approximately (N−1)Σ(N_i/N)². Then consider the special cases N=0 and N=1 and N=2. Now the problem is surrounded! Bo Jacoby (talk) 08:37, 27 February 2011 (UTC).

Thank you very much. That's a very clean line of reasoning to the approximation, and good hints. I ran out of time that my wife would allow me to spend before I got very far deductively, but I did discover that your approximate solution can be made to match my exact solution for $S=2$ by replacing $N-1$ with $N$, suggesting a candidate general exact solution (for the number of consecutive differing labels): $N\left(1.0-\sum _{i}\left({\frac {N_{i}}{N}}\right)^{2}\right)$. This matches the results of my simulations to great precision for a wide variety of inputs, so I'm reasonably convinced that it's right, and sure that my immediate engineering need is satisfied. I'm still working on a derivation just out of interest. Thank you again. Rotcaeroib (talk) 01:17, 28 February 2011 (UTC)

I checked you formula for the 11 cases N=1,2,3,4, and it reproduces the values exactly! For example N=4, N₁=2, N₂=N₃=1. The 12 arrangements 1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211 contain a total of 30 consecutive different labels, and 30/12 = 2.5. The formula gives 4(1−(2/4)²−(1/4)²−(1/4)²) = 4(1−(1/4)−(1/16)−(1/16)) = 2.5. Still we need a proof. Bo Jacoby (talk) 11:20, 4 March 2011 (UTC).

Bridge card hand: binary encoding problem

Hi all, I could use some help with interpreting a question on a lecture course on data coding i'm attending.

Q: In Bridge, a 52 card pack is dealt to provide 4 hands of 13 cards each. If the contents of a hand are conveyed by one player to their partner by a series of nods and shakes of the head, how many movements of the head are required? Show that at least 40 movements are required. Give a simple code requiring 52 movements.

I am assuming a 'nod' and a 'shake' each correspond to exactly 1 distinct movement, i.e. we're encoding into binary. I'm aware that the number of points in a bridge hand is out of 40 but i don't think we're meant to know that for this question, so to the best of my knowledge, the 'contents of a hand' is presumably the suit and value of each card in the hand: but I'm struggling to show at least 40 movements are required.

I tried looking at injectivity; if we have 52 possible cards, then there are either 52^13 or (52*51*...40) possible hands, depending on how crudely we calculate this. I wanted to argue something like that 2^39 < 52^13 or 52*51*...40 and 2^40 is greater than it; equivalently (in base 2) 39 < 13 log(52) or 39 < $\sum _{i=40}^{52}\log(i)$, but by this argument I calculate the RHS to be approximately 70, in which case the '40' estimate is obviously way off, but since 52 is possible this argument is clearly false. Where am i going wrong? How do I obtain 40? 131.111.185.68 (talk) 05:11, 27 February 2011 (UTC)

The order in which you are dealt the 13 cards doesn't matter. See Combination. PrimeHunter (talk) 05:21, 27 February 2011 (UTC)

Of course, how stupid of me :) Thankyou! 131.111.185.68 (talk) 06:17, 27 February 2011 (UTC)

The different bridge hands, from all spades to all clubs, can be indexed from 1 to 635013559600, or, in binary, from 0000000000000000000000000000000000000001 to 1001001111011001110000011111010100110000. The binary index of any hand can be transmitted by 40 movements of the head. I wonder if there exists a smart conversion algorithm between the index and the bridge hand? Bo Jacoby (talk) 03:04, 28 February 2011 (UTC).

The above analysis (52 choose 13 is between 2^39 and 2^40) seems to be ignoring the fact that your partner has some information about your hand, since they get to see 13 cards they know you don't have. If you knew which 13 they had, this would reduce to 39 choose 13, but of course you don't. Is there a way to take advantage of their information to reduce the number of bits needed?--130.195.2.100 (talk) 03:15, 28 February 2011 (UTC)

That's an interesting question. If there were only nine cards overall and you and your partner got four each, how much information would they have to give you about their hand for you to determine the card that neither of you have? I don't see any way of saving them some effort. And yet if there wasn't that extra card they wouldn't have to tell you anything for you to know everything in their hand. Dmcq (talk) 16:41, 28 February 2011 (UTC)

I don't think so: your message can't depend on their hand, and for any two of your hand's possibilities there is a hand that they could have in either case, so every pair of your hands must have distinct messages. If you and your partner were each dealt more than a third of the cards, you could start to rule out possibilities. For example, if 5 cards are dealt two to me, two to you, and one aside, the messages for my hand being AB and CD need not be distinct because there's no hand you could have that wouldn't rule one out. We can then send 3 bits to pick from {AB/CD, AC/BE, AD/CE, AE/BD, BC/DE} rather than 4 to pick from the list of 10 hands. --Tardis (talk) 16:45, 28 February 2011 (UTC)

That's very good, thanks. So with five cards overall, two cards each and one card left out that does give a very worthwhile saving. Dmcq (talk) 16:56, 28 February 2011 (UTC)

That number is of course 52*51*50*…*40; an algorithm (and an encoding) based on that is:

def pick_hand(deck,idx): # deck holds the 52 card objects; idx is the 40-bit number
  deck=deck[:] # local copy to destroy
  hand=[]
  for i in range(13):
    digit,idx=idx%(52-i),idx/(52-i)
    hand.append(cards[digit])
    del cards[digit]
  return hand

I don't know if you can avoid the $O(Nn)$ behavior of the del. --Tardis (talk) 16:45, 28 February 2011 (UTC)

Interesting Integrals

I was wondering if you guys know of any interesting examples of integrals that I can give my calculus students. So single integrals, something which can be solved with calc 1 and calc 2 methods. The problem is when I give them something for practice, they can just plug them into mathematica, wolfram alpha, or its online integrator and copy even the steps. So I am looking for something which these dumb programs can't solve and requires "intelligence" and "ingenuity" which machines can't replicate. Something which will force the students to think. Something with perhaps an elegant solution and requires thinking out of the box. Two of my favorite examples are

$\int _{0}^{1}{\frac {1}{Floor(1/x)}}dx$

and

$\int _{0}^{1}{\frac {1}{x}}-Floor(1/x)dx$.

Anything more I can add to the list? Thanks!!!!-Looking for Wisdom and Insight! (talk) 09:25, 27 February 2011 (UTC)

Are you sure you want this problem solved? The modern way of calculating integrals is to plug them into intelligent programs like wolfram alpha. Don't teach your students difficult, insecure and slow methods when easy, reliable and fast methods are around. Bo Jacoby (talk) 07:58, 27 February 2011 (UTC).

I am afraid I disagree with that. I want them to think. I don't want them to be lazy and reach for their calculators to tell me what sixteen times two is. In addition, (so far) programs can't solve all of the problems that we can (like the examples I gave above). I want them to understand what is it that goes on in background and once they have mastered the concepts then they can let machines do the tedious work while they solve bigger problems like integrating something in the middle of solving a PDE.-Looking for Wisdom and Insight! (talk) 09:25, 27 February 2011 (UTC)

I would be careful with fancy terms like "intelligence" and "ingenuity" which machines can't replicate. It took me just 5 minutes to write the following Mathematica function, which integrates any function of the form $f(x)=g(x,\lfloor h(x)\rfloor )$:

FloorIntegral[g_, h_, a_, b_] := 
 Sum[Integrate[g[x, k] Boole[k <= h[x] < k + 1], {x, a, b}], {k, -\[Infinity], \[Infinity]}]

It eats up your two examples, and probably other similar ones:

FloorIntegral[(1/#2) &, (1/#) &, 0, 1]
FloorIntegral[(1/#1 - #2) &, (1/#) &, 0, 1]

Gives ${\frac {\pi ^{2}}{6}}-1,\ 1-\gamma$, respectively. It is just a matter of time until Wolfram implements a more advanced version of this, which doesn't require a special syntax, handles multiple floors and edge cases, is more efficient and so on.

If you argue that this just handles floors, and different examples can be found, such examples will also fall into some pattern which can and eventually will be programmed. And that's even without anything advanced in the form of algorithms to deal with a wide variety of cases without a hardcoded pattern for each.

That said, I agree completely that the students should learn how to do these things themselves if they are to have a real understanding. But you need to find a way to achieve this that doesn't depend on average college students being able to outsmart world-class technical software. -- Meni Rosenfeld (talk) 09:46, 27 February 2011 (UTC)

Meni, it wasn't the machine which actually "solved" the problem. You still had to intervene and the machine did exactly what you told it to do. I agree that machines are excellent at following orders (and they can do them fast too). I use Mathematica and MATLAB myself on a daily basis. If a student does this then this doesn't mean that they have mastered calculus. This just shows that they can code in Mathematica. The point was to stop the kids from running to the nearest computer and letting them know that its okay to think and take more than a few minutes to solve a problem. I know I can test them with proofs or something but what if I just want them to practice. Most of them just go home and abuse this resource. Anyway, my goal wasn't for a discussion of pedagogy here. If nothing else, then just for fun, does anyone know any such interesting integrals? Something that challenges conventional thinking taught in calculus classrooms? Something for which our cookbook procedures taught in calc books today fail spectacularly? Like the first integral has to be thought of geometrically and then it is just the area of a bunch of squares added up.-Looking for Wisdom and Insight! (talk) 10:16, 27 February 2011 (UTC)

You've missed my point, despite the efforts I made to clarify it. It's not that I was able to write a program that does the integral. It's that it's an accident that this functionality isn't built-in already. If one year from now your students will go to Mathematica and type Integrate[1/Floor[1/x], {x, 0, 1}] they will get the answer, and likewise for any other example. The other point, which I won't go much into, is that I don't think the borders between "intelligence" and "mechanically following orders" are as clear-cut as you present them.

Anyway, for your original request - maybe something like the Sophomore's dream? Some guidance will probably be required. -- Meni Rosenfeld (talk) 10:28, 27 February 2011 (UTC)

To me the purpose of intelligence is to solve problems, but to the OP the purpose of problems is to develop intelligence. It is not intelligent to do impressive and useless stuff like memorizing 100 digits of pi, or to integrate by hand. Why doesn't the OP want students to be lazy? The lazy solution is the intelligent solution! After they have learned to let machines do some tedious work they will eventually master the concepts. Bo Jacoby (talk) 12:16, 27 February 2011 (UTC).

[ec] First learn how to do integrals by hand, then learn how to not do them by hand.

Mathematics is not a spectators sport, if you want to understand something (and I suppose we agree that people should understand integrals) you have to do some hands-on exercises with it.

To use an analogy, people go to the gym to do the seemingly pointless activity of lifting weights up and right back down where they started. It would be much easier to use a forklift or not do it at all. There is no use in this, except for the fact that your muscles are trained by the experience.

And this is even without delving into the useful vs. beautiful issue. What the OP asked for are integrals whose solutions are beautiful. -- Meni Rosenfeld (talk) 12:33, 27 February 2011 (UTC)

I very rarely comment on editors on these desks, but I must just say that the responses to this question have probably been of the worst I've seen. The OP in good faith is looking for insightful examples which will teach his students to think about integration and really try to understand what they're doing. To come in and start berating him for this is extremely unhelpful and comes across as quite rude. If instead of "integration" and "calculus" the OP had said "multiplication" and "mental arithmetic" would we have told him to stop wasting his school pupil's time and allow them to mindlessly use calculators? Is it wrong to force students to think carefully about problems rather than run to the nearest computer? Zunaid 12:37, 27 February 2011 (UTC)

The OP is looking for examples that aren't handled by Mathematica yet rather than exercises that will help them learn straightforward techniques. They also asked that they be pretty. You can't optimise two disparate things at the same time you have to do a trade off. Ugly exercises I consider as going to the gym, and I go dancing which is fun and social rather than going to a gym. If they don't do the work they'll fail their exam anyway and I'd try and get them to like it, they can always copy the answers for exercises from someone who actually does the work. Dmcq (talk) 12:53, 27 February 2011 (UTC)

I am sorry to hear that you feel that the responses by Bo and myself are bad. It should be noted that our responses are very different and I am puzzled by your inclusion of both in the same criticism. As you have not made a distinction, I will regard the criticism as directed to my own responses and attempt to justify myself accordingly.

• The OP did indeed ask in good faith for insightful examples. Although belatedly, I did offer such an example.
• I did not berate the OP. I did inform him that I find a premise of his query flawed, which is germane to our ability to answer it. The OP originally asked specifically for exercises which would not be solvable by modern computer algebra systems, and I wished him to know that I find this search futile.
• The OP has also made implications about the nature of CASes in general and the limits of automated computation. While off topic, I found it productive, for the benefit of the OP and readers, to voice some reservations about the ideas presented.
• Based on my feedback, the OP has refocused his question, which I find conducive to our ability to answer it.
• I find it beneficial for respondents to have some leeway in broadening the scope of an OP's verbatim query in order to help him in unexpected ways. I think that one of the pillars of asking questions the smart way is to focus on the problem, not on a particular solution which may or may not be the way to solve it. The OP did later express his disinterest in such broadening, which I find unfortunate, though should be respected.
• Some of my comments were really directed at Bo, in a discussion about one of the OP's premises (that students should be encouraged to develop a better understanding and an ability to work on problems themselves). Once again, this discussion was only tangentially related by I still found it important. For what it's worth, in these comments I have defended the OP's position.

-- Meni Rosenfeld (talk) 13:35, 27 February 2011 (UTC)

As a general rule, computer algebra systems have difficulty with integrals requiring you to exploit some kind of symmetry. This is especially true for integrals in dimension greater than one, and it used to be true for one-dimensional integrals as well, but the systems have gotten more crafty in recent years. Anyway, here's at least one integral that mathematica couldn't evaluate, even though it requires only a moment's thought for a human being:

$\int _{-1}^{1}x^{3}\left(\int _{0}^{|x|}e^{\sin ^{2}t}\,dt\right)\,dx.$

You could try some variation on this theme. Sławomir Biały (talk) 14:37, 27 February 2011 (UTC)

This reminded me of an important integral with an elegant solution, $\int _{-\infty }^{\infty }e^{-x^{2}}\ dx$. -- Meni Rosenfeld (talk) 15:07, 27 February 2011 (UTC)

You might find the following online reference desk to be helpful.

• Math Forum: Teacher2Teacher (T2T) ("Welcome to Teacher2Teacher, a resource for teachers and parents who have questions about teaching mathematics.")

—Wavelength (talk) 16:54, 27 February 2011 (UTC)

I think that the only way to make sure that your students are thinking and solving the problems by hand, independently, is to check their solutions. Tell them that they will only receive marks for their working and and explanation and that no marks will be awarded for simply having the correct answer. It means a lot more work for you, but it will get you closer to your goal. — Fly by Night (talk) 23:23, 27 February 2011 (UTC)

WolframAlpha shows how the integration is done. Taemyr (talk) 23:48, 27 February 2011 (UTC)

I've just asked WolframAlpha to find

$\int e^{x}\sin x\,\operatorname {d} x\,.$

Asking it to show the steps it uses the "step" that

$\int e^{ax}\sin(bx)\,\operatorname {d} x={\frac {e^{ax}\left(a\sin(bx)-b\cos(bx)\right)}{a^{2}+b^{2}}}\,.$

So, one of the steps to solving the integral was to instantly solve a more general integral. That wouldn't convince any teacher that that was done by hand. The usual method would be to apply integration by parts twice. — Fly by Night (talk) 00:35, 28 February 2011 (UTC)

I agree. I've done a bit of marking before, and you can easily tell if someone understands what they are doing or if they are just applying things learned by rote (such as that standard formula WolframAlpha used, but no human would bother memorising) or just using a computer. One clue is the notation they use - humans tend to use more elegant notation than computers. --Tango (talk) 00:50, 28 February 2011 (UTC)

"humans tend to use more elegant notation than computers": You've obviously never had to teach calculus at a US university.  :-P Sławomir Biały (talk) 13:57, 28 February 2011 (UTC)

I said humans, not Americans! ;) --Tango (talk) 20:05, 28 February 2011 (UTC)

Try to be more sensitive! There might even be some Americans reading in this discussion. Those that can read, at any rate. :-P Sławomir Biały (talk) 21:11, 28 February 2011 (UTC)

How about the following? $\int _{0}^{\pi /2}\arccos(\cos(x)/(1+2\cos(x))dx=5\pi ^{2}/24$. Maple and Maxima can't do it, I'd be interested to hear if any other programs can (especially Mathematica). I'm not sure if it can be done using elementary methods though. Tinfoilcat (talk) 00:44, 28 February 2011 (UTC)

Another difficult integral: $\int _{0}^{({\sqrt {5}}-1)/2}\log(1-x)/x+\log x/(1-x)dx=-\pi ^{2}/5$. Good sources are Coxeter's work on polytopes (where both of my examples are from), and Hardy's book Integration of Functions of a Single Variable (I've not seen this, but I'm sure it will have many interesting and tricky integrals). Tinfoilcat (talk) 00:54, 28 February 2011 (UTC)

But how solvable are these for a first year calculus student? The OP was asking for integrals that required intelligence, originality, but relatively basic calculus. — Fly by Night (talk) 01:00, 28 February 2011 (UTC)

Mathematica can do the second, but not the first. -- Meni Rosenfeld (talk) 07:18, 28 February 2011 (UTC)

Thanks for checking Meni. @FBN, you're right that these are not examples that address the OP's question - you couldn't give them to 1st yr calc students and expect them to solve them. Indeed I doubt there are any real examples of functions that can be integrated by first years but not by good software. However I wanted to address Bo's claim that integration by hand wasn't "impressive" (I'd be impressed by a hand evaluation of those two) [edit: misread this], and also to attempt to find examples where CASs fail. Those integrals were just the first couple I came across: I'm sure with some research one could discover a lot more that mathematica would struggle with. I do think this sort of example could be useful to the OP though - he can use them to prove that there are still integration problems only humans can do. Tinfoilcat (talk) 11:32, 28 February 2011 (UTC)

I too find integration by hand impressive. My point is that by now it has moved from the realm of craftmanship into the realm of sports. It is still impressive but no longer competitive. See John Henry (folklore) for an example of man-machine competition. I think the teacher should encourage the students to explore the capabilities of the machine, rather than search for problems that still must be done by hand. Bo Jacoby (talk) 12:54, 28 February 2011 (UTC).

Misread you, sorry, corrected. Tinfoilcat (talk) 17:04, 28 February 2011 (UTC)

The students can be encouraged to use old-fashioned "intelligence" and "ingenuity" and to "think outside the box", if their instructor "thinks outside the box" and requires that the students solve the assigned questions in the classroom, under old-fashioned supervision by the instructor. No assigned question is carried forward to the next day. (How many students are in the class, or in each class? You might need to hire a teacher's assistant.)

—Wavelength (talk) 02:36, 28 February 2011 (UTC)

I know the so-called "Harvard calculus" (Hughes-Hallet, Gleason, et al) is perhaps the least liked calculus textbook by real mathematicians, as it epitomizes the "reform calculus" approach. In spite of this, I have found that the exercises challenge students because they require students to understand what they are doing, not merely to perform some task such as computing an integral. Many of the exercises are really quite ingenious in how they achieve this. I strongly recommend that the original poster check this book out. (However, I have only taught multivariable calculus from this textbook. It might have earned its bad reputation from the earlier chapters, I don't know.) Sławomir Biały (talk) 13:57, 28 February 2011 (UTC)

Similarly to what Wavelength said, I assign homework weekly but I never collect it. I am not worried about the online calculators. I did it because they can download the full instructor's solutions manual from the internet if they look around. A year ago when I taught Calculus, I caught 9 students (out of 40) cheating on one assignment. I warned the whole class that any one cheating would be turned in to the dean of students for cheating and I still caught 2 of those cheating again another student cheating. So 25% of my students (those are the only ones I caught) were copying answers out of the instructor's solutions manual. I once heard someone say they do not give points for anything unless they witness the students doing the work themselves. Even if you assign homework that you make up, it could be done by their friends or an online calculator or their mom or whatever. So, I assign homework from the book and do weekly quizzes that covers the homework. This ensures they keep up with the work. StatisticsMan (talk) 16:11, 28 February 2011 (UTC)

Start with something routine like

$\int {\frac {x}{x^{2}-6x+13}}\,dx,$

and then instead of asking them to evaluate the integral, lay out all the steps explicitly before them, taking even routine algebra at a leisurely pace, and then ask them particular questions about each step. Michael Hardy (talk) 18:09, 28 February 2011 (UTC)

When I took the Cambridge Entrance Exam (in 1971), one of the questions was, in full:

Evaluate the indefinite integral $\int {\frac {px+q}{rx^{2}+2sx+t}}\,dx$, where $p,q,r,s,t$ are real constants.

It might seem quite a daunting prospect to identify and solve all the possible cases, but as far as I remember it turned out to be not too bad - mainly a question of keeping one's nerve. AndrewWTaylor (talk) 21:40, 28 February 2011 (UTC)

See here Count Iblis (talk) 22:37, 28 February 2011 (UTC)

A problem I like is to determine $\int {\frac {x^{6}}{(1+x)^{8}}}\,dx$ as the neat solution found manually using $u=1+{\frac {1}{x}}$ or x = tan²θ is not the same as Wolfram gives. EdChem (talk) 17:59, 2 March 2011 (UTC)