Wikipedia:Reference desk/Archives/Mathematics/2012 June 17

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.

June 17

Logic operator name and usage

Resolved

I've been reasing Rosen's Discrete Mathematics and its Applications (7th ed.), and so far going well.

Unfortunately, I've got to the section on "Applications of Satisfiablity", and he uses the following notation:

$\bigwedge _{i=1}^{9}\bigwedge _{n=1}^{9}\bigvee _{j=1}^{9}p(i,j,n)$

Basically, he is talking about a Sudoku puzzle. To encode the Sudoku puzzle, he lets $p(i,j,n)$ denote the proposition that is true with the number n is i the ith row and the jth column.

So what he says he's doing is that he's asserting that for every row of a normal Sudoku puzzle (9 cells), that every row contains every number from 1 to 9. Which he says is:

$\bigwedge _{i=1}^{9}\bigwedge _{n=1}^{9}\bigvee _{j=1}^{9}p(i,j,n)$

Now earlier in the text he says that $\bigwedge _{j=1}^{n}$ can be used as shorthand for $p_{1}\land p_{2}\land \cdots \land p_{n}$, and $\bigvee _{j=1}^{n}$ can be used as shorthand for $p_{1}\lor p_{2}\lor \cdots \lor p_{n}$. However, what does it mean when you have $\bigwedge _{i=1}^{9}\bigwedge _{n=1}^{9}\bigvee _{j=1}^{9}p(i,j,n)$?

Furthermore, what are the names for the symbols $\bigwedge _{j=1}^{n}$ and $\bigvee _{j=1}^{n}$?

I've looked everywhere, including the logical conjunction and logical disjunction pages, but can't find any reference to this!

Any help would be greatly appreciated :-) - Letsbefiends (talk) 08:05, 17 June 2012 (UTC)

I don't know whether the "bigwedge" and "bigvee" symbols have formal names. But we can unpack the meaning of the compound expression as follows. Starting with

$\bigvee _{j=1}^{9}p(i,j,n)$

which says one or more of p(i,1,n) ... p(i,9,n) is true i.e. the number n occurs at least once in row i. Then we have

$\bigwedge _{n=1}^{9}\left(\bigvee _{j=1}^{9}p(i,j,n)\right)$

where I have inserted brackets to make the order of operations clearer. This says that

$\bigvee _{j=1}^{9}p(i,j,n)$

is true for all values of n from 1 to 9 i.e. each number 1 to 9 occurs at least once in row i. Since row i only has 9 cells, this also means that each number 1 to 9 occurs exactly once in row i. And finally we have

$\bigwedge _{i=1}^{9}\left(\bigwedge _{n=1}^{9}\left(\bigvee _{j=1}^{9}p(i,j,n)\right)\right)$

which says that

$\bigwedge _{n=1}^{9}\left(\bigvee _{j=1}^{9}p(i,j,n)\right)$

is true for all values of i from 1 to 9 i.e. each number 1 to 9 occurs exactly once in each row. The convenience of the notation becomes obvious when you realise that if you wrote this out explicitly as a logical expression in p(1,1,1), p(1,1,2) etc. then it would involve 9³ = 729 terms. Gandalf61 (talk) 08:46, 17 June 2012 (UTC)

Ahhhh! Thanks Gandalf61! I wrote something below that didn't make sense... have scratched it. But I see what you are saying! A great help :-) Letsbefiends (talk) 10:46, 17 June 2012 (UTC)

Modified Monty Hall -- paradox?

Resolved

Suppose one has 2 players in the same Monty Hall problem with 5 doors. Guy A picks door 1 and Guy B picks door 5. Doors 2, 3 and 4 are opened -- and it ends up that each guy ought to switch to the other guys' door. Even though the initial Monty Hall problem isn't a true paradox, doesn't this constitute a paradox? DRosenbach ^{(Talk | Contribs)} 22:12, 17 June 2012 (UTC)

How is it determined which doors are opened in your scenario? What would have been opened if the prize had been behind one of door 2, 3, 4? Can the two constestants pick the same door and still get a full prize each if the prize is there? PrimeHunter (talk) 23:19, 17 June 2012 (UTC)

Alright -- I see the error in this set up, because it's possible that neither of them picked the money and there's not 3 goat doors to open up. Thanx! DRosenbach ^{(Talk | Contribs)} 01:34, 18 June 2012 (UTC)

There is a related and fundamental difference between the original Monty Hall -- paradox and your set up. In the original setting, the programme leader knows where the money (or the car) is, and chooses the door to open based on that knowledge. Recall, that if this were not the case, but the opened door just accidentally happened to hide a goat, then there would have been a 50-50 % chance for the money being behind one of the closed doors. JoergenB (talk) 15:57, 18 June 2012 (UTC)

That's not the difference -- my set up is such that there is no difference other than 2 contestants instead of 1 and 5 doors instead of 3. But the problem with my set up, that I've just come to discover, is that it's possible that both people choose doors with goats, in which case it would be impossible for 3 other doors to be opened. DRosenbach ^{(Talk | Contribs)} 23:28, 18 June 2012 (UTC)

So don't open 3 doors, open 2 and leave Guy A, Guy B and one other closed? -- SGBailey (talk) 09:10, 19 June 2012 (UTC)

I guess the scenario is: Monty knows where the car is. The contestants know which door the other contestant chose, and they know that Monty will always open two of the 3 unchosen doors, and never one with the car. In this scenario there is no advantage to switching to the door of the other contestant. They knew in advance that this door would not be opened so it still has 1/5 chance of the car; same as their own door. It is the 1/5 chance of each of the 3 unchosen doors which is merged into 3/5 chance of the unchosen door Monty doesn't open. So both contestants should switch to that door if they are allowed, even if it means they have to share the car (assuming a share is worth half a car to them). If we allow scenarios where the contestants don't know which door the other contestant chose, or don't even know there is another contestant, then it's possible to get a situation where it's advantageous, from their respective points of view, to switch to the other contestant's door. This is not a paradox. It is just a case of making different but rational choices due to having different information. PrimeHunter (talk) 11:21, 19 June 2012 (UTC)

Alright -- thanx! DRosenbach ^{(Talk | Contribs)} 12:17, 19 June 2012 (UTC)

Uniform distribution

A is a discrete uniform random variable. B is the sum of A choices from a second discrete random variable (there are a*b possible values for B where a and b are the possible values from A and the second distribution). Is there a name for distribution B? Here's a picture with (1,4) and (1,6): http://i.imgur.com/QNQzp.png 70.162.10.166 (talk) 23:52, 17 June 2012 (UTC) Alternatively is there a name for this operation in general? 70.162.10.166 (talk) 00:32, 18 June 2012 (UTC)

I don't think so, but if you divide by A you have the sample mean with a randomly sized sample. It's not clear to me why that would be useful. Looie496 (talk) 18:08, 18 June 2012 (UTC)