wonderings

Thread Rating:
  • 6 Vote(s) - 2.5 Average
  • 1
  • 2
  • 3
  • 4
  • 5
wonderings
#56
RE: wonderings
In a programming language where the only operations are boolean OR and boolean NOT, all variables are 1-bit, and data can only be read once before it is destroyed, what operations are possible, and how can we distinguish those that are and those that aren't?

Or, if we represent all boolean operations as directed graphs, what operations are both planar and acyclic?

Or, what operations can we make with redstone in minecraft without ever making bridges?


Given some finite collection of positive integers S = {a1, ... } (repeats are allowed) of size N, where you're allowed to ask for the closest number X to some number Y that can be made as a sum of the elements, how many times do you have to ask before you know the whole collection, as a function of N?

For example, if you have the collection {2, 2, 10}, you can determine the set in four guesses, if you somehow know to ask exactly the right numbers. First, ask for the closest sum to infinity, which tells you 14 is the sum of all elements. Your guess for the set is currently {14}. Next, ask for the closest sum to 12, which returns 12. Your guess for the set is now {2, 12}. Next, ask for the closest number to 10. Your guess for the set is now {2, 2, 10}. Finally, ask for the closest number to 7, which gives 10. The only number less than ten that is further from 7 than 10 is 4. 4 cannot be in the set, as to get a total sum of 14, you would also have to have a 6 (or some combination of numbers that add to six) which is impossible, as you already know the closest number/sum to 7 in the set is 10.

In other words, how many different attempted withdrawals from an atm do you have to make to determine what bills are in the atm?

What are the average minimal values as a function of N? The average average values from some algorithm? The average average values from guessing randomly?
Quote


Messages In This Thread
wonderings - by a52 - 11-27-2016, 09:11 PM
RE: wonderings - by a52 - 11-27-2016, 09:15 PM
RE: wonderings - by a52 - 11-27-2016, 09:17 PM
RE: wonderings - by a52 - 11-27-2016, 09:27 PM
RE: wonderings - by a52 - 11-27-2016, 09:45 PM
RE: wonderings - by a52 - 11-27-2016, 09:59 PM
RE: wonderings - by OTTO - 11-28-2016, 06:39 AM
RE: wonderings - by a52 - 11-28-2016, 06:59 AM
RE: wonderings - by Dragon Fogel - 11-27-2016, 10:07 PM
RE: wonderings - by Our Lady of Lampreys - 12-20-2016, 03:34 AM
RE: wonderings - by a52 - 11-27-2016, 10:10 PM
RE: wonderings - by a52 - 11-27-2016, 10:14 PM
RE: wonderings - by a52 - 12-18-2016, 08:30 PM
RE: wonderings - by Dragon Fogel - 12-20-2016, 04:05 AM
RE: wonderings - by a52 - 12-20-2016, 07:18 AM
RE: wonderings - by Our Lady of Lampreys - 12-20-2016, 07:42 PM
RE: wonderings - by a52 - 12-24-2016, 07:09 PM
RE: wonderings - by Kaynato - 12-24-2016, 07:21 PM
RE: wonderings - by a52 - 12-24-2016, 08:31 PM
RE: wonderings - by Kaynato - 12-24-2016, 10:42 PM
RE: wonderings - by a52 - 01-08-2017, 05:11 PM
RE: wonderings - by Sleepy - 01-10-2017, 09:37 PM
RE: wonderings - by ICan'tGiveCredit - 01-10-2017, 10:16 PM
RE: wonderings - by a52 - 01-13-2017, 05:34 AM
RE: wonderings - by a52 - 02-03-2017, 03:15 AM
RE: wonderings - by ☆ C.H.W.O.K.A ☆ - 02-06-2017, 09:10 PM
RE: wonderings - by a52 - 02-03-2017, 03:16 AM
RE: wonderings - by a52 - 02-03-2017, 03:38 AM
RE: wonderings - by a52 - 02-03-2017, 04:01 AM
RE: wonderings - by a52 - 03-16-2017, 01:44 AM
RE: wonderings - by a52 - 03-16-2017, 04:40 AM
RE: wonderings - by a52 - 03-16-2017, 01:47 AM
RE: wonderings - by a52 - 03-16-2017, 01:53 AM
RE: wonderings - by Kíeros - 03-16-2017, 03:16 AM
RE: wonderings - by a52 - 04-06-2017, 04:52 PM
RE: wonderings - by a52 - 05-27-2017, 02:18 AM
RE: wonderings - by qwerx3 - 05-27-2017, 08:26 AM
RE: wonderings - by qwerx3 - 05-27-2017, 08:38 AM
RE: wonderings - by a52 - 06-04-2017, 05:48 AM
RE: wonderings - by ICan'tGiveCredit - 06-04-2017, 02:23 PM
RE: wonderings - by a52 - 06-09-2017, 01:48 AM
RE: wonderings - by a52 - 08-09-2017, 08:16 PM
RE: wonderings - by ICan'tGiveCredit - 08-09-2017, 09:03 PM
RE: wonderings - by a52 - 08-10-2017, 03:03 AM
RE: wonderings - by a52 - 08-14-2017, 10:06 PM
RE: wonderings - by a52 - 08-14-2017, 10:30 PM
RE: wonderings - by wyatt - 08-21-2017, 03:46 PM
RE: wonderings - by Reyweld - 08-21-2017, 04:08 PM
RE: wonderings - by a52 - 09-23-2017, 08:41 PM
RE: wonderings - by a52 - 12-11-2017, 01:17 AM
RE: wonderings - by Our Lady of Lampreys - 12-12-2017, 07:04 PM
RE: wonderings - by Myeth - 12-12-2017, 10:30 PM
RE: wonderings - by Reyweld - 12-12-2017, 10:54 PM
RE: wonderings - by Myeth - 12-13-2017, 12:22 AM
RE: wonderings - by a52 - 02-23-2018, 08:56 AM
RE: wonderings - by a52 - 04-23-2018, 06:23 PM
RE: wonderings - by a52 - 05-04-2018, 08:07 AM
RE: wonderings - by a52 - 05-04-2018, 08:14 AM
RE: wonderings - by Myeth - 05-04-2018, 08:31 AM
RE: wonderings - by a52 - 05-05-2018, 02:19 AM
RE: wonderings - by ICan'tGiveCredit - 05-05-2018, 01:42 PM
RE: wonderings - by a52 - 10-22-2018, 09:08 PM
RE: wonderings - by a52 - 10-22-2018, 09:16 PM
RE: wonderings - by a52 - 05-21-2019, 03:07 AM