| Forum Index > General Forum |
|
Kleinmuuhg
Vanuatu4091 Posts
On September 24 2018 05:31 Simberto wrote: The cardinality of the whole N^4 is infinite. But the cardinality of N^4 which also satisfy a+b+c+d=40 is not. This set might be a good idea but it is so huge I don't feel that way. Edit: Not a good idea, see longer explanation below. | ||
The_Templar
your Country52797 Posts
On September 24 2018 04:47 travis wrote: I have an inclusion/exclusion principle question. I have been given a formula a+b+c+d = 40 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. First, you should reduce the problem to a+b+c+d =37 with 0 ≤ a ≤ 13, 0 ≤ b ≤ 20, 0 ≤ c ≤ 25, and 0 ≤ d ≤ 24, which is functionally the same thing. Assuming you know how to find the number of solutions to a+b+c+d = 37 with no restrictions, you can use exclusion/inclusion to subtract the cases where a > 13, b > 20, c > 25, d > 24. | ||
|
Acrofales
Spain18093 Posts
On September 25 2018 00:53 Kleinmuuhg wrote: This set might be a good idea but it is so huge I don't feel that way. I dunno. It doesn't seem so bad. The solution can be found in a similar way to the earlier problems, by seeing it as ways of placing 3 blue cars in between 40 red cars (thereby dividing the space up into 4 sets of red cars that sum to 40). There are 43!/(40!3!) = 12341 ways of doing that. Imho the problem is that I agree with simberto that I don't see a way of using inclusion exclusion, because I can't find an easy way of calculating the union of that set and the set with the individual constraints. | ||
|
Kleinmuuhg
Vanuatu4091 Posts
On September 25 2018 01:27 Acrofales wrote: I dunno. It doesn't seem so bad. The solution can be found in a similar way to the earlier problems, by seeing it as ways of placing 3 blue cars in between 40 red cars (thereby dividing the space up into 4 sets of red cars that sum to 40). There are 43!/(40!3!) = 12341 ways of doing that. Thanks for using my car example :D but I am afraid in this case that will not yield the correct result. Best seen by the fact that an integer can be used more than once (drawing with putting back) On September 25 2018 01:24 The_Templar wrote: IMO everyone is way overcomplicating this problem. First, you should reduce the problem to a+b+c+d =37 with 0 ≤ a ≤ 13, 0 ≤ b ≤ 20, 0 ≤ c ≤ 25, and 0 ≤ d ≤ 24, which is functionally the same thing. Assuming you know how to find the number of solutions to a+b+c+d = 37 with no restrictions, you can use exclusion/inclusion to subtract the cases where a > 13, b > 20, c > 25, d > 24. Reducing is an elegant idea I like it. The second part of your answer however is not how Inclusion - Exclusion works. Without going into math details, let me try to explain: You dont count good cases and bad cases and then substract the bad cases. You count different combinations of sets of good cases and then substract the number of good cases you counted more than once. Imagine you have you want to count fruit you bought but you are a bit of a dimwit so you only know that you bought 8 apples (A) and you bought 7 green fruit (B) and that you have 3 green Apples (A ∩ B) . Then the total number of fruit is 8+7-3=12. You count all apples and all green fruit, but then you counted the green apples twice, hence you substract that number. Obviously if you have more than 2 sets (which might be the case here  ) then you count some stuff thrice etc.. formulas for those cases are very intuitive and can be found everywhere (wikipedia eg).What does this mean for our case here? We dont want to count cases that are not valid solutions to our equation (and substract them later or sth. like that; This can work to get to a solution but its not inclusion-exclusion) Hence counting all solutions to a+b+c+d=40 or 37 is not the way to go. And just after writing all of this I realize that I am dumb and tired. I'd delete it but I will let it stand as a warning to all others. Im going to bed good night. sorry ;D | ||
|
Melliflue
United Kingdom1389 Posts
Let S = set of solutions for a+b+c+d=37 A= solutions with a<=13 B = solutions with b<=20 C = solutions with c<=25 D = solutions with d<=24 then you are looking for the intersection of A,B,C,D. The number of solutions that satisfy all of those inequalities is |S| - those which fail at least one; |AnBnCnD| = |S| - |S\A u S\B u S\C u S\D| You can use inclusion-exclusion principle on |S\A u S\B u S\C u S\D| because the intersections are small and often empty (for example, (S\A)n(S\C) requires both a>13 and c>25 but then a+b+c+d>38 which is not possible). So mainly you need to know |S\A| etc and the condition a>=14 can be reduced to a+b+c+d=23, with a,b,c,d>=0. Side note: + Show Spoiler + On September 24 2018 05:24 Simberto wrote: 4 dimensional space with integers as elements in each dimension. An element might look like this (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. This is an aside, but why do you call N^4 a space? It is not a vector space (because there are no additive inverses) and it is not interesting as a topological space unless you give it a weird topology, and there is no obvious metric to make it a metric space, and even if you do give it a topology I don't see how that would in any way help. This also means that 'dimension' is not well-defined. I don't find it helpful here to talk about spaces or dimension. | ||
|
Acrofales
Spain18093 Posts
On September 25 2018 02:44 Melliflue wrote: I think The_Templar is on the right lines. Let S = set of solutions for a+b+c+d=37 A= solutions with a<=13 B = solutions with b<=20 C = solutions with c<=25 D = solutions with d<=24 then you are looking for the intersection of A,B,C,D. The number of solutions that satisfy all of those inequalities is |S| - those which fail at least one; |AnBnCnD| = |S| - |S\A u S\B u S\C u S\D| You can use inclusion-exclusion principle on |S\A u S\B u S\C u S\D| because the intersections are small and often empty (for example, (S\A)n(S\C) requires both a>13 and c>25 but then a+b+c+d>38 which is not possible). So mainly you need to know |S\A| etc and the condition a>=14 can be reduced to a+b+c+d=23, with a,b,c,d>=0. Side note: + Show Spoiler + On September 24 2018 05:24 Simberto wrote: 4 dimensional space with integers as elements in each dimension. An element might look like this (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. This is an aside, but why do you call N^4 a space? It is not a vector space (because there are no additive inverses) and it is not interesting as a topological space unless you give it a weird topology, and there is no obvious metric to make it a metric space, and even if you do give it a topology I don't see how that would in any way help. This also means that 'dimension' is not well-defined. I don't find it helpful here to talk about spaces or dimension. Yeah, that is smart. Hadn't thought of it that way. Furthermore, you can do inclusion-exclusion for the union too: |S\A u S\B| = |S\A| + |S\B| - |S\A n S\B| and in addition to S\A n S\B being a fairly small set, you can simply repeat Templar's initial trick in reducing the problem again here. Neat! Oh, and as you pointed out, any intersection of more than 2 is empty, so only need to worry about the pairwise factors. Otherwise you'd still have quite a lot of work to do. | ||
|
Deleted User 3420
24492 Posts
I was wondering if the following is the case for a hamiltonian graph. Let's say we have a hamiltonian graph. Somehow, we just know it is. It has N nodes, and each node has a random amount of edges between 3 and n/2. I do believe, and I think I remember having done it before, that I can systematically remove edges until every node has the same degree, simply by examining the count of how many times each node is in an edge, and removing the edges that are out of balance. My question is - does doing this ever remove hamiltonicity of the graph, or is it always safe to do this when investigating hamiltonicity? | ||
|
mahrgell
Germany3943 Posts
On September 26 2018 04:17 travis wrote: Pushing this thread along, one question at a time. Thank you everyone for your contributions to my education. I have a graph theory question... not sure if this is in anyone's realm of knowledge here. I was wondering if the following is the case for a hamiltonian graph. Let's say we have a hamiltonian graph. Somehow, we just know it is. It has N nodes, and each node has a random amount of edges between 3 and n/2. I do believe, and I think I remember having done it before, that I can systematically remove edges until every node has the same degree, simply by examining the count of how many times each node is in an edge, and removing the edges that are out of balance. My question is - does doing this ever remove hamiltonicity of the graph, or is it always safe to do this when investigating hamiltonicity? In short: it ain't safe. Simply assume 8 nodes, split in 2 groups of 4 nodes, all connected to each other. Then add 2 edges between the 2 groups so that the graph becomes hamiltonian. You could/would now remove the 2 connecting edges, thus leading to two isolated clusters. | ||
|
Deleted User 3420
24492 Posts
so I suppose my question should be, is it impossible to guarantee the existence of edges that are safe to remove? | ||
|
Acrofales
Spain18093 Posts
E: nvm. I misread. Deleted this paragraph. Rest is ok. | ||
|
mahrgell
Germany3943 Posts
On September 26 2018 06:29 travis wrote: that's true, but there's 2 edges we can remove in that graph that *are* safe, too. so I suppose my question should be, is it impossible to guarantee the existence of edges that are safe to remove? See Acros post: if you reduce the graph down to the hamilton ring, thus every node having 2 edges, you always have a perfect solution But if you want to enforce the 3+ edges condition on the the new graph, it is easy to create a counter example. e.g. ![[image loading]](https://i.imgur.com/pUjPW67.png) Here you are absolutely forced to remove the connections between the 2 clusters, if you want to keep every node at 3+ edges. edit: of course the left cluster is fully connected... blegh... forgot to put those in. | ||
|
Deleted User 3420
24492 Posts
edit2: wow, fantastic. nice construction it perfectly illustrates that this isn't the case | ||
|
Geiko
France1939 Posts
There is a room with 8 levers numbered 1-8 which are in a random (unknown) initial position. The guard is going to tell you a number between 1 and 8, then you're going to go in the room, look at the levers, move one and only one lever, and then leave the room. Then your friend goes in the room and he has to guess the number that the guard gave you. You can discuss strategy with your friend before the game starts. What is the strategy to be 100% sure that your friend will find the right number ? If I remember well, the answer had to do with logical gate XOR, but I can't figure it out anymore :'( | ||
|
Ciaus_Dronu
South Africa1848 Posts
On October 18 2018 21:44 Geiko wrote: Hey guys I need your help, I used to know the answer to a math puzzle but I can't seem to figure it out anymore... There is a room with 8 levers numbered 1-8 which are in a random (unknown) initial position. The guard is going to tell you a number between 1 and 8, then you're going to go in the room, look at the levers, move one and only one lever, and then leave the room. Then your friend goes in the room and he has to guess the number that the guard gave you. You can discuss strategy with your friend before the game starts. What is the strategy to be 100% sure that your friend will find the right number ? If I remember well, the answer had to do with logical gate XOR, but I can't figure it out anymore :'( Question about this, are you *forced* to move a lever? Can you just leave the levers alone? My current approach is to try find a nice partition of a hypercube (totally equivalent to binary strings of certain length differing at one digit, which is in turn totally equivalent to on/off levers of which you flip one) which might make the answer fall out (the answer will be in the form of "you can find a partition of all possible arrangements of levers into 8 classes such that you can always take a starting configuration, flip one lever, and wind up in any class of your choosing). EDIT: nvm I think it doesn't matter if you are forced to move one. | ||
|
Geiko
France1939 Posts
On October 18 2018 23:12 Ciaus_Dronu wrote: Question about this, are you *forced* to move a lever? Can you just leave the levers alone? My current approach is to try find a nice partition of a hypercube (totally equivalent to binary strings of certain length differing at one digit, which is in turn totally equivalent to on/off levers of which you flip one) which might make the answer fall out (the answer will be in the form of "you can find a partition of all possible arrangements of levers into 8 classes such that you can always take a starting configuration, flip one lever, and wind up in any class of your choosing). EDIT: nvm I think it doesn't matter if you are forced to move one. Yes you are forced, but like you said, it basically doesn't matter because if you find the correct method, there will always be a lever that won't change the class of the lever configuration. The problem is finding a smart way to partition the 8 dimension hypercube. The answer was fairly elegant and simple if that helps... | ||
|
opisska
Poland8852 Posts
| ||
|
Geiko
France1939 Posts
On October 19 2018 00:01 opisska wrote: Number the levers 1-8 and make number so that you add the lever's number if it's ON, then modulo 8 and +1 to get a number from 1-8. Switching a single lever can change this number by any amount. Was my first guess too but it doesn't work... Let's say you enter the room and the configuration is 1:ON 2-8:OFF and you want to make your friend guess the number 2. There's no lever that can make the sum = 2 [8]. | ||
|
opisska
Poland8852 Posts
On October 19 2018 00:10 Geiko wrote: Was my first guess too but it doesn't work... Let's say you enter the room and the configuration is 1:ON 2-8:OFF and you want to make your friend guess the number 2. There's no lever that can make the sum = 2 [8]. That's why it's modulo 8 and then +1, but the switches are numbered 1-8 not 0-7. Thus the sum is already 2. If you are forced to move a lever, you can always move the last one which has no effect (equals to 8). edit: To elaborate, if you were able to not act at all, you would have 9 options, but you need only 8, so you can have that taken away, but you need to basically have one option equal to "it's already good" and that's the last lever with value 8 edit2: I am dumb, it would work exactly as well with switches numbered 0-7, only the first one would do nothing. Getting into the "modulo something" thinking is always hard  | ||
|
Geiko
France1939 Posts
On October 19 2018 00:14 opisska wrote: That's why it's modulo 8 and then +1, but the switches are numbered 1-8 not 0-7. Thus the sum is already 2. If you are forced to move a lever, you can always move the last one which has no effect (equals to 8). To elaborate, if you were able to not act at all, you would have 9 options, but you need only 8, so you can have that taken away, but you need to basically have one option equal to "it's already good" and that's the last lever with value 8. The problem with your method is that not all options are possible. If the configuration is 1:OFF, 7:ON 2:OFF, 6:ON 3.OFF, 5.ON 4:OFF The sum is 5+6+7=2[8] if you switch lever 1: sum=3[8] if you switch lever 2: sum=4[8] if you switch lever 3: sum=5[8] if you switch lever 4: sum=6[8] if you switch lever 5: sum=5[8] if you switch lever 6: sum=4[8] if you switch lever 7: sum=3[8] if you switch lever 8: sum=2[8] you'll notice there is no way to obtain sum=1[8] or sum=7[8] or sum=0[8] If you needed to make any of these numbers, the method doesn't work. | ||
|
opisska
Poland8852 Posts
On October 19 2018 00:32 Geiko wrote: The problem with your method is that not all options are possible. If the configuration is 1:OFF, 7:ON 2:OFF, 6:ON 3.OFF, 5.ON 4:OFF The sum is 5+6+7=2[8] if you switch lever 1: sum=3[8] if you switch lever 2: sum=4[8] if you switch lever 3: sum=5[8] if you switch lever 4: sum=6[8] if you switch lever 5: sum=5[8] if you switch lever 6: sum=4[8] if you switch lever 7: sum=3[8] if you switch lever 8: sum=2[8] you'll notice there is no way to obtain sum=1[8] or sum=7[8] or sum=0[8] If you needed to make any of these numbers, the method doesn't work. Okay, fuck me, I am dumb! I see the problem now, can't see how I did not see it at first. Long time since I did a puzzle like this the last time ... | ||
| ||
StarCraft 2 StarCraft: Brood War Dota 2 League of Legends Counter-Strike Super Smash Bros Heroes of the Storm Other Games Organizations Other Games Counter-Strike Other Games StarCraft 2 StarCraft: Brood War |
|
Wardi Open
Wardi Open
PiGosaur Monday
Replay Cast
Tenacious Turtle Tussle
The PondCast
OSC
WardiTV Invitational
Online Event
RSL Revival
[ Show More ] |
|
|
EPT
