Logic Puzzles

[chaos_defrost]

Wow, are you serious, hahahaha

A. It is the only square.
B: It is the only red shape.
C: (see previous statements)
D: It is the only "small" shape.

My answer is A. "Large" and "small" are subjective terms. To a red-green colorblind person, all of B-D can possibly be described as a "brown-ish circle" when weighed independently.

True or false: This is a true statement.  http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" />

[Zaphod77]

True or false: This is a true statement.  http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" />

yes. http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

the statement is true or false. whichever it is, there is no contradiction.  without more knowledge, we can't tell.

as for the previous, the question implies that among any possible grouping of three and one, only one of the groupings has a shared characteristic between three that is not shared with the fourth. following from this, the only such characteristic is presence or lack of a unique characteristic.  c is the one that lacks a unique characteristic.

and i got the color card problem right first try.

[Proxima]

I disagree -- the statement is neither true nor false. Raymond Smullyan explained that in order for a statement to be true or false, we must understand what it would mean for it to be true, i.e. what the statement is claiming. "Apples grow on trees" is true because we know what apples are, what trees are and what "to grow" means, and putting these together makes a true claim about the world. We cannot understand what it would mean for "This statement is true" to be true because we would first have to know what it means for "This statement is true" to be true.

[chaos_defrost]

While pondering what went wrong with my life to this point, I remembered a corporate presentation given the day before my failed actuarial internship started:

Imagine an equilateral triangle inscribed in a circle. Randomly and independently generate two points on the circle, so all points on the circle are equally likely. What is the probability that the chord connecting the points is longer than a side of the triangle?

A) 1/2
B) 1/3
c) 1/4

This was an hour lecture about how "any of these can possibly be correct, it's a matter of perspective blah blah corpospeak syergisticising" ... I remember thinking how "no, only one of those can possibly follow the assumptions of independence and uniform distribution about the circle."

Re-thinking about it, I am almost certain that one of these answers is right. Which means this flawed logic is vastly preferred in the corporate world to my abilities.

Please vindicate my life  http://www.lemmingsforums.com/Smileys/lemmings/sad.gif" alt=":(" title="Sad" class="smiley" />

[Clam]

1/3.

• The longer the arc length between two points, the longer the chord, i.e. they are equivalent in terms of ordering. [The formula is c = 2r sin(θ/2) which is increasing for θ between 0° and 180°.]
• The arc length between points on the triangle is 120°
• The arc length between the two random points is uniform between 0° and 180°
• The probability that this length is between 120° and 180° is (180-120)/180 = 1/3.

[Simon]

1/3, yes.

In 1/3 of the cases, when you rotate the triangle to match its corner to either point, the other point falls in between the two opposing corners. Then use Clam's argument for arc length ordering == chord length ordering.

I'm somewhat interested in irrational conviction systems. Can you elaborate on the corporate rigmarole?

-- Simon

[chaos_defrost]

Yea, that's what I got, using Simon's method. Place point A, without loss of generality align the triangle so a vertex is at the point, chord is longer iff the second point falls in the arc corresponding to the opposite side, which happens 1/3rd the time.

I can't remember the other arguments. I think the 1/4 one had to do with the locus of possible chord midpoints to make the longer chord (which is I think a circle of half the radius, correct me if I'm wrong but you do get 1/4 if this is the case), which is flawed because the distribution of midpoints is not uniform.

I think the goal of this presentation was to show "there's different correct ways to look at a problem" -- by using flawed probability. Did I mention the interns this was for were studying to be ACTUARIES? You know, where the "easiest" test is entirely about probability? Company proceeded to lose 90% of its stock that year probably because of thinking like this. *shrug*

[Proxima]

Wow, that's hilarious. I assume the intention was to ask "given a fixed circle, what is the probability that a randomly chosen chord is longer than the side of the inscribed equilateral triangle?" This is ambiguous because "a randomly chosen chord" is not rigorously defined. One method of random choice is to choose two points on the circumference and connect them. Another, as you mentioned, is to choose a single point in the interior (all points being equally likely) and generate the chord of which that point is the midpoint (this is always unique unless the interior point is the exact centre). Using this method, the probability is 1/4 because success occurs in exactly those cases when the point falls within a circle of the same centre and half the radius. Yet another method is to choose a bearing at random, then choose at random a line with that bearing that crosses the circle; with this method the probability is 1/2.

By wording the question so as to eliminate this ambiguity, they undermined the whole point of asking the question in the first place  http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />

[geoo]

I just stumbled across this cute theorem:

Imagine an arbitrary minesweeper board A, and its inverse B that has a mine in a cell iff it doesn't have a mine in the corresponding cell in A. Now imagine both boards are completely solved with the according numbers in the non-mine cells. Then the sum of all the numbers in A equals the sum of all the numbers in B.
Example:

Code Select Expand


111 ***
1*1 *8*
111 ***    8x1 = 1x8

Code Select Expand


**100 24***
34321 *****
*2**1 3*44*    3x1 + 2x2 + 2x3 + 4 = 17 = 2 + 3 + 3x4


Prove this theorem. The proof is a nice and intuitive counting argument.


Here's another one, which is a lot harder (haven't solved it) and is apparently inspired by the dwarfs with hats problem that needs the axiom of choice:

There is a countably infinite number of boxes in a room, each containing a real number.
There are 100 prisoners who can discuss a strategy beforehand, but once the game has started they cannot share any information.
In some order (not sure if the prisoners know the order beforehand, let's assume yes) they are lead into the box room, one by one. In there they can open as many boxes as they want (countably many is allowed, but not all), and then they have to pick one unopened box and predict the number in that box.
After a prisoner leaves the box room, all boxes are closed again and then the next one enters.
If 99 of the prisoners predict correctly, they are released. Find a successful strategy.

<SimonN> and the prediction must be the exact real, no margin of error or anything
<geoo> yes
<SimonN> geoo: is it legal for two boxes to have the same real?
<geoo> not sure, let's assume no to ensure it's solvable
<SimonN> hmm, and countably many == countably infitiely many, or (finitely many or countably infinitely many)? Are the boxes labelled?
<geoo> the boxes are ordered and will not be rearranged at any point in the game
<geoo> countable can mean both finite and countably infinite

[Proxima]

Prove this theorem. The proof is a nice and intuitive counting argument.

Spoiler

A pair of touching boxes adds 1 to the total if and only if exactly one box of the pair is a mine. This is invariant under the switching operation.

[Simon]

These questions are about a shuffled deck of finitely-many playing cards. Each card in the deck is either red or black. We don't necessarily assume that there are equally many reds as there are blacks. The physical order of cards inside the shuffled deck is linear.

A "block" is a largest-possible contiguous set of equally-colored cards in the deck. For example, if the red/black cards come up (red, red, black, black, black, red, black, red, red, ...), we have a block of 2 red cards, then a block of 3 black cards, then a block of 1 red card, and so on.

1. You could determine the number of blocks by looking at each card in sequence, comparing it against the previous card. Can you design an algorithm to determine number of blocks such that, at least with high likelyhood, the algorithm need not examine every card?

2. Now we're only interested in whether the number of blocks is even or odd. What's the most efficient algorithm?

Both were solved by Proxima in IRC, but I found it interesting enough to give everyone a try. :-)

-- Simon

[NaOH]

This was posed by a friend of mine this morning:

We have 30 chocolate-chip cookies in 5 cookie boxes. The cookies have different numbers of chocolate chips on them (not necessarily unique). This is the distribution:

A: 0, 10, 10, 10, 10, 10
B: 2, 2, 12, 12, 12, 12
C: 4, 4, 4, 14, 14, 14
D: 6, 6, 6, 6, 16, 16
E: 8, 8, 8, 8, 8, 18

This distribution has the curious property that if you pick a cookie from A and from B, odds are that the cookie from B has more chocolate chips. This is true for B and C, D and E, E and A as well. (https://en.wikipedia.org/wiki/Nontransitive_dice)

How many cookies can we eat and preserve this property?

Edit: I can eat 19 (so long as they're vegetarian). Can you eat more?

[mobius]

These questions are about a shuffled deck of finitely-many playing cards. Each card in the deck is either red or black. We don't necessarily assume that there are equally many reds as there are blacks. The physical order of cards inside the shuffled deck is linear.

A "block" is a largest-possible contiguous set of equally-colored cards in the deck. For example, if the red/black cards come up (red, red, black, black, black, red, black, red, red, ...), we have a block of 2 red cards, then a block of 3 black cards, then a block of 1 red card, and so on.

1. You could determine the number of blocks by looking at each card in sequence, comparing it against the previous card. Can you design an algorithm to determine number of blocks such that, at least with high likelyhood, the algorithm need not examine every card?

2. Now we're only interested in whether the number of blocks is even or odd. What's the most efficient algorithm?

Both were solved by Proxima in IRC, but I found it interesting enough to give everyone a try. :-)

-- Simon

did you mean to say "a 'block' is ANY set of equally colored contiguous cards in the deck, including each "single" [e.g. 1 red card in between two blacks]"

The "largest possible contiguous set" means in you're example you would only count 1 block; the 3 blacks in a row.

1. Isn't there a large lack of information? Otherwise it's a huge gamble. There are a huge number of possibilies ranging from all cards being 1 color, to an equal amount of each and each color evenly shuffled [red,black,red etc..] or 2 blocks; all colors to each side. Even if you look at 50% of the cards I don't see the liklihood being very high that you get it right.

I guess I need a clue. I read part of Proxima's answer to one of these but it didn't make any sense to me.

[Simon]

did you mean to say "a 'block' is ANY set of equally colored contiguous cards in the deck, including each "single" [e.g. 1 red card in between two blacks]"

A block needn't be the overall-largest equally-colored contiguous set. The set is a block if you can't enlarge it: There is no strict superset (equally-colored, contiguous) of the set. As a result, each card belongs to exactly one block.

A single red card sandwiched between two blacks is a block of length 1.

1. Isn't there a large lack of information? Otherwise it's a huge gamble.

Your algorithm can do different things, based on what cards it has already examined. We're trying to minimize the need to look at cards. We aren't minimizing computational complexity.

There are a huge number of possibilies ranging from all cards being 1 color, to an equal amount of each and each color evenly shuffled [red,black,red etc..] or 2 blocks; all colors to each side. Even if you look at 50% of the cards I don't see the liklihood being very high that you get it right.

Look at more than 50 % of the cards. Yes, there are distributions in which you would have to look at every card. The idea is that the ratio of such distributions becomes close to 0 for large number of cards.

-- Simon

[bsmith]

How about this algorithm. I don't have end-of deck behavior, just the basic idea of the main process.
10 Start by looking at the first card, noting its color: card position = 1, block count = 1
20 Jump ahead to the second card after the current card and note its color: increment card position by 2
30 If these two cards are different, add 1 to the block count: increment block count by 1, goto 20
40 Go back one card (the one that was skipped) and note its color: decrement card postion by 1
50 If this card is different from the other two: increment block count by 2
60 Increment card position by 1 (already looked at it), goto 20