Round 3 https://manifold.markets/jacksonpolack/will-anyone-post-an-interesting-mat-92aee85710a2
Work must be done by close date
this is achievable btw! I've spent >8 hours on several algorithms problems in the last years (trying to derive the solution myself without looking for hints)
1,000🏅 Top traders
| # | Trader | Total profit |
|---|---|---|
| 1 | Ṁ25 | |
| 2 | Ṁ4 | |
| 3 | Ṁ2 |
People are also trading
A different way of trying to get up to 8 hours:
There is a competition you want to enter: Write a program to find n in a row of 1s (horizontal vertical and the two diagonal directions) in a 2d array of ones and zeros. The winner will be the program that makes the fewest reads of locations in the test arrays before being able to identify accurately where all the n in a row of 1s are.
The test 2d arrays which will have different n and different density of 1s.
Suppose the first test grid is 100*100, n=5 and the density of 1s is extremely low. You will need to read at least 20 from each row for 2000 reads. However in this situation you can use the same 2000 reads to cover the vertical and diagonal directions. How? You may find this easy to extend to 7 in a row and lots of other odd numbers, but what do you do if given n=6 or n=9. There are also all sorts of different patterns you might consider using if the density of 1s is higher.
Note I don't have anything like a full solution to this and I wouldn't be at all surprised if it just keeps on presenting problem after problem that you have to attempt to solve efficiently as the means of getting up to over 8 hours required.
40 Jewels 1 real 39 fake. Indistinguishable except by weight but I am not going to tell you whether lighter or heavier. Using a balance scales, guarantee to find the one real jewel in 4 weighings.
The fakes all weigh the same and the real one a slightly different amount.
(stolen from @ChristopherRandles)
@DanMan314 So someone noticed me posting that.
Could be extended by asking: How many can you cope with, with 5 weighings?
It probably isn't the right sort of question: many people attempting it probably spend less than 30 minutes on it and give up or conclude there is something wrong with the question. I did with an easier version then a few months later realised something which then made solving it easy. Did I spend less than an hour or months?
I do believe the question is correctly stated.
Has anyone:
a) solved it? or
b) given up on it? or
c) failed and searched for answer?
@ChristopherRandles I just fiddled around with it a bit and made some progress. I suspect a key insight is to have a holdout group, otherwise halving 40 four times is insufficient. I haven't applied this insight well enough to have a solution yet.
I'm also "wasting" a weighing distinguishing which of 2 imbalanced jewels is the fake at the end. I'm wondering if I could figure out whether the fake is lighter or heavier earlier on without losing a weighing.
Of course if this is too easy or not getting up to 8 hours, I can make it a whole lot more complicated:
Instead of one real and the rest fake, suppose I merely tell you there are more fakes than real and I want a formula for the maximum number that you can guarantee to cope with when allowed x weighings. (To be fair I should note that I haven't got a solution for this.)