I gotta tell you though! my solve was more optimized for speed and made less verifications ;) :p :D
Printable View
I gotta tell you though! my solve was more optimized for speed and made less verifications ;) :p :D
Okay, I have one problem question and one general question.
Problem
We make strings with only the characters '0' and '1'. How many strings of length N can we make if we additionally require that we can never have any adjacent '0's.
ie. 11011110 is a legitimate string of length 8
and 0001 is not allowed.
General
I'm curious what type of problems everyone is interested in. Some problems have been the classic word problems that require some logical and arithmetic insight, while a few others have been more calculational. In particular, I have a bunch of problems that others might find interesting, but looking through them I see that many of them are proofs or problems in specialized domains (combinatorics, group theory, number theory, topology, series manipulation, etc.). Proofs seem like they may cause a problem, since there is likely differing opinions on what constitutes a proof, but they can be quite interesting to work out as well. The specialized domains could probably be handled by given specific definitions that are required for the solution, but this may take away some of the insight of trying to work it out. So I am a little stumped. In particular, I'd probably like to post a few series manipulation problems if people were interested, since I particularly love manipulating the little things, but then the questions would probably be something like "prove" or "what are the series of steps" to show a particular identity (which has the problem of proofs in a way, unless a collection of atomic manipulations were agreed on) or they would be something like "calculate" a particular sum (which could leave open the use of Mathematica and its ilk).
So basically, my second question is: what type of problems do all of you enjoy most?
well
let a(n) = the number of such sequences of length n.
a(1) = 2
a(2) = 3
a(n) = a(n-1) + a(n-2)
The Fibonacci Sequence
Yep! Your turn.
(though I'd like to know your reasoning if you cared to share... not necessary, just curious which direction you took) :)
Hi Galathaea,
I have seen this question as homework in many text books, but have never bothered to solve it. Like any honest person I was trying to guess at a general formula and prove it by induction. Needless to say I could not come up with a general formula, that would be quite an accomplishment (Is that a solution which is worth quite a bit of money?). The question I ended up asking myself was: "How do I build sequences of length n with no adjacent zeros from sequences of length n-1 with no adjacent zeros". The answer was I can add a 1 to every sequence of length n-1 and I can add a 0 to all the sequences of length n-1 which end in 1. It is easy to see by this same reasonong that the number of sequences of length n-1 which end in 1 is the number of sequences of length n-2. I then recognized the Fibonacci sequence.
I am having troublr thinking of a good problem. Here is one
Problem:
You have 9 brass rings, three of which are gold. can you find the three gold rings using a balance scale three times?
Number of possible ways to have 3 gold and 6 brass rings:Quote:
Originally posted by souldog
You have 9 brass rings, three of which are gold. can you find the three gold rings using a balance scale three times?
9!/(3!6!)=84
Number of possible data to aquire from scale:
3^3=27
84>27
So I say it is impossible.
[edit: "3^3=81" changed to "3^3=27," thank you souldog for pointing that out. But my answer still holds ;)]
Also, it is impossible to have brass rings which are gold ;).Quote:
Originally posted by souldog
You have 9 brass rings, three of which are gold. can you find the three gold rings using a balance scale three times?
Yes, it is not possible.
Note: 3^3=27 not 81.
There is not a one-to-one correspondance between the possible outcomes of the weighings and the number of possibilities for the three gold rings. So more than one configuration for the three gold rings will lead to the same result in three weighings.
YOur turn
I say brass rings can be gold. Just my opinion.
Maybe you can look at the rings and separate out the gold-colored rings from the brassy-colored rings, and then use the scale to weigh three pouches of diamonds that a black-market dealer is exchanging for the rings. But you have to make sure that you leave real quickly, before the dealer scratches off the gold paint and discovers that the ring is really brass...
I'm not sure how general you mean here. There is a simple function for the Fibonacci sequence that gives the function explicitly (its 1/sqrt(5)*(((sqrt(5)+1)/2)^n - ((sqrt(5)-1)/2)^n) or something like that where you differ powers of the roots of the characteristic) instead of just defining it recursively. But if you meant sequence problems in general, then I was actually thinking of a solution method that does generalize this somewhat. I was thinking of the use of generating functions and the 4 foundational theorems of combinatorial enumeration. In particular, this problem is a simple use of the composition theorem and the fact that there exists an isomorphism from the composition of the collection of sequences I specified and the collection of sequences of zeroes to the collection of all sequences of ones and zeroes. You get the generating function right away, and similar methods work for all kinds of sequence problems (as well as enumerating all kinds of cool other combinatorial structures).Quote:
Originally posted by souldog
Needless to say I could not come up with a general formula, that would be quite an accomplishment (Is that a solution which is worth quite a bit of money?).
I take it you did not like my problem. I did not like it either.
I had fogotton that there was a general formula for the Fibonnaci sequence. It has been a while. Although I have had to teach basic finite combinatorics a few times, I am no expert and so did not use any theorems. In fact I work in servohydraulic control now and so am kind of out of the loop as far as theoretical mathematics goes. It seemed more expediant to just solve the problem at hand. Please show the solution using the theory.
souldog: pm me the solution and I will come up with a combination of rings for which it will not work.
I didn't mind it. I was trying to figure out if there was some trick way to solve the problem, because it wasn't solvable through the standard way as Solarflare has pointed out. But I hadn't noticed the gold / brass thing that Solarflare posted about, or that the question was not to solve but whether one could solve. So I just posted my $m@rt@$$ response on color as a joke... not unhappy with it...Quote:
Originally posted by souldog
I take it you did not like my problem. I did not like it either.
Well, just to add to my previous post, here is the basic outline:Quote:
Originally posted by souldog
Please show the solution using the theory.
- First, you start with two-dimensional generating functions, so you can keep track of the number of 0's and 1's separately. For ease of putting them on the boards, I will call them F[{0,1}*](x, y), F[S](x, y), and F[0{0}*](x, y) for the generating functions of all sequences of 1's and 0's, the sequences I am enumerating, and the sequences of 0's only (at least one 0) -- with x being the zeroes and y the ones.
- Combinatorial composition is the replacement of certain combinatorial subobjects in one collection with elements of another collection, and the composition theorem (commonly just referred to as a lemma, since its pretty straightforward to prove) is that the combinatorial composition generating function is the functional composition.
- So for this problem, it is easy to see that replacing any zero in our collection with a member of the collection of zero sequences will give any member of the collection of all sequences of 0s and 1s, and conversely that this is uniquely done. So we get the generating function equation: F[{0,1}*](x, y) = F[S](F[0{0}*](x, y), y).
- Now the generating function for the two sequences we are not solving for can be taken as known or solved for immediately using the combinatorial sum and product theorems. Without going into the details, I will just say that F[{0,1}*](x, y) = (1 - x - y)^(-1) and F[0{0}*](x, y) = x (1 - x)^(-1).
- This gives (1 - x - y)^(-1) = F[S](x (1 - x)^(-1), y). You then use the substitution u = x (1 - x)^(-1) to get the nice form F[S](u, y) = {1 - u (1 + u)^(-1) - y}^(-1).
- And finally, to get the generating function for sequence of length n regardless of the number of 0s and 1s, you just set the two arguments equal and the convolution sums the various terms nicely for you. In other words, you get F[S](x, x) = (1 + x) (1 - x - x^2)^(-1), which is the generating function for the Fibonacci sequence, starting at Fibonacci(2) instead of (1). You can see this by multiplying the denominator over and solving it as a series problem, from which you get the recurrence relationships.
However, it is obvious that your solution is much more straightforward for the problem. This is just the way I was thinking of because I was trying to come up with a combinatorial problem that might present some insight to the general way of solving these things and actually gave a problem with several different ways of attack specific to the question. Another method I thought of after I posted the question was to divide the sequence into two subsequences, both of which must also obey the problem. Counting out the places where you can divide up the sequence and using the fact that the split point must not combine two different sequences the first of which ends on zero and the other that begins, you get a relationship that also solves to Fibonacci fairly quickly. But I think I like your solution best...
There is no solution. You were right. Why don't you ask another question so this keeps going.Quote:
Originally posted by solarflare
souldog: pm me the solution and I will come up with a combination of rings for which it will not work.
I guess SolarFlare is not going to ask a question so I will.
Be warned. I do not know the answer to this question. I do not know if there is an answer, i.e. if the solution can be found with standard algebraic techniques.
Problem: (working in 3 dimensions) Six vectors are are attached to six distinct points in the XY-plane (if you like put them on the vertices of a hexagon centered at the origin). They all have a positive (>0) z-coordinate. The other end of the six vectors (call it the free end) are coplanar. If all you know is the lengths of the six vectors, find the equation of the plane determined by the free ends. Restrict the lengths of the vectors to be in some range, say between 8 and 10. The distance between the free ends of any two of the vectors is constant.
The distance between the free ends of any two of the vectors is constant