but how do you 'know' these can't be further optimized?Spoiler for like this
Well.... I guess I don't.
Spoiler for but let me think
Your assumption (highlighted in the quote) is not that difficult to prove.
Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-) |
Posted by k-man on 13 February 2015 - 06:44 PM
but how do you 'know' these can't be further optimized?Spoiler for like this
AAABBB
AAAABBB
AAABBBB
AAABBBB
AAABB
AAAAAA
AABBBBB
ABBAAAB
AAAABBB
BBBBB
Well.... I guess I don't.
Spoiler for but let me think1)There's no straight vertical line that can split the figure equally in half, which is really the only thing that might take fewer lines. So I must be right.
2) The maximum number of boundary segments that a figure composed of N unit squares can have is 2N + 2. Granted, I don't know how to prove this rigorously - but if I accept this, then I can actually calculate the number of line segments I need to create these shapes: (2 * (2 * 16 + 2) - 24) / 2 = 22. That's exactly how many I used.
Your assumption (highlighted in the quote) is not that difficult to prove.
Posted by k-man on 10 February 2015 - 06:25 PM
Using the interpretation of "crossing" as "having a common point with"...
Spoiler for there are an infinite number of such straight linesMore specifically, at least one straight line in every direction.
Let's draw a random straight line on the plane containing the polygons. Every one of the polygons with respect to that line is either
1) crossed by the line
2) lays entirely in one of the half-planes formed by the line - i.e. not crossed by the line.
Since every pair of polygons has at least one common point, all polygons that are not crossed by the line must be in the same half-plane. Find the polygon that is the farthest away from the line (call it P) and find the point on P that is the closest to the line (call it A). Draw another straight line through point A parallel to the first line. This new line crosses every polygon.
Spoiler for in case the conclusion is not obviousBy construction, the line "touches" polygon P, so aside from the point A (and potentially other common points), P lays entirely in one half-plane formed by the line. There cannot be any polygons that lay entirely in the same half-plane as P and not cross the line because any such polygon would be further away from the original line, but P was picked as the farthest polygon. There cannot be any polygons that lay entirely in the other half-plane either because they would not have any common points with P.
k-man always has such elegant solutions to these problems. I'm sorry but I couldn't contain myself.
Thanks, gavinksong, but the real credit should be given to BMAD for posting these great puzzles.
Posted by k-man on 09 February 2015 - 03:52 PM
Spoiler for I thinkIt's not possible, but <=75% is possible.
Is this claim for any nxm table or only when n = m ?
For any nxm. I don't have a rigorous proof, but I think it would go along these lines...
Suppose that there is a way to fill a rectangle as per OP requirements. Every row and every column will have a dominant color. Rearranging rows and columns doesn't change the number or ratio of black/white squares in each row/column, so we can rearrange rows in such a way that all black-dominant rows are on top and all white-dominant rows are on the bottom. Similarly, we can rearrange columns, so that all black-dominant columns are on the left and white are on the right. Using gavinksong's notation the rectangle would look like this:
XXXO
XXOX
XOOO
OXOO
Now, four quadrants have been established. Those quadrants will not necessarily have the same size, and that's where the proof gets tricky, but the idea is that the top left quadrant is all black and bottom right quadrant is all white. The other 2 quadrants are mixed colors. Let's look at the top right quadrant. It belongs to the black-dominant rows and to white-dominant columns, so to achieve balance it should be a 50/50 mix of black/white. Of course, the actual distribution of colors may be off balance especially if the whole black/white quadrants are not the same size, but since the total number of black squares equals the total number of white squares, it can be shown that if one color exceeds 75% in every row then the opposite color will be less than 75% in some columns or vice versa.
Posted by k-man on 30 January 2015 - 09:03 PM
Using the interpretation of "crossing" as "having a common point with"...
Let's draw a random straight line on the plane containing the polygons. Every one of the polygons with respect to that line is either
1) crossed by the line
2) lays entirely in one of the half-planes formed by the line - i.e. not crossed by the line.
Since every pair of polygons has at least one common point, all polygons that are not crossed by the line must be in the same half-plane. Find the polygon that is the farthest away from the line (call it P) and find the point on P that is the closest to the line (call it A). Draw another straight line through point A parallel to the first line. This new line crosses every polygon.
Posted by k-man on 18 November 2014 - 11:38 PM
Suppose that there isn't a common point shared by all 5 circles. Let A be the point that is shared by circles 1-4, but not by 5. Let B be the point that is shared by circles 1-3 and 5, but not 4. Let C be the point that is shared by circles 1,2,4 and 5, but not 3. Points A, B and C must all be distinct points, but all three are shared by circles 1 and 2. Since two circles can only have at most two points in common, we reached a contradiction.
Now, for disks, the answer is the same, although proof is different, but the OP isn't asking about the disks.
Posted by k-man on 12 November 2014 - 05:16 PM
Posted by k-man on 02 September 2014 - 08:05 PM
If the caretaker remembers 5 eggs which he might have swapped two of them,
(5c2) or 10 possible combinations,how he could find the pair with 2 trials?
Weight Eggs 6 1<->4 7 1<->3 8 1<->2 10 4<->5 11 3<->5 12 2<->5
If the weight is 10, then you need a second weighing to determine from one of 4 possible remaining scenarios: 1<->5, 2<->3, 2<->4, 3<->4.
You can weigh eggs 1, 3 and 4 and use the following table to determine the switched eggs:
Weight Eggs 6 2<->4 7 2<->3 8 3<->4 12 1<->5
I started working out a similar solution for 10, but didn't have enough time to finish it yet. I'm trying to do it in 3 weighings using a digital scale, but so far, looks like it will require 4. Maybe a combination of digital/balance could be optimal. Is it allowed?
Posted by k-man on 08 July 2014 - 05:06 PM
Posted by k-man on 23 June 2014 - 05:03 PM
In the picture below, the black lines are drawn as per the OP. The red lines are drawn through the point P parallel to the sides of the triangle. The red lines are dividing the triangle into 3 equilateral triangles (B,D,F) and 3 parallelograms (A,C,E). The black lines divide those triangles and parallelograms in half proving that the sum of blue shaded areas equals the sum of the white areas (every blue area marked with a letter has an equal white area marked with the same letter). Now let's look at triangles formed by black lines. Starting from left corner going clockwise (A+B) + (C+D) + (E+F) = (B+C) + (D+E) + (F+A).
Posted by k-man on 03 June 2014 - 07:07 PM
Convex hull method identifies pairs of red/blue points on the outside of the set, so those line segments cannot cross any other line segments. As long as there are points of both colors on the convex hull, we can continue to use this method.
If convex hull contains only red points, then Divide & Conquer method will always find such blue point that splits the set into 2 subsets (see gray line in step 4) each containing equal number of red and blue points. Each subset is then solved independently of another.
Posted by k-man on 10 April 2013 - 07:21 PM
I think you should mark this as solved. There is no way to place 6 points on a surface in a way that the minimum distance between any 2 points was m and the maximum distance between any 2 points was m*sqrt(3).
Let's start with one town and identify the area where the rest of the towns should be. This area is marked in red
Now, since we must have another town at the distance of m from the first, let's put it there and show the remaining area for the rest of the towns.
There are 2 red areas that should contain the remaining 4 towns. The distance between these two areas is exactly m*sqrt(3), which means that the only combinations that allow both areas to be used are marked as pairs of blue, green and purple dots. Choosing any pair of these dots eliminates any other possible locations for more towns. This way we get only 4 towns.
However, there is no way to fit 4 more towns in only one of these red areas. Below pictures aren't a formal proof, but make it pretty obvious that no more than 5 towns can be placed under these constraints. Black dots are committed towns. Red areas are remaining valid areas. Blue, green and purple dots are mutually exclusive with each other and red areas.
Posted by k-man on 14 March 2013 - 04:15 PM
This puzzle cannot be solved unless a bounded range of numbers is given. The OP simply states that the numbers are consecutive. If the numbers are drawn from an unbounded range then neither A nor B can ever deduce the other's number.
Posted by k-man on 13 February 2013 - 09:57 PM
GCEAFHDB
This linear arrangement works without placing any dolls inside any others. However, some neighboring dolls can be combined without breaking the conditions of the OP (for example B could be inside D and A could be inside F).
Posted by k-man on 30 January 2013 - 08:47 PM
There are a total of 18 possible ways how the stamps may be distributed among 3 players. Each "No" answer eliminates possibilities that have unique combination of colors for the other 2 players and would allow the answering player determine his colors. For example, the first "No" by player A eliminates the possibility that both B and C have 4 stamps of the same color. Each subsequent "No" answer eliminates any remaining possibility with unique combination. After 4 answers 5 possible distributions remain and in all of the player B has one red and one blue stamp. Here is the complete table of possibilities and the answer eliminating that possibility ("P" is for Pocket):
A B C P Answer BB RR RR BB 1 RR BB BB RR 1 BB RR BB RR 2 RR BB RR BB 2 BB BB RR RR 3 BB RR BR BR 3 RR BB BR BR 3 RR RR BB BB 3 BB BR RR BR 4 BR BB BR RR 4 BR BB RR BR 4 BR RR BB BR 4 BR RR BR BB 4 BB BR BR RR BR BR BB RR BR BR BR BR RR BR BB BR RR BR BR BB
Community Forum Software by IP.Board 3.4.7
Licensed to: BrainDen