The harder hardest logic puzzle where Random can randomly say 'ja', 'da' or remain silent cannot be solved in two questions. This is not too difficult to prove.

Let the gods be arranged ABC. When the gods are in arrangement W and a question P is posed to god A we write P_W(A) for the response (an element of {y,n,s} -- (y)es, (n)o, (s)ilent).

Claim. It is not possible to solve the version of the hardest logic puzzle ever where Random randomly remains silent, answers `yes' or answers `no' in two questions.

Proof. Assume (to reach a contradiction) that it is possible, then there is a procedure for solving it in two questions. Let Q be the first question that is asked in this procedure and without loss of generality assume it is addressed to god A. There are 4 possible arrangements of T, F and R such that A \neq R and only 3 possible responses. Hence there must be two different arrangements U and V with A \neq R such that Q_U(A) = Q_V(A). Let X = RTF, Y = RFT. Then we can choose Random's responses so that Q_U(A) = Q_V(A) = Q_X(A) = Q_Y(A) = D. But then after asking Q and receiving response D all we know is that the arrangement is one of U, V, X, Y. Thus the second question must distinguish 4 possibilities with one question which is impossible.

i haven't existed since i last existed here.



rlavwfv

Working on using the following theorem to prove the full Borodin-Kostochka conjecture.

Theorem: If G contains a doubly critical edge and satisfies chi >= Delta >= 6, then G contains a K_Delta.

So, the Borodin-Kostochka conjecture (and more) holds for graphs containing a doubly critical edge. This allows one to try to find a doubly critical edge instead of trying to find a big clique. This works to give a new proof of Brooks' theorem, but it gets intricate for the Borodin-Kostochka condition; however, there is a lot of room to play and it looks very promising (this all uses a decomposition theorem of Lovasz -- actually a modification of it by Catlin).

nqsiq

dxbpgril

One can only flourish among people who share the identical ideas and the identical will; i have no one -- that is my sickness.


whafedp

Infinitely many primes.

Here is a game.

I've picked a number between 0 and N and your goal is to find out what the number is by asking me yes/no questions.

(1) There are N+1 possible numbers i could have picked, so any plan that you devise will require you to ask at least lg(N + 1) questions in the worst case.
(2) There is a plan that you can follow that will require at most ceiling(lg(N + 1)) questions -- a binary search will do.


Assume (to reach a contradiction) that there are finitely many primes p_1, ..., p_M.

(3) N = p_1^k_1 * ... * p_M^k_M for some choice of non-negative integers k_1, ..., k_M.

(4) Since the smallest prime is 2, we have k_i <= lg(N) for all i. Consider the following plan.

Use (2) to determine k_1 in at most ceiling(lg(k_1)) <= ceiling(lg(lg(N))) questions.
Use (2) to determine k_2 in at most ceiling(lg(k_2)) <= ceiling(lg(lg(N))) questions
. . . .

We have determined k_1, ..., k_M in at most M * ceiling(lg(lg(N))) questions. But this determines N completely! So we have determined N in at most M * ceiling(lg(lg(N))) <= M * (1 + lg(lg(N))) = M * (lg(2) + lg(lg(N))) = M * (lg(2 * lg(N))) = lg((2 * lg(N))^M) questions.


(5) You can win the game in at most lg((2 * lg(N))^M) questions for any N. By (5) and (1), for all N we have lg((2 * lg(N))^M) >= lg(N + 1), killing the lg's gives

(2 * lg(N))^M >= N + 1

This holds for all N, so in particular for N >= 2^(2^(2^(2^M - 1) / M) / 2). This gives

(2 * lg(2^(2^(2^(2^M - 1) / M) / 2)))^M >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
(2 * 2^(2^(2^M - 1) / M) / 2)^M >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
(2^(2^(2^M - 1) / M))^M >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
2^(2^(2^M - 1)) >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
2^(2^(2^M - 1)) > 2^(2^(2^(2^M - 1) / M) / 2)
2^(2^M - 1) > 2^(2^(2^M - 1) / M) / 2
2^((2^M - 1) + 1) > 2^(2^(2^M - 1) / M)
2^(2^M) > 2^(2^(2^M - 1) / M)
2^M > 2^(2^M - 1) / M

M > 2^(2^M - M - 1)

Which is false for all positive integers. This contradiction completes the proof.


solkkj


uaugw


boiagmz

.NET and Nintendo on iMac. As i told Cerny, everything can be simulated.


hjukhova

Here is the magic squares searcher running on my iMac under vmware.