EPTand a hint at the solution for #3 would be
(Possibilities of mixing A,C,D,Es )* (Possibilities of distributing 3 Bs in between 8 other letters)
Where the latter part works exactly the same as in #2
The Math Thread - Page 20
| Forum Index > General Forum |
|
Kleinmuuhg
Vanuatu4091 Posts
and a hint at the solution for #3 would be (Possibilities of mixing A,C,D,Es )* (Possibilities of distributing 3 Bs in between 8 other letters) Where the latter part works exactly the same as in #2 | ||
|
enigmaticcam
United States280 Posts
On July 17 2018 04:24 Kleinmuuhg wrote: Edit: Okay Im not typing this, sorry. Hope you can read my scribbling  Not sure why our results are different for 3.If you have any questions, please ask and I can elaborate more if needed. Oh btw, I wanted to say thanks again for this. It helped me solve a few more problems so I think I finally have a good understanding of it. | ||
|
Kleinmuuhg
Vanuatu4091 Posts
On September 08 2018 07:20 enigmaticcam wrote: Oh btw, I wanted to say thanks again for this. It helped me solve a few more problems so I think I finally have a good understanding of it. Very glad to hear | ||
|
Deleted User 3420
24492 Posts
Had to use purely math by the way. No computers lol for #1, I think all of you were right about your criticisms. for #2, I couldn't use dynamic programming! but klein, your way of thinking about it is brilliant. It's kind of how I approached it, but I ended up doing it.. a little wrong. I didn't conceptualize it as clearly as you did. for #3, does anyone have a mathematical explanation? I did it wrong anyways, I saw Acrofales post and have a lot of faith in him so I approached it like that even though my brain was telling me the problem was different. I was low in time, lol. I am a bit behind in my classes I am going to have to stop focusing on side projects or im gonna get creamed in midterms. | ||
|
raNazUra
United States10 Posts
On September 09 2018 11:26 travis wrote: Alright, it's been a bit but im back. I imagine I did quite poorly on the homework since I did not know how to do these. Had to use purely math by the way. No computers lol for #1, I think all of you were right about your criticisms. for #2, I couldn't use dynamic programming! but klein, your way of thinking about it is brilliant. It's kind of how I approached it, but I ended up doing it.. a little wrong. I didn't conceptualize it as clearly as you did. for #3, does anyone have a mathematical explanation? I did it wrong anyways, I saw Acrofales post and have a lot of faith in him so I approached it like that even though my brain was telling me the problem was different. I was low in time, lol. I am a bit behind in my classes I am going to have to stop focusing on side projects or im gonna get creamed in midterms. For #3 I'd definitely recommend looking at Klein's hint above. Basically, the recommendation is to count the number of possible words by saying: "When generating a word, I will first choose the positions of the Bs, and then I will choose the order of the remaining letters and fill them into the open spaces". The important things you have to ask when doing a constructive argument like this are: - Am I not overgenerating? That is, can I generate the same word twice in two different ways and thereby end up counting it twice? - Am I not undergenerating? That is, are there some valid words that my method won't generate, and thus won't be counted? - In this case, where there's multiple steps, are the steps independent? If not, you can't multiply them together to get the final count. If you can convince yourself of these three things, then it simply becomes (number of ways to place the Bs) * (orderings of the remaining letters) The first is an identical problem to #2, and the second is a more straightforward calculation. + Show Spoiler + If I'm not too rusty, it should be (8 choose 4) * (4 choose 2) * (2 choose 1) | ||
|
Day_Walker
104 Posts
If you get stuck, here's the mathematical solution I wrote up for #2 and #3. Before jumping into the details of the problems, let me go over the "stars and bars" idea. Imagine I have 3 stars * and 2 buckets [], and I want to count how many ways I can put the stars in the buckets. Our example is tiny, so we can just draw pictures of all the possiblities: [***] [] [**] [*] [*] [**] [] [***] Now the key idea is to ignore the buckets themselves, and focus on the divisions between the buckets, which we can draw with a bar |. Using bars instead of buckets, our pictures look like this: ***| **|* *|** |*** 2 buckets means 1 division/bar, and we still have the 3 stars, so there are (3+1) choose 1 possibilities. If we change the scenario to have 3 buckets, then there will be 2 divisions/bars. Now our pictures look like *|*|* or *||** or |***|, and there are (3+2) choose 2 possibilites. In general if we have N stars and M buckets, then our pictures will have N stars and M-1 bars, and there are (N+M-1) choose (M-1) of these. (Equivalently, N+M-1 choose N.) ------------------------------------ OK, now let's use this idea for problem #2: We know the string will have 4 ones, and then we can imagine 5 "buckets" where we can put the 11 zeroes: [ ] 1 [ ] 1 [ ] 1 [ ] 1 [ ] <--- 11x 0s need to go in To avoid consecutive ones, it is necessary and sufficient to put a zero in each of the middle 3 buckets: [ ] 1 [0] 1 [0] 1 [0] 1 [ ] <--- 8x 0s need to go in The remaining 0s can go into the buckets without any restrictions. We just need to count the number of ways to distribute 8 things in 5 buckets. Using our result above, there are 12 choose 4 = 495 possibilities. For example, one possiblity for putting in the 8x 0s is 00||0|00|000, which produces 001010010001000 when combined with the 1s and 0s we already placed. So, there are 495 of these binary strings. ------------------------------------ On to problem #3: First let's just worry about consecutive Bs, and ignore the distinction between A, C, D, E by saying we just have 8 other undetermined ? letters for now. So we have 3x Bs and 8x ?s, and we can apply the method from problem #2: [ ] B [?] B [?] B [ ] <--- 6x ?s need to go in There are (6+3) choose 3 = 84 possiblities. Now for each of the 84 possibilities, we need to turn the 8 ?s into ACDEs. For example, ??B??B??B?? could turn into AABAABCCBDE. There are 8! ways to do this ignoring duplicates, which we can account for by dividing out 4! * 2! * 1! * 1! (because of 4 As, 2 Cs, 1 D, 1 E). So we get 840 distinct words from each of the 84 possiblities. One last thing, we need to ask ourselves if 2 different possibilities could produce the same word. For example if B?B?B?????? can turn into the same word as ??B??B??B??, then we need to worry about overcounting. But that can't happen, because the Bs are in different positions. So the final count is just 84 * 840 = 70560 words. | ||
|
Deleted User 3420
24492 Posts
In the mean time I have another question, it's very specific and it's not actually for school. I really should be able to solve this... but I have so much going on in my brain lol and I think this should be very simple for some of you. I have a system of equalities: First, I will say that In this system, I know the actual value of A,B,C,D,E,F. I want to solve for G,H,I,J,K,L. I know that there *is* a solution of whole numbers. And I know the following. A = G+H B = I+J C = K+L D = G+H+I+J+K+L E = G+I+K F = H+J+L So, if I know the integer values of ABCDEF, is it possible to solve for GHIJKL? | ||
|
Acrofales
Spain17979 Posts
On September 11 2018 07:54 travis wrote: Wow, thank you, that is fantastic. I'll need to practice this, I'll probably end up coming back with a couple more combinatorics questions. In the mean time I have another question, it's very specific and it's not actually for school. I really should be able to solve this... but I have so much going on in my brain lol and I think this should be very simple for some of you. I have a system of equalities: First, I will say that In this system, I know the actual value of A,B,C,D,E,F. I want to solve for G,H,I,J,K,L. I know that there *is* a solution of whole numbers. And I know the following. A = G+H B = I+J C = K+L D = G+H+I+J+K+L E = G+I+K F = H+J+L So, if I know the integer values of ABCDEF, is it possible to solve for GHIJKL? Clearly doesn't work for arbitrary values. So first check that D=E + F and D= A + B + C. If that's the case, then I'm not sure there is a unique solution, but it's just linear algebra. Write it as a matrix and solve using Gaussian elimination. | ||
|
Simberto
Germany11505 Posts
I have come to the conclusion that this system does not have a unique solution. For there to be a solution, it is necessary that D = E+F and D = A+B+C. If that is not the case, there is no solution. And if D = E + F, then equation 4 is superfluous and does not add any additional information to the set of equations 1,2,3,5,6, which means that you don't have a set of 6 equations to solve for 6 variables, which means that the system does not have a unique solution. There seems to be another superfluous equation, since you can easily get a solution by choosing, for example, G=I=0 (Other choices are also valid, and G doesn't have to be equal to I, this is just the laziest solution i came up with) The solution in that case is, G=0 H=A I=0 J=B K=E L=F-A-B. So your solution has two degrees of freedom due to not having enough equations. | ||
|
mahrgell
Germany3943 Posts
On September 11 2018 21:02 Simberto wrote: Firstly, Acrophales is correct. I have come to the conclusion that this system does not have a unique solution. For there to be a solution, it is necessary that D = E+F and D = A+B+C. If that is not the case, there is no solution. And if D = E + F, then equation 4 is superfluous and does not add any additional information to the set of equations 1,2,3,5,6, which means that you don't have a set of 6 equations to solve for 6 variables, which means that the system does not have a unique solution. There seems to be another superfluous equation, since you can easily get a solution by choosing, for example, G=I=0 (Other choices are also valid, and G doesn't have to be equal to I, this is just the laziest solution i came up with) The solution in that case is, G=0 H=A I=0 J=B K=E L=F-A-B. So your solution has two degrees of freedom due to not having enough equations. As the conditions D = E+F and D = A+B+C have to be enforced on the input, it is easier to get the 2 superfluous equations by keeping the equation for D and considering one (any) of the first 3 and one (any) of the last two equations to be superfluous. But of course the problem is much easier to solve (as you did) by only removing the D equation, setting G and I to arbitrary values and then the remaining variables are a simple elimination without any need of equation transformation. | ||
|
Deleted User 3420
24492 Posts
2<=a<=15 0<=b<=20 0<=c<=25 1<=d<=25 It says to find the number of integer solutions using the exclusion/inclusion principle. I am... confused. The answer I found is 5502, but I did not find it with exclusion/inclusion principle. I am not sure how to apply exclusion/inclusion here. | ||
|
Simberto
Germany11505 Posts
and another set as all elements of (a,b,c,d) of N^4 where the set of inequalities is true. Both of those should be easy to count, and if you also get the number of elements in the union of the sets somehow, you can use inclusion-exclusion to get the number of elements in the intersection. That is the only way i see to apply inclusion-exclusion here. Maybe the number of elements in the union is easier to find than the number of elements in the intersection? | ||
|
Deleted User 3420
24492 Posts
On September 24 2018 05:11 Simberto wrote: You could use one set as all elements (a,b,c,d) of N^4 where a+b+c+d = 40 what do you mean by N^4? edit: are you, (or my instructor), saying to essentially find 1.) all a+b+c+d and then exclude all a+b+c+d != 40 ? | ||
|
Simberto
Germany11505 Posts
(1,4,291,11) So basically, you have a set out of sets of 4 numbers. I don't know if this actually makes the thing easier to solve though. Edit to your edit: I was suggesting finding all a, b, c, d with a+b+c+d = 40 (or rather the amount of such things) And the amount of abcd which satisfies the second set of inequalities And the amount of stuff in the union of those sets. Then you can use inclusion exclusion to find the amount of stuff in the intersection of those sets. | ||
|
mahrgell
Germany3943 Posts
so a being in N, b being in N, etc... | ||
|
Deleted User 3420
24492 Posts
| ||
|
Simberto
Germany11505 Posts
(Basically, it is a fancy way of saying "find out how many numbersets of 4 integers which satisfy a+b+c+d=40 exist") Edit: I have something else i want to write, but people are replying to quickly. Edit2: If you want to use inclusion exclusion, you need (at least) two sets which partially overlap. I see the two sets of "4 integers with a+b+c+d = 40" and "4 integers with the other 4 inequalities") which do partially overlap. The cardinality of each of those sets should be easy to find, so if you could also find the cardinality of the union of the sets, inclusion/exclusion would deliver to you the cardinality of the intersection, which is what you were asking for originally. However, i don't see a very obvious way to finding that cardinality of the union, which might mean that this is not the best path either. I don't see another way how inclusion/exclusion would be useful for this, though. | ||
|
Deleted User 3420
24492 Posts
then find the cardinality, for each singleton a,b,c,or d - where they are not within the constraints then the pairs then the triplets then use exlusion/inclusion to remove the cardinality of sets that broke the constraints? | ||
|
Kleinmuuhg
Vanuatu4091 Posts
| ||
|
Kleinmuuhg
Vanuatu4091 Posts
On September 24 2018 13:03 travis wrote: so what im gonna do is, count the cardinality of the set of all a+b+c+d=40 Infinitely large set as well, you will not get anywhere using that set Im a bit busy rn. I will try to think about it and give a more productive answer if possible but I thought I'd spare you that wrong approach | ||
| ||
