Thursday 31 October 2013

chess - Two Knights, two Bishops, two Rooks and two Kings on a 4x4 chessboard


Place two Knights, two Rooks, two Bishops and two Kings on a 4x4 chessboard, so that:


1) The Kings are not attacked at all.



2) All other pieces are attacked exactly once.


Ignore color, so every piece attacks every other piece whose square it can move to, including the Kings.


I don't know how many solutions there are, but there is at least one.



Answer



I hope I didn't make any mistakes:



enter image description here



Edit : Replace queens by king


Wednesday 30 October 2013

pattern - What is the central color?


This puzzle belongs to the puzzle series: hyper-modern art




The two friends move on in the gallery.


"You have now shown me two examples of hyper-modern art, but I still don't quite get it. What is this 'art' all about?"


"Art, my friend, should draw the observer closer, involve him, make him think or feel. Hyper-modern art aims at this with a slightly different angle. To understand an image, the observer has too fully engage with it until he discovers the things which rule the image underneath. By doing so, the image depicts exactly what can not be seen. Do you understand?"


"Hmm, I see how this applies to the two previous examples, but it doesn't help me much with understanding any new piece, does it? Just look at what is hanging here: Why on earth is the picture called The (colour) star, if the star is absolutely not of that colour?"


"Exactly! You have to see the invisible part of the picture to understand why it can only be that colour, my friend. But to make it easier, why not switch on your special HUD device to make it visible to you..."


"Oh."





HM3





The goal of the puzzle is to find the colour of the central circle marked with the star. It is one of the 7 colour used by the other circles (Red, orange, yellow, green, cyan, blue, or violet.) A complete answer must give both the colour and the explanation of why it is the correct colour. (Bonus: What does the HUD show?)





Hints




  • The outer ring colours are "paler" for visual effect only. The whole puzzle is based on 7 distinct colours and the solution is one of those 7.





  • The puzzle can be solved with a printed version of the image above. (Or by just looking at that image above.)




  • The puzzle has a single, objective and logical solution. The "Pattern" tag for this puzzle is appropriate. Basically the whole images follows a specific rule, and the central circle has to fulfil that rule as well, which defines its colour.





Answer



The central star should be coloured:




Indigo (dark blue)



The reason is, that if you draw a hexagonal grid across everything like this (excuse the sloppy photoshop work):



enter image description here



Then, for any given dot, you simply:



count up the number of dots on any of the intersecting lines, which will always give the same sum, based on the colour of the dot you chose:

Red - 0
Orange - 1
Yellow - 2
Green - 3
Blue - 4
Indigo - 5
Violet - 6



Tuesday 29 October 2013

strategy - Will a greedy algorithm solve Tatham's Flood?


I was just investigating some of the puzzles on Simon Tatham's website, and came across Flood, in which we start with an $n\times n$ grid of cells each of which is filled with one of $k$ predetermined colours, and (quoting the game instructions):



Try to get the whole grid to be the same colour within the given number of moves, by repeatedly flood-filling the top left corner in different colours.


Click in a square to flood-fill the top left corner with that square's colour.




My strategy for doing this is to use a simple 'greedy algorithm'. At each stage:



  • consider the single-colour block which starts from the top left corner

  • count the number of cells of each colour which are adjacent to this block (i.e. which will become part of the block if we flood-fill with that colour)

  • pick the colour such that this number is maximal, and flood-fill with that colour.


For example, in a position such as this:


example


... flood-filling blue would gain us 4 cells, purple would gain us 5, red 3, yellow 2, and orange 2, so we choose purple.





Is this algorithm always optimal? If so, is there a nice proof of its optimality? If not, what is the optimal algorithm for making the whole grid monochromatic as fast as possible?

Disclaimer: I don't know the answer to this question. Also, I'm not completely confident that I've explained the algorithm well enough - please leave a comment if it's not clear, and I'll try to improve it.



Answer



A normal greedy algorithm, as TheGreatEscaper has demonstrated, can be quite inefficient for some arrangements.


But there may be value in a greedy algorithm which values percentage of a colour removed, rather than merely number of cells removed. For example, in TheGreatEscaper's example, you have three choices - red, yellow, or orange. Choosing red will clear ~17% of the red on the board. Choosing yellow will clear ~50% of the yellow on the board. But choosing orange will clear 100% of the orange on the board. Therefore, there is no value in delaying the choice of orange.


I doubt even this approach would end up being guaranteed to be optimal. But I would expect it to perform better than the naive cell-count approach.


Even better would be if a multi-step greedy algorithm were applied - a greedy algorithm that looks more than one step at a time.


For instance, with a two-step algorithm, you'd look at the next two colours. So for example, using TheGreatEscaper's example, if you look only one step (using a cell-count approach), you get one cleared for each of red and orange, and two for yellow. With a two-step approach, the sequence orange-yellow, red-yellow, and yellow-Lgreen all clear 5 cells, whereas other choice pairs give fewer cells.


Using this, along with percentages, would stabilise the sequence, avoiding many of the pitfalls that the naive approach gives, although it probably won't be completely optimal.



Imagine TheGreatEscaper's example, but with orange replacing the dark blue at the far edges.


In this case, the sequence using the naive approach will go yellow (2), Lgreen (3), Dgreen (4), blue (5), orange (7), red (6), blue (5), Dgreen (4), Lgreen (3), yellow (2) - 10 steps.


If using a simple percentage approach (with a tie broken by count), it will go yellow (50%), Lgreen (50%), Dgreen (50%, 4), red (~67%), blue (100%, 10), orange (100%, 13), Lgreen (100%, 3), yellow (100%, 2), red (100%, 2) - 9 steps.


If using a percentage approach with two-step greediness, it will go red (~117%), yellow (200%), Lgreen (200%), Dgreen (200%), blue(200%), orange(200%), red - 7 steps.


Monday 28 October 2013

word - Alphabetical Sudoku



Who loves fish?




Okay that might sound a bit weird but don't worry, I am still sane.
Maybe.



To answer the question you must complete the Sudoku below. A word will appear in the highlighted box which will tell you who does indeed love fish.


Oh wait... I forgot to mention.


This is an alphabetical Sudoku


Instead of numbers this Sudoku uses the letters



MAEGLBDRT




Here's your starting grid (which has a unique solution this time):


enter image description here



EDIT



While an answer has been accepted anyone who can provide logical steps will get the accept




Answer



A logical derivation




All steps except two in the solution I present here are either
- "naked singles" - only possible value a cell could be, or
- "hidden singles" - only cell in a unit (row, column, or block) which could be that value
The two other steps are
- "alternating inference chains" - If this cell is X then another cell isn't X, then another cell is Y, etc.
...both of which lead to row-wise contradictions.

I bring in pencil marks (the values a cell could possibly be) before the alternating inference chains and highlight the first cell in green, then the relevant pencil marks that can't be something in red and those that must be something in green; then show the row-wise contradiction in blue.

animated solution



Here is a step-by-step, unanimated version with the deductions:




The original sudoku:
1
Naked single at D7:
2
Naked singles at E7 and G7:
3
Naked single at B7:
4
Hidden singles at A1, I4, E5, and G9 (all "only cell in block that may take value"):
5

Hidden singles at
- F4 ("only cell in row that may take value"); and
- A9 ("only cell in column that may take value")
(also added pencil marks):
6
Assume: D6 $=$ M
$\rightarrow$ F5 $\neq$ M and F6 $\neq$ M
$\rightarrow$ F6 $=$ A
$\rightarrow$ F5 $\neq$ A
$\rightarrow$ F5 $=$ D

$\rightarrow$ A5 $\neq$ D
$\rightarrow$ A5 $=$ A
$\rightarrow$ H5 $\neq$ A
$\rightarrow$ H6 $=$ A:
7
Contradiction between F6 and H6 both being A, hence D6 cannot be M as was assumed:
8
Assume D6 $=$ A
$\rightarrow$ F5 $\neq$ A and F6 $\neq$ A
$\rightarrow$ F6 $=$ M

$\rightarrow$ F5 $\neq$ M
$\rightarrow$ F5 $=$ D
$\rightarrow$ A5 $\neq$ D
$\rightarrow$ A5 $=$ A
$\rightarrow$ H5 $\neq$ A
$\rightarrow$ H6 $=$ A:
9
Contradiction between D6 and H6 both being A, hence D6 cannot be A as was assumed:
10
Naked single at D6:

11
Hidden single at D3 ("only cell in row or column that may take value"):
12
Naked single at G3:
13
Naked single at C3:
14
Naked single at B3:
15
Naked single at H3:

16
Hidden singles at B5 and I8 (both "only cell in block, row, or column that may take value"):
17
Hidden single at F5 ("only cell in row that may take value"):
18
Naked single at F6
Hidden single at D4 ("only cell in block that may take value"):
19
Naked single at H6:
20

Naked singles at G4 and B6:
21
Naked singles at G1 and I5:
22
Naked singles at D1, G2, and H5:
23
Naked singles at I2, A5, and D9:
24
Naked singles at D2, E2, C5, F8, and H9:
25

Naked singles at E1, F1, C8, H8, and E9:
26
Naked singles at H1, C2, F2, A8, and E8:
27
Naked singles at B1, H2, A4, and C9:
28
Naked Singles at B4 and B9, completing the sudoku:
29






Previous


I got the answer first with my home-brewed solver.



BALDEAGLE:


>>> text = '  E     MM        R    EA D  B L  M    T  B  G T B D LL M  R DA   G  T       B   '
>>> translation = [c for c in ' EMRADBLTG']
>>> numericString = ''.join(str(translation.index(c)) for c in text)
>>> sudoku=ss.Solver(numericString)
>>> sudoku
1 2 3 4 5 6 7 8 9

--------+-------+--------
A| · · 1 | · · · | · · 2 |A
B| 2 · · | · · · | · · · |B
C| 3 · · | · · 1 | 4 · 5 |C
--------+-------+--------
D| · · 6 | · 7 · | · 2 · |D
E| · · · | 8 · · | 6 · · |E
F| 9 · 8 | · 6 · | 5 · 7 |F
--------+-------+--------
G| 7 · 2 | · · 3 | · 5 4 |G

H| · · · | 9 · · | 8 · · |H
J| · · · | · · 6 | · · · |J
--------+-------+--------
1 2 3 4 5 6 7 8 9
>>> for soulution in sudoku.genSolutions():
... slnNumeric = sln.representation()
... print(''.join(translation[i] for i in [int(slnNumeric[j]) for j in >!range(0,81,10)]))
...
BALDEAGLE
>>>


Saturday 26 October 2013

wordplay - A chain of words



curlicue
baleful
running rigging example
passionate
toothy?
more up

complement of because
triangular cloth
curlicue



Replace each line above with a new two-syllable word of similar meaning that is legal in Scrabble. The last two or more letters of each new word must form the start of the next new word, and the first and last new word must be the same word. The correct answer might follow a pattern like below, for example.



abcdefg
defghi
ghijkl
klmn

mnop
nopqrstuv
tuvwxyz
yzab
abcdefg




Answer



This sequence seems to fit



curlicue - ringlet

baleful - lethal
running rigging example - halyard
passionate - ardent
toothy? - dental
more up - taller
complement of because - ergo
triangular cloth - goring
curlicue - ringlet



riddle - Colored Pills MADNESS



You have two bags of similar (weight, texture) solid pills. One bag contains red pills and the other contains green pills. There are 13 pills in one bag and 14 pills in the other. Today, tomorrow, and the day after tomorrow you must select and consume a valid pill set from the following options:



  • [3 green pills and 8 red pill]

  • [3 green pills and 4 red pill]

  • [4 green pills and 3 red pill]


Although you are blind, your colorblind friend is there to assist you. Neither of you know which bag contains which colored pills.


Side effects (Upon you):



  • When you take an invalid pill set you die.



Side effects (Upon your friend):




  • Concurrently taking 3 red pills today will instantly blind your friend forever.




    • Consecutively taking 2 red pills today will instantly blind your friend for 24 hours.



      • Taking 1 red pill today will instantly remove a positive memory from your friend for 48 hours.







  • Concurrently taking 3 green pills today will instantly fix your friend’s color blindness forever.




    • Consecutively taking 2 green pills today will temporarily fix your friend’s color blindness, tomorrow.




      • Taking 1 green pill today will temporarily fix your friend’s color blindness, the day after tomorrow.






  • Taking any number of green pill within a minute after taking any number of red pills will instantly undo the red pill’s side effects. Green pill side effects will still apply.




  • Taking any number of red pill within a minute after taking any number of green pills will instantly undo the green pill’s side effects. Red pill side effects will still apply.





How can you insure the cure of your friend’s colorblindness indefinitely and your survival?



Answer



Denote the bags as A and B, where A has 14 pills and B has 13. Have your friend grab two pills from A, and hold three from B in his other hand (so he knows where it is if he goes blind). Your friend takes the two from A, and determines if he's gone blind or not:


If he's blind, he takes the pills he grabbed from B. B is green, A is Red. Once the green pill he took fixes his vision, have him label the bags (leave them in distinct places so he doesn't mix them up). There are now 12 red pills and 10 green ones, so you can take 4 red and 3 green each day and everything is good


If he isn't blind, he should take 1 more from A (or 3 if taking 2 then 1 green doesn't work), and put the three pills from B back. Have him label the bags (A is green, B is red), and you'll have at least 9 green and 13 red left. Take 4 red and 3 green each day, and it'll all be dandy


mathematics - Move a single match to make this expression true


Move a single match to make the following expression true:


6 + 4 = 4


So far I've found 6 valid solutions, can you find all 6? (or more!)


Edit: Lots of great, creative answers! All 6 I found are represented among the answers, plus quite a few more!



A few clarifications:



  1. I changed "equation" to "expression" in the title and question, for the mathematically pedantic. This officially allows for inequalities.

  2. The expression still has to logically evaluate to true or false in a boolean sense. So "8 + 4 - 4" wouldn't count, even though it might be treated as TRUE by most programming languages.

  3. You're not limited to "perfectly-formed" LED-style numbers, although using a single vertical match as a "1" is kind of stretching it. But I'll allow it, if it gets us more good answers.



Answer



Here are the compiled expressions from the current answers. These are from Glorfindel's answer, Matt's answer, humn's comment, as well as the various other comments on other answers. I have also added alphabetic labels to identify the unique relations and the different expressions.


Expressions A through G are either equations and strict inequalities with one operator:




[A] 0 + 4 = 4
[B] 5 + 4 = 9
[C] 8 - 4 = 4
[D] 6 + 4 > 4
[E] 6 ≠ 4 - 4
[F] 5 + 4 ≠ 4
[G] 6 - 4 ≠ 4



If expressions can have multiple inequality operators, then you also get expressions H and I:




[H] 5 ≠ ­4 ­= ­4
[I] 6 > 4 = 4



In total, that's 9 unique relations listed above.


For some of the inequalities that contain ≠, you can rewrite the expression with a different inequality operator. Because these new expressions have similar structure, I indicate them with a * suffix.


If the + was changed into ≠, then the + can also be changed into a negated strict inequality (either ≮ or ≯). Or, if the = was changed into ≠, then the = can also be changed into a non-strict inequality (either ≥ or ≤).



[E*] 6 ≮ 4 - 4
[F*] 5 + 4 ≥ 4
[G*] 6 - 4 ≤ 4

[H*] 5 ≮ ­4 ­= ­4



This raises the total to 13 different expressions.


If you allow a single vertical match to count as the number 1, then there are more expressions that you can form, using the same rules as above:



[J] 614 ≠ 4
[J*] 614 ≥ 4
[K] 6 + 4 ≠ 11
[K*] 6 + 4 ≤ 11
[L] 6 + 11 ≠ 4

[L*] 6 + 11 ≥ 4



These additional expressions raise the total to 19.


Friday 25 October 2013

riddle - A Puzzle With Weird Genii Making Deli Meat


Part of the Community Metapuzzle. The word in the puzzle below is also the word needed here.




I received a very odd communication this morning. When I got up, I found a letter on the kitchen table. It wasn't there last night. The doors were all still locked and the windows latched. I heard nothing although I am a very light sleeper.


When I picked up the letter, I saw that it had no stamp - I hadn't expected to see one - only a stylized capital Q in the upper left corner and in the center, the words I have used in the title: "Weird Genii Making Deli Meat".



Inside was a single sheet of what I believe to be papyrus. The poem that appears below was written on it in reddish-brown ink using a brush of some sort.


I know humn went much deeper into the time and space travel aspect of the community meta-puzzle than the rest of us. I can only assume that he has discovered some of the dread secrets from which Deusovi tried to protect us. I believe the poem was written in ancient Egypt. I have no theory regarding the envelope. I can only pray humn returns safely to this time and place. I believe also that it is, was, or will be his wish that this poem be published as part of the community meta-puzzle. I hope I am doing the right thing.



It's a piece of a code round a man with a gun.
More than half a grand grand of it, isn't that fun?
It is found in your fist and the glove of a fox
And this pie piece, I've heard, is no stranger to socks!




Answer



I believe the answer is




DIGIT.



Firstly, the title:



Weird Genii Making Deli Meat.



As soon as I saw the word "genii", I suspected that



final letters of words would be required somewhere along the line -- that word was clearly chosen because it's one of relatively few English words which end in I




-- and I was not disappointed!





a stylized capital Q in the upper left corner



This just refers to humn's avatar:


humn


The whole business of talking about humn in the question also appears not to be part of the puzzle, but simply a reference to the fact that humn was originally supposed to contribute to the community metapuzzle but was unable to, and so you've valiantly stepped up to take his place.





It's a piece of a code round a man with a gun.

This is probably a wordplay clue of some sort, the 'round' cluing us to put one word around another to get DIGIT? Edit: yes indeed, it's DI(GI)T: "dit" as in the dits and dahs of Morse code, GI as in a US soldier.



More than half a grand grand of it, isn't that fun?



A grand is slang for a thousand, so half a grand grand is 500,000. Not sure what that has to do with digits though, except that it's got six of them. Edit: DI is "more than half a grand" in Roman numerals, and "grand of it" --> G+IT. Also "isn't that fun?" could be a reference to "dig it?"



It is found in your fist and the glove of a fox




Digits (fingers) are in a fist, and foxgloves are also called digitalis.



And this pie piece, I've heard, is no stranger to socks!



Something to do with pi(e) being irrational with infinitely many digits?



Thanks to @GarethMcCaughan for some help with the riddle - specifically, both edits above.


mathematics - The clearly wrong proof


Bob claims to have a proof that $0.\dot1=1$.
That's $0.\overline1=1$, $0.(1)=1$ or $0.11111...=1$ in other common formats.
The proof starts $$\text{If }1x=0.\dot1,\\ \text{then }10x=1.\dot1\\ 10x-1x=1.\dot1-0.\dot1\\1x=1\\ \text{substituting in the value of }1x\text{ for }0.\dot1\text{ (as defined at the start)}\\ \\0.\dot1=1$$


He is not wrong (Ignore the title). Everything is correct. Every number in this question is in base $10$.


How is this possible?



Answer





"There are 10 types of people in this world, those who understand binary and those who don't."

Bob is doing his calculations in base 2 (aka. binary): $$0.111..._2 = 1_2$$ similarly to the the following in base 10: $$0.999..._{10} = 1_{10}$$ The apparently wrong part is correct when the calculation is done in base 2: $$10_2 - 1_2 = 1_2$$ The last sentence states that every number is in base 10, which interpreted correctly (as a binary number again) means that every number is in base $$10_2 = 2_{10}$$



Thursday 24 October 2013

strategy - The knight's game


Alice and Bob play the following game on a standard $8\times8$ chessboard.



  • In the very beginning, Alice picks a square on the chessboard and places a knight on this square.

  • Then Bob and Alice alternate in moving the knight. Bob makes the first move. The knight moves in standard chess knight-move fashion, but it must never revisit a square that it has visited in an earlier move.

  • The game ends, once a player has no move left. This player wins the game.




Question: Which player is going to win this game? (As usual, we assume that Alice and Bob both use optimal strategies.)




Answer



The player who will win this game on an $8 \times 8$ board is:



Bob, assuming he has a computer and a few hours to calculate the variants (details below). It doesn't matter which square is chosen by Alice, because Bob has always a forced win. On smaller boards Alice has always at least one square which she can choose to win.

With the result known, maybe someone can come up with a solution that doesn't require an exhaustive search. But if the solution is not specific to an $8 \times 8$ board, it has to explain why Alice can win on smaller boards.



Computer based proof


I managed to significantly increase the speed of my previously posted program, so I was able to calculate the result for an $8 \times 8$ board. It's much bigger now, but I have added some comments this time. The speed up was achieved through following steps:




  • Mutlithreading: Usually pretty obvious, but I use it here only to calculate all starting positions in parallel. This doesn't complicate the code as much as other possibilities.

  • Precalculating possible moves: Also pretty obvious, not much to say here.

  • Sorting the possible moves: This was the most important point, and a huge speed up. The idea is, if we find a winning move for the current player, we don't need to check the other possible moves. The hard part is to find the right moves. I did it here by sorting the possible moves by the number of possible moves from their target square. So corner squares are preferred, squares in the center are searched last. The effect is huge, if you want to see it set the SIZE to 7 and reverse the sorting.


Despite the speed up, calculating the $8 \times 8$ results takes several hours. On a Core i5 I got the result for the first square (C1) after 1 h 38 m. Total runtime was about 8.5 hours.


Results for smaller boards


The result is that Alice always has a square where she can guarantee a win:



  • $3 \times 3$: any square except B2 (example win)

  • $4 \times 4$: any corner square (example win/loss)


  • $5 \times 5$: A1, C2 and any mirrored/rotated version of them (example win/loss)

  • $6 \times 6$: C2 and any mirrored/rotated version (example win/loss)

  • $7 \times 7$: any black square (example win/loss)


The code


import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

public class Main {

private static final int SIZE = 6;
private static final int[] ROW_OFFSET = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 };
private static final int[] COL_OFFSET = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 };

private static class Square {
/** Usual naming: A1, B2, C3, ... */
public final String name;
/** Possible knight moves from this square. */
public Square[] moves = new Square[0];
/** Marks that this square was already used in the current variant. */

public boolean used = false;

public Square(int row, int col) {
super();
this.name = (char) ('A' + col) + "" + (1 + row);
}

/** Append a move to the array. */
public void addMove(Square square) {
int tmp = moves.length;

moves = Arrays.copyOf(moves, tmp + 1);
moves[tmp] = square;
}
}

/** Create a new board with the given size. */
private static Square[][] createBoard(int size) {
Square[][] board = new Square[size][size];
// Create all squares first, so that they can be referenced later.
for (int row = 0; row < size; ++row) {

for (int col = 0; col < size; ++col) {
board[row][col] = new Square(row, col);
}
}
// Precalculate all possible knight moves.
for (int row = 0; row < size; ++row) {
for (int col = 0; col < size; ++col) {
for (int i = 0; i < ROW_OFFSET.length; ++i) {
int newRow = row + ROW_OFFSET[i];
int newCol = col + COL_OFFSET[i];

if (newRow >= 0 && newRow < size &&
newCol >= 0 && newCol < size) {
board[row][col].addMove(board[newRow][newCol]);
}
}
}
}
// Sort the possible moves by number of moves from the target square.
for (int row = 0; row < size; ++row) {
for (int col = 0; col < size; ++col) {

Arrays.sort(board[row][col].moves, (o1, o2) ->
Integer.compare(o1.moves.length, o2.moves.length));
}
}
return board;
}

/**
* Determine the winner of current position.
* @param player '0' for the first moving player (Bob), '1' for the second

* moving player (Alice).
* @param square Target square of the last move, or square chosen by Alice
* to start.
* @return Number of the player who will win the game.
*/
private static int winner(int player, Square square) {
// Mark target square as used.
square.used = true;
try {
boolean movesLeft = false;

// Recursively check all possible moves.
for (Square newSquare : square.moves) {
if (!newSquare.used) {
movesLeft = true;
if (winner(1 - player, newSquare) == player) {
// If the current move wins the game for current player,
// there is no need to look further.
return player;
}
}

}
// No winning move found. If there are no moves left at all we win,
// otherwise we loose.
return movesLeft ? 1 - player : player;
} finally {
// Unmark target square before backtracking.
square.used = false;
}
}


public static void main(String[] args) {
Instant begin = Instant.now();
// Check all unique starting squares.
for (int row = 0; row < (SIZE + 1) / 2; ++row) {
for (int col = row; col < (SIZE + 1) / 2; ++col) {
// Each square is checked by a separate thread, so each of them
// need a new copy of the board.
Square square = createBoard(SIZE)[row][col];
new Thread() {
@Override

public void run() {
System.out.println(square.name + " " +
winner(0, square) + " " +
Duration.between(begin, Instant.now()));
}
}.start();
}
}
}
}

Wednesday 23 October 2013

strategy - $N_{max}$ balls in 3 weightings



This is a small generalization of well known 12 balls puzzle:



You are given two-sided scale and some number of balls. All balls have the same weight but one. It is of a different weight, although you don't know whether it's lighter or heavier. You are allowed to do only 3 weighings to determine not only what the different ball is, but also whether it's lighter or heavier. You can distinguish balls, but you do not know a weight of some of them. How many balls with unknown weight you may have and still be able to find the different one?




Answer



This answer is a follow up of Joe Z.'s answer on the similar puzzle. If you have problems with understanding this one, you can read Joe Z.'s answer, which explains used notations in much more details, which I would like to skip here.


In the assumption of fixed weighing schedule the optimum (maximum) number of unknown balls are, so to say, 13.5, where optimum (minimum) number of known balls is 1.
The following is solution for tasks with 13 balls with unknown weight (they can be normal, light, heavy), 1 ball with partially unknown weight (it can be either normal or lighter, but it can't be heavier) and 1 ball, which is known to be normal.


It is easy to prove that you can't add more unknown balls and you need at least one known ball.
Indeed:

1. this has $13\times2+1 = 27$ possibilities to choose between, this is maximum having 3 weights and 3 states of them: $27=3^3$;
2. you must use all $27=3^3$ possible sets of ball placement: 2 sets per first 13 balls to distinguish between heavy and light and 1 set (which is "always off the scale") for 14-th ball, but one can see that in this case exactly 27 balls must be on the scale in total during 3 weightings, that means at least one time there must be odd number of balls, this would lead to fault until we have one more ball is needed with known state.


Ball's arrangement:


Ball  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10-11-12-13
W1 L L R R L R R L R L R R L L R L L R L
W2 L R L R L R L R R L R L R L R L R L L
W3 R L R L L L R R R L L R L R R R L L L

Table of inverses here should not include 14th and 15th balls, since they are already different and you can distinguish between them using their properties.


Weighing schedule of balls:



Weighing 1:  1  4  8 12 13 /  5  7 10 11 15
Weighing 2: 2 6 9 11 13 / 4 7 10 12 15
Weighing 3: 5 8 9 10 13 / 3 6 11 12 15

The outcomes interpretation:


= = L :  3L    L = = :  1H   R = = :  1L
= = R : 3H L = L : 8H R = L : 5H
= L = : 2H L = R : 5L R = R : 8L
= L L : 9H L L = : 7L R L = : 4L
= L R : 6H L L R : 10L R L L : 12L

= R = : 2L L R = : 4H R L R : 11H
= R L : 6L L R L : 11L R R = : 7H
= R R : 9L L R R : 12H R R L : 10H
= = = : 14L L L L : 13L R R R : 13H

Tuesday 22 October 2013

Word Number Puzzle


If letters are factors of equations:


zero = 0


one = 1


two = 2


three = 3


four = 4


five = 5


six = 6


seven = 7



eight = 8


nine = 9


ten = 10


twelve = 12


fifteen = 15


twenty = 20


thirty = 30


forty = 40


sixty = 60


hundred = 100



thousand = 1000


million = 1000000


What is the product for answered = ?



Answer



The answer of the equation answered is



±3,401,222,400



Here I want to thank Matsmath to remind me that a negative solution do exist.

I use induction to find out the law behind the puzzle, with 11 steps below:


Step 1:




Let's take a look at sixty first. Here we can cut it into two pieces: six and ty. As six is known as 6, we can found that:

ty = 10

ten as 10, ty as 10, so there is a equation:

y = en

Then we can compare ty to other "tys". In forty we found:

for = 4

four as 4, also for as 4, so the letter u can be found as:

u = 1

In twenty we found that twen as 2, the same value as two, and another euqation is here:

en = o

Along with y = en we summarize that:

y = en = o In thirty, thir represent the value 3. Compare thir with three, we found that:

i = ee



Step 2:



Focus on one, and the equations we have in step 1:

y = en = o

Then we found the equation one can be seen as oo. Since the value is 1, we found that:

o = ±1

Then apply y = en = o with value o, we found:

y = en = o = ±1



Step 3:



Here we look at ten, with the fact that en is ±1, the value of t can be found:

t = ±10




Step 4:



Variable t has found, then we focus on equation two, along with the value of o, w is solved:

w = 1/5



Step 5:



Put equation en = ±1 into consider when we see nine, a new equation is found:

ni = ±9

Since ni need to multiply ne to have a positive 9, and we can assume that n could be a negative number.

Then combine i = ee with the equation above, we found that:

een = ±9

As we know en = ±1 and n can be negative, then e, n and i have been solved:

e = 9, n = ±1/9, i = 81



Step 6:




Back to equation thir, we join the value of t and i, and we found that:

81 * (±10) * hr = 3
27 * (±10) * hr = 1
hr = ±1/270



Step 7:



Take a look at hundred, here we join the value of u, e, and n (with both positive and negative), and:

hundred = hndrd = 100

We have found the value of hr in step 6, the equation become like this:

hndrd = hr * n * dd = (±1/270) * (±1) * dd = 100
dd = 27,000




Step 8:



For equation fifteen, put the value of i, t, e, n into it, and fifteen becomes:

fifteen = 81 * (±10) * 9 * (±1) * ff = 15

And ff is:

ff = 1/486

Then the f itself:

f = ±1/(9√6)



Step 9:



With the value of f, we can turn to four and solve r. First, join o = ±1, u = 1, we can see that:

four = f * (±1) * 1 * r

Then, join the value of f:

f * (±1) * 1 * r = ±1/(9√6) * (±1) * 1 * r
= 1/(9√6) * r = 4

And we can found r is (with square version):

r = 36√6
rr = 7,776




Step 10:



Move our step to thousand and hundred, we can apply a division here:

thousand / hundred = tosa / red = 1,000/100 = 10

Join t, o, and e s' value into it, and here it goes:

(±10) * (±1) * sa /9 * rd = 10
sa /9 * rd = 1
sa = 9 * rd



Step 11:



Finally, focus on the equation answered. Just a bit more to reach the solution!
Join the value of n, w, and e.

answered = a * (±1/9) * s * (1/5) * 9 * r * 9 * d

= (±1) * (1/5) * 9 * as * rd

We have known that as = 9*rd from step 10:

(±1) * (1/5) * 9 * as * rd = (±1) * (1/5) * 9 * (9 * rd) * rd
= (±1) * 81 * (1/5) * rrdd

Join the value of rr and dd from step 9 and 7 respectively:

(±1) * 81 * (1/5) * rrdd = (±1) * 81 * (1/5) * 7,776 * 27,000
= (±1) * 81 * 5,400 * 7,776

Note that there's a ±1 inside, and we found equation answered is actually:

answered = ± 3,401,222,400



Monday 21 October 2013

calculation puzzle - "Magic: the Gathering" Challenge #4: Stuck in the Grenzone


Previous Challenge


Next Challenge


BACKGROUND:


The usual magic rules apply here. Please don't post a solution that if a solution for more damage already exists. Please be explicit in mana usage in your solution. I've tried to ensure that there are no infinite loops available, but if I somehow missed one (that Kiki-Jiki's always causing trouble), please inform me and I'll remove the required components from the puzzle.


For this puzzle, assume that unless otherwise modified, the bottom of your library will always be 50 mountains, regardless of shuffling. Similarly, assume that beneath any cards deliberately placed on the top of your library, there will always be 50 mountains regardless of shuffling. Basically, you can't just activate Grenzo blindly and say that you hit whatever you want. Cards on the top or bottom cannot be assumed to exist there unless deliberately placed there in your solution.


Oh and for those wondering, no, the punny titles will not stop as long as I can help it.


PUZZLE SETUP:


It is your main phase 1. You have just had a Goblin Recruiter enter the battlefield (don't worry about how, it's magic) and are about to resolve its ability. Defeat your opponent this turn by doing as much damage as possible! The solution that gets the most damage through wins. I won't tell my current best record as I don't want to dissuade other answers that do less damage from getting posted initially, but suffice to say that it is in the triple digits.


Your hand:

Demonic Tutor
Brightstone Ritual


Your board: (all untapped; recruiter has summoning sickness, the others do not)
Grenzo, Dungeon Warden with a +1/+1 counter, making it a 3/3
Viscera Seer
Sol Ring
Goblin Recruiter
1 Forest
2 Mountain
2 Swamp



5 life


Your graveyard:
Nothing


Your library:
Adaptive Automaton
Battle Squadron
Beetleback Chief
Blazing Shoal
Brightstone Ritual
Chasm Guide

Clickslither
Coat of Arms
Door of Destinies
Empty the Warrens
Goblin Bushwhacker
Goblin Chieftain
Goblin Clearcutter
Goblin General
Goblin King
Goblin Lookout

Goblin Marshal
Goblin Matron
Goblin Ringleader
Goblin War Marshal
Goblin War Strike
Goblin Warchief
Goblin Wardriver
Goblin Welder
Hall of Triumph
Heartstone

Hellraiser Goblin
Kiki-Jiki, Mirror Breaker
Krenko, Mob Boss
100 Mountain
Murderous Redcap
Reckless Charge
Reckless One
Siege-Gang Commander
Vampiric Tutor
Warren Instigator

Zada, Hedron Grinder


Opponent's hand:
Nothing


Opponent's board:
Nothing


20 life


Opponent's graveyard:
Nothing



Answer



Some slight improvements to the solution DrunkWolf used (I don't feel too bad about the similarities, I swear I came up with the base solution independently).



Goblin Recruiter puts the following on top of my library:



  • Goblin Marshal

  • Kiki-Jiki, Mirror Breaker

  • Goblin Chieftain

  • Krenko, Mob boss

  • Goblin Clearcutter

  • Goblin Ringleader

  • Goblin Welder



Tap everything for ]]]]]]
Sacrifice Recruiter to Viscera seer to scry Marshal to the bottom, then activate Grenzo to get Marshal (2 tokens) ]]]]]
Sacrifice a token to bottom Kiki-Jiki, then activate Grenzo to get Kiki (1 token) ]]]
Tap Kiki to copy Marshal (3 tokens)
Sacrifice both Marshals to bottom Chieftain and Krenko (7 tokens)
Cast Brightstone Ritual ]]]]]]]]]]]
Activate Grenzo twice to get Chieftain and Krenko ]]]]]]]
Sacrifice Kiki-Jiki to bottom Clearcutter
Activate Grenzo to get Clearcutter ]]]]]
Tap Clearcutter for three red ]]]]]]]]

Sacrifice Clearcutter to bottom Ringleader
Activate Grenzo to get Ringleader, putting Goblin Welder into your hand. ]]]]]]
Cast Goblin Welder ]]]]]
You now control Grenzo, Chieftain, Krenko, Ringleader, Welder and 7 tokens. Activate Krenko for 12 tokens
Cast Demonic Tutor getting Vampiric Tutor ]]]
Cast Vampiric Tutor putting Coat of Arms on top ]]
Sacrifice Viscera Seer to bottom Coat of Arms
Activate Grenzo to put Coat of Arms into the graveyard
Activate Goblin Welder to swap Sol Ring for Coat of Arms


Attack with 27/27 Grenzo, 26/26 Ringleader, 25/25 Chieftain and nineteen 25/25 tokens, for a total of 553.



Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...