Timeline for Find highest scoring matrix without property X
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:41 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Nov 7, 2014 at 23:50 | comment | added | justhalf | Oops, yeah, that's true, sorry for that. I edited my answer. | |
| Nov 7, 2014 at 23:50 | history | edited | justhalf | CC BY-SA 3.0 |
added 55 characters in body
|
| Nov 6, 2014 at 8:08 | comment | added | justhalf |
I see. Let's see whether that's true. =). Btw @xnor, I found another answer that seems to suggest there will always be solution for 2n-3: math.stackexchange.com/a/672555/92861
|
|
| Nov 6, 2014 at 8:06 | comment | added | kennytm |
@justhalf I mean the Java program shows for higher n, the pattern becomes 2n-2. Perhaps it becomes 2n-1, 2n, ... 2n+x for even higher n, which breaks the limit "2".
|
|
| Nov 6, 2014 at 7:53 | comment | added | justhalf |
@KennyTM: I can't really follow your reasoning. What do you mean by "higher for big n"? My answer also gets higher for bigger n, just that its limit is 2.
|
|
| Nov 6, 2014 at 7:46 | comment | added | kennytm | Since the score is smaller for low n (6/5 instead of 7/5), and given the Java answer is correct it is higher for big n (20/11 instead of 19/11, 22/12 instead of 21/12), I believe the matrix width is superlinear in n, and the score may be able to exceed 2. | |
| Nov 6, 2014 at 0:16 | comment | added | justhalf |
@KennyTM: Yes, the formula only works for n>=6. For n<=5, we have: 1/1, 2/2, 4/3, 5/4, 6/5.
|
|
| Nov 6, 2014 at 0:15 | comment | added | justhalf |
@PeterTaylor: I used de Bruijn sequence because I initially thought that the vectors of all possible combinations don't have property X (which is why I thought the answer is infinite). But after I found that that's not the case, I still continued using de Bruijn sequence. You seem to have found the truly optimal solution, though. Congrats! =). And btw using this sequence I only need to brute-force 2^n instead of 2^(2n-3), although like you said, it's not complete.
|
|
| Nov 6, 2014 at 0:13 | comment | added | justhalf | @xnor: No, I haven't been able to prove it, unfortunately. This is just a conjecture after seeing a pattern, and the code is just to brute-force it. | |
| Nov 5, 2014 at 20:08 | comment | added | kennytm | At least the formula doesn't work for n=5: The best ratio is 6/5 or 7/6. | |
| Nov 5, 2014 at 19:00 | comment | added | xnor |
Can you prove that you can always obtain a matrix of n*(2n-3)
|
|
| Nov 5, 2014 at 17:12 | comment | added | Peter Taylor | I'm not sure where de Bruijn sequences fit into things - can't you just brute-force by counting? But your brute force doesn't actually seem to be complete, because I think I've got a better result than the one you found. | |
| Nov 5, 2014 at 15:03 | comment | added | justhalf |
@Lembik I don't think I can. It requires n >= 31, which implies I'd need to check up to 2^(2n-3) = 2^59 combinations of 31-dimensional vector. Won't finish in our lifetime =D
|
|
| Nov 5, 2014 at 14:59 | comment | added | user9206 | In that case, can you beat 19/10 ? | |
| Nov 5, 2014 at 12:53 | comment | added | justhalf | @Lembik Now I can beat almost (limited by computational time) anyone claiming any score below 2. =) | |
| Nov 5, 2014 at 12:21 | history | edited | justhalf | CC BY-SA 3.0 |
Generalize the method
|
| Nov 5, 2014 at 11:05 | history | edited | justhalf | CC BY-SA 3.0 |
Improve score
|
| Nov 5, 2014 at 10:24 | history | edited | justhalf | CC BY-SA 3.0 |
Improve speed, add case n=8,9
|
| Nov 5, 2014 at 10:20 | comment | added | user9206 | A great start :) | |
| Nov 5, 2014 at 10:13 | history | edited | justhalf | CC BY-SA 3.0 |
Added scoring, add input
|
| Nov 5, 2014 at 10:07 | history | answered | justhalf | CC BY-SA 3.0 |