• Current Events & Politics
    Welcome Guest
    Please read before posting:
    Forum Guidelines Bluelight Rules
  • Current Events & Politics Moderators: deficiT | tryptakid | Foreigner

Questions With Answers (cf. the "Universe Threads")

^Good job!

BTW, that was a BA original.

This weekend, I'll put some thought into your dual-colored houses problem. It looks like the solution will consist in every house being painted exactly twice by the end of the 17 month cycle. Hope someone doesn't beat me to it! ....LOL, yeah, right :)
 
I've seen a similar problem before, only it involved a circular board and quarters. First player to not be able to lay a quarter down on the board without either being over an edge or overlapping another lost. Player 1 would win by placing his first quarter in the center and then mimicking player 2 radially until 2 got forced off of the board.
 
RedLeader said:
Question: Seventeen painters live in 17 houses, each of which is either white or black. The houses are built around one circular road (entrance irrelevant). Each month, a single (novel) painter, starting from his own house, goes counterclockwise along the road and repaints houses according to the following rule:

1) Determine if the house is white or black.
1.a) If white, paint it black, move on to next house, and begin again at 1).
1.b) If black, paint it white, stop, and return home.

Prove that if at least one of the houses is originally white, then in 17 months time each house will have its initial color (note that in 17 months, each painter goes once).
Click to expand...

Sol'n ^


NSFW:
First, a bit of notation.

Let S be the set of binary representation of Z mod 2^17. Let "0" denote a white house, and let "1" denote a black house. Let P = {P_0, P_1, P_2, ... P_16} be the set of painters (that is, their corresponding permutation of S, per the "painting rules" you mentioned). For example, P_0(000...000) = 0111...111, and P_1(000...000) = 1011...111, and so on.

It is easy to show that for all P_x and P_y in P and all s in S, we have P_x*P_y(s) = P_y*P_x(s). In other words, P commutes under composition. Thus, to solve this problem, we want to show that:

P_0*P_1*P_2....*P_16(s) = s.

To do this, we make use of one key identity:

Identity P_i*P_i = P_(i+1)
(proof omitted for ease of BL text, but it's pretty easy to verify :) )

Lemma For all P_i in P, we have (P_i)^(2^17 - 1) is the identity function.

Proof: By the identity, (P_i)^2 = P_(i + 1). Thus, (P_i)^4 = P_(i + 1) ^2 = P_(i + 2), and (P_i)^8 = P_(i + 3), and so on. Hence, (P_i)^(2^17) = P_(i + 17) = P_i, whence the lemma follows. ###

And now, the grand finalee:

P_0*P_1*P_2...*P_16(s) = P_0*P_0^2*P_0^4...*P_0^(2^16)(s) = P_0^(2^17 - 1)(s) = s
 
Last edited:
BTW, the proof of the "lemma" depends on P being invertible. And this happens if and only if we exclude 1111...1111 (all houses black) from the range.




Again, very easy to prove, but I just thought I'd clarify that additional bit of handwaving.
 
NEW PUZZLER

You have six chunks of [No drug talk in S&T]. Their respective weights are 1 g, 2g, 3g, 4g, 5g, 6g.

You gave one of your [No prostitution talk in S&T] the supposedly simple job of labeling the chunks with the proper weight.

However, the bitch has been known to fuck up on occasion. So you want to double check her work.

Unfortunately, all you have at your disposal is a two-pan balance scale. In other words, you can't directly weigh any of the chunks, you can only determine if a given set of chunks is heavier, lighter, or equal to another set of chunks.

And even more unfortunately, it takes a full second to use the scale, and you've got a plane to catch in two seconds. So, yep, you can only use the scale twice.

So the question is, with only two weighings, how can you determine, with 100% certainty whether or not the bitch correctly labled the chunks? And no, you can't "eyeball" the chunks, or anything like that. The only information you get must come from the scales.
 
(This is kind of like the above one [which I have been too busy to try so far])

Question: John and Michael inherit n pieces of gold, which have a total weight of 2n. Each piece has an integer weight, and the heaviest piece is not heavier than the remaining n-1 combined. Prove that if n is even, then the boys can divide the gold into two piles of equal weight. Note that no scales are allowed; only a pen and paper.
 
^sketch of a "cleanish" sol'n:


NSFW:
Verify the statement, by enumeration of cases, for n = 2 & n = 4.

Begin the induction for n > (or =) 6.

Distinguish two cases:

1. there are fewer than two gold pieces of weight 1. Show that the statement follows almost immediately.

2. there are two or more gold pieces of weight 1. Remove two pieces of weight 1. Suppose the heaviest coin left has weight m. Replace m by m - 2. Thus, we now have n - 2 coins with total weight 2(n - 2). Thus, we can partition the coins into two groups of total weight n - 2***. Now, replace m - 2 with m, and we have a group (the one originally containing m - 2) with total weight n - 2 + 2 = n, and the statement follows.

***The exception is if the resulting coins are something like {1, 1, 1, 5}. This clearly cannot be partitioned into two groups of total weight 4 (of course, this falls outside of the "rules" of the game). But if we ended up with a set like this, that would mean our original set was {1, 1, 1, 1, 1, 7}, which would have also been outside of the rules.
 
This one is from the Stanford Mathematics Problem Book:

In a tennis tournament there are 2n participants. In the first round of the tournament each participant plays just once, so there are n games, each occupying a pair of players. Show that the pairing for the first round can be arranged in exactly (1 x 3 x 5 x 7 x 9 ... x (2n-1)) different ways.

And this is a fun one, since at first it appears unsolvable (uncertain of the progeny for this):

You and your partner invite 10 couples to a party. By questioning everyone (except yourself), you determine that each person asked has shaken the hand of a different number of people, and that no one has shaken the hand of his or her partner. How many hands has your partner shaken?
 
OK, no opiates today. Time for some PROOFZ, mutha fuckaz!

Problem #1.

NSFW:
We prove the statement by induction.

The equality is easy to verify for the case n = 1, as there is only one possible matchup.

Now, we assume that the equality holds for n = N, and show that it therefore holds for n = N + 1.

Progressing to N + 1, we have added 2 participants. Call them A & B. There are 2N + 1 possible opponents for A. And, after A is paired up, by our inductive hypothesis, there are 1 x 3 x 5 x ...x 2N - 1 ways to pair off the remaining 2N participants. Thus, the TOTAL number of possible matchups is [1 x 2 x 5 x....x 2N - 1] x [2N + 1], and the induction is COMPLETE.

Q to the E to the D.


Now, on to # 2.

NSFW:
By pidgeonholing, the number of handshakes is 20, 19, 18...2, 1, 0. (21 different people total).

Now, consider the person who shook 20 hands. Then this person's spouse must be the one that shook zero hands (because any one who is NOT this guy's spouse had their hand shaken by him).

Similarly, the person who shook 19 hands had the spouse that shook 1 hand (and her hand was shook by the last guy).

And, clearly, the pattern continues, so that, for each person, the number of hands he shook, plus the number of hands his spouse shook, is 20.

Hence, only a person who shook 10 hands could say that everyone (EXCLUDING HIM) shook a different number of hands (ie, because anyone else would say that there were TWO people that shook 10 hands).

Hence, the dude and his wife both shook 10 hands.

Bada bing. Fuckaz.
 
Last edited:
RedLeader said:
Question: If the set {1,2,..,3n} is partitioned into three equal subsets (in cardinality - so each has n elements), show that it is always possible to choose one number out of each set so that one of these three selected numbers is the sum of the other two.
Click to expand...


NSFW:
We do a proof by contradiction.

Call the sets A, B, & C.

Assume 1 is in A, and let b be the smallest element of B (which we assume is smaller than the smallest element of C).

Now, suppose c is in C. We show that c - 1 must be in A.

Pf: Clearly, c-1 can't be in B (otherwise, 1 + c-1 = c. Yeah, no).

Now suppose c-1 is in C. Then where can we put c-b and c-b-1? We can't either in A, because when added to b (from B), they yield c or c-1, both of which are assumed to be in C. If we put either one in B, then we can't put the other in C (as they are consecutive, and 1 is in A), and we can't put both in B, because b-1 (assumed to be in A) + c - b (in B) = c-1 (in C). Hence, our only remaining option is to place both c-b and c-b-1 in C. But by the same logic, c-2b and c-2b-1 must be in C. And indeed, so must c-nb and c-nb-1, until we are left with elements in C that are smaller than b, a contradiction.

Hence, the bold statement follows.

So, for all c in C, we must have c-1 in A. Hence, c-1 is an "into" function from C to A. But it's not "onto" as this function won't hit 1 (2 is in either A or B). Hence |C| < |A|, a contradiction.
 
^This, of course, begs two follow up questions.


On a scale of 1/10,

1. How hot is your sister?

2. How aroused is she by that huge mathematical penis I just whipped out on the table?
 
Last edited:
Problem: On Sunday Beauty learns that she is going to be put to sleep for the next two days, and be woken briefly either once or twice. A fair coin is tossed. If it lands on Heads, she will be woken just on Monday. If it lands on Tails, she will be woken on both Monday and Tuesday. If she is woken just on Monday (H), she is put back to sleep with a drug that makes her forget waking. Beauty knows this, so that when she wakes on Monday she won't know which day it actually is.

What probability should she assign to the coin having landed Heads (H)?

(A) 1/2, becuase it was a fair coin and she's learned nothing new relevant to how it fell.

(B) 1/3, because if the trial were repeated week after week after week, she should expect twice as many Tails-wakings as Heads-wakings. For every time the coin lands Tails she is woken twice, as compared with once when it lands Heads.

Question: Which answer, (A) or (B) is correct and why? (The answer is not "both" or "neither.")

Difficulty Level: Extremely Hard (sort of like a grown-up Monty Hall)
 
Last edited:
You must log in or register to reply here.
Top